Отключаемые счетчики электроэнергии на пульте. Все с документами пломбами, гарантией и без посредников!

Сортировка

Сортировка

В этом разделе будет показаны способ отыскания наибольшего (наименьшего) значения среди массива чисел и два фундаментальных метода сортировки (обменом и выбором), адаптированных для системы команд AVR. Это так называемым “простые” методам сортировки. Для того чтобы упорядочить массив из n элементов они требуют порядка n2 операций сравнения. Существуют и более совершенные “логарифмические” методы, для которых тот же показатель эффективности составляет n*ln(n). Однако в микроконтроллерных приложениях скорость работы последних не оправдывает сложности алгоритма. Да и преимущества их начинают сказываться только при больших значениях n. С массивами малых размеров “простые” методы справляются также хорошо, как и “логарифмические” или даже быстрее.

На практике необходимость в сортировке чаще всего возникает, когда надо упорядочить список событий. Если, например, в памяти хранится набор установок времени, каждой из которых соответствует определенное действие системы, то будет очень удобно, если все они окажутся упорядоченными по возрастанию (в порядке следования во времени). Кроме того, сортировка, как правило, является самым простым способом отыскания медианы (элемента выборки, значение которого меньше или равно половины элементов и больше или равно другой половины). Очевидно, что в отсортированном массиве, состоящем из n чисел, медианой является элемент под номером n/2 + 1, а пара элементов с индексами 0 и n-1 имеют граничные значения.

Отыскание минимального и максимального элементов

Найти наибольшее (наименьшее) значение среди массива чисел очень легко. Достаточно взять произвольный элемент последовательности (скажем самый первый) и поочередно сравнить его со всеми остальными. В самом начале первый элемент считается самым большим числом, но если во время сравнения находится элемент с большим числовым значением, то тогда уже ему присваивается статус наибольшего и т.д. Подпрограмма для нахождения максимального значения приведена на рис.1. Замена в ней условия перехода brcc на brcs, позволит получить на выходе наименьший элемент списка.

; Подпрограмма нахождения наибольшего элемента массива чисел ; YH:YL – указатель на элемент массива чисел ; R16 – регистр для промежуточных операций ; R17 – наибольшее элемент массива на выходе ; R18 – счетчик итераций сравнения ; array – адрес начала массива сортируемых чисел ; ASIZE – размер массива (2…256) max_item: ldi R18,ASIZE-1 ;инициализируем счетчик итераций ldi YH,high(array) ;заносим в указатель адрес начала ldi YL,low(array) ;массива чисел ld R16,Y+ ;в R16 заносим первый элемент массива mx1:ld R17,Y+ ;в R17 заносим i элемент массива cp R16,R17 ;сравниваем текущий наибольший элемент brcc mx2 ;с i элементом массива и если он mov R16,R17 ;оказывается меньше, то меняем их местами mx2: dec R18 ;декрементируем счетчик R18 и если R18=0, brne mx1 ret ;то цикл сравнений закончен


Категория: Микроконтроллеры
Метки:

Написать коментарий

*
= 5 + 6

Добавить изображение

Последние статьи