Главная » Микроконтроллеры
Призовой фонд
на май 2017 г.
1. Тестер компонентов MG328
Паяльник
2. Осциллограф DSO138
Паяльник
3. Регулируемый паяльник 60 Вт
Паяльник
4. 100 руб.
От пользователей

Похожие статьи:


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

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

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

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

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

Теги:

Котов Игорь Юрьевич Опубликована: 2012 г. 0 0
Я собрал 0 0
x

Оценить статью

  • Техническая грамотность
  • Актуальность материала
  • Изложение материала
  • Полезность устройства
  • Повторяемость устройства
  • Орфография
0

Средний балл статьи: 0 Проголосовало: 0 чел.

Комментарии (2) | Я собрал (0) | Подписаться

0
Alexander #
Немного изменил алгоритм автора: стал короче и работает быстрее. Также добавил возможность выбирать порядок сортировки и возможность передавать в качестве параметра адрес массива

;Производительность алгоритмов на массиве 256 элементов
; BUBBLE_SORT SELECT_SORT
;Случайный 380917 315915 17%
;Отсортированный 329977 263935 20%
;Обратный 427507 349667 18%

; SELECT_SORT Подпрограмма сортировки выбором
; http://kvodo.ru/sortirovka-vyiborom-2.html сортировки выбором
; YH:YL, ZH:ZL– указатели на элементы массива чисел
; R16,R17 – регистры для промежуточных операций
; R18 – счетчик итераций сравнения
; array – адрес начала массива сортируемых чисел
; size – размер массива (2…256)
; Пример:
; .EQU _SELECT_SORT_ONE_BUFFER_ = 1 - в программе только один массива для сортировки, тогда
; адрес и размер массива НЕ передаётся в функцию, а определяется меткой array и константой size
; .EQU _SELECT_SORT_DESCENDING_ = 1 - сортировка по убыванию

; ldi ZH,high(array+size) ;заносим в указатель Z адрес i-го
; ldi ZL,low(array+size) ;элемента сортируемого массива
; ldi R18,size-1 ;инициализируем счетчик проходов
; call SELECT_SORT
; Если массив один (_SELECT_SORT_ONE_BUFFER_ определён), тогда достаточно просто вызвать функцию:
; call SELECT_SORT
; Начало массива должно быть определено меткой array, размер задан в size

.IFDEF _GENPROCLIB_SELECT_SORT_
SELECT_SORT:
.IFDEF _SELECT_SORT_ONE_BUFFER_
ldi R18,size-1 ;инициализируем счетчик проходов
ldi ZH,high(array+size) ;заносим в указатель Z адрес i-го
ldi ZL,low(array+size) ;элемента сортируемого массива
.ENDIF
movw Y,Z ;заносим в указатель Y адрес j-го
sbiw Y,1 ;следующего элемента массива
SELECT_SORT_1: ;внешний цикл
push R18 ;сохраняем счетчик проходов в стеке
ld R16,-Z ;в R16 заносим i элемент массива
SELECT_SORT_2: ;внутренний цикл
ld R17,-Y ;в R17 заносим i+j элемент массива
cp R16,R17 ;сравниваем элементы i с i+j
.IFDEF _SELECT_SORT_DESCENDING_
brcs SELECT_SORT_3 ; по убыванию
.ELSE
brcc SELECT_SORT_3 ; по возрастанию
.ENDIF
st Z,R17 ;меняем местами
st Y,R16
mov R16,R17
SELECT_SORT_3:
dec R18 ;декрементируем счетчик и если
brne SELECT_SORT_2 ;нуль, то проход закончен
pop R18
movw Y,Z
sbiw Y,1
dec R18 ;декрементируем счетчик и если
brne SELECT_SORT_1 ;нуль, то сортировка завершена закончен
ret
.ENDIF
Ответить
0
Григорий #
В листинге (в строке 25), возможно, ошибка. Лишний раз инкрементируется X. Должно быть "st X,16".
Ответить
Добавить комментарий
Имя:
E-mail:
не публикуется
Текст:
Защита от спама:
В чем измеряется электрическая мощность?
Файлы:
 
Для выбора нескольких файлов использйте CTRL

Pickit 2 - USB-программатор PIC-микроконтроллеров
Pickit 2 - USB-программатор PIC-микроконтроллеров
Модуль радиореле на 4 канала Мультиметр DT9205A
вверх