Сортировка

В этом разделе будет показаны способ отыскания наибольшего (наименьшего) значения среди массива чисел и два фундаментальных метода сортировки (обменом и выбором), адаптированных для системы команд 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           ;то цикл сравнений закончен

Перейти к следующей части: Сортировка обменом

Теги:

• AVR
• Микроконтроллер