Сортировка выбором

Сортировка выбором

Сортировка выбором потребует немного больше памяти и регистров, чем сортировка обменом, но в большинстве случаев будет выполняться быстрее.

Сортировка выбором

Подобно пузырьковой сортировке за каждый проход массива также выявляется один элемент, но несколько иным способом. Сперва берется самый первый элемент последовательности и поочередно сравнивается с оставшимися элементами. Если в ходе просмотра находится элемент с большим весом, то происходит  обмена местами. В конце цикла сравнений наибольше число выборки размещается в голове очереди. В нашем случае на первом проходе производится серия сравнений: 1 и 3 (1<3, числа меняются местами), 3 и 2 (3>2, числа сохраняют свои позиции), 3 и 4, 4 и 5. Точно также наибольший элемент выбирается из массива оставшихся 4-ч чисел и т.д. Подпрограмма сортировки выбором:

; Подпрограмма пузырьковой сортировки массива чисел ; XH:XL, YH:YL– указатели на элементы массива чисел ; R16,R17 – регистры для промежуточных операций ; R18 – счетчик итераций сравнения ; array – адрес начала массива сортируемых чисел ; ASIZE – размер массива (2…256) ; Время сортировки массива из 256 1-байтовых чисел: ; обратная последовательность (0…255) – 462071 циклов ; прямая последовательность (255…0) – 331511 циклов select_sort: ldi YH,high(array) ;заносим в указатель Y адрес i-го ldi YL,low(array) ;элемента сортируемого массива ldi XH,high(memory+1);заносим в указатель X адрес j-го ldi XL,low(memory+1) ;следующего элемента массива ldi R18,ASIZE-1 ;инициализируем счетчик проходов ss1:push R18 ;сохраняем счетчик проходов в стеке push XH ;сохраняем указатель X в стеке push XL ld R16,Y ;в R16 заносим i элемент массива ss2:ld R17,X ;в R17 заносим i+j элемент массива cp R16,R17 ;сравниваем элементы i с i+j brcc ss3 ;если элемент с индексом i меньше элемента st Y,R17 ;с индексом i+j, то меняем их местами st X+,R16 mov R16,R17 ss3:adiw XH:XL,1 dec R18 ;декрементируем счетчик и если brne ss2 ;нуль, то проход закончен pop XL ;восстанавливаем указатель X из стеке pop XH pop R18 adiw YH:YL,1 ;перемещаем указатели X и Y на следующие adiw XH:XL,1 ;на следующую пару элементов dec R18 ;декрементируем счетчик и если brne ss1 ;нуль, то сортировка завершена закончен ret

Как видим из сравнительных тестов, сортировка выбором существенно превосходит пузырьковую сортировку в плане эффективности работы. Скорость обработки массива из 256 байт у второй на 10…40% выше. С ростом числа элементов этот показатель будет еще лучше. Может показаться, что алгоритм сортировки выбором всегда работает быстрее, но на самом деле это не так. При небольших размерах массива чисел (примерно до 8 элементов) именно пузырьковая сортировка будет иметь преимущество и, например, с указанной выше последовательностью справится за 213 машинных циклов против 227 у сортировки выбором.

Перейти к следующей части:


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

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

*
= 3 + 9

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

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