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

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

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

Подобно пузырьковой сортировке за каждый проход массива также выявляется один элемент, но несколько иным способом. Сперва берется самый первый элемент последовательности и поочередно сравнивается с оставшимися элементами. Если в ходе просмотра находится элемент с большим весом, то происходит  обмена местами. В конце цикла сравнений наибольше число выборки размещается в голове очереди. В нашем случае на первом проходе производится серия сравнений: 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 у сортировки выбором.

Перейти к следующей части: Ввод информации - Матричная клавиатура

Теги:

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