Сортировка обменом

Сортировка обменом

Сортировка обменом (или пузырьковая сортировка) – это самый простой способом упорядочить массив чисел, с точки зрения затрат программных ресурсов. Алгоритм пузырьковой сортировки очень прост для понимания и легок в реализации.

Сортировка обменом

Рассмотрим, как работает этот метод с набором из пяти чисел, расположенных случайным образом. Задача пузырьковой сортировки заключается в том, чтобы за каждый просмотр массива выявлять элемент с наименьшим весом. Для этого, в нашем случае, сначала сравниваются числа 1 и 3. Поскольку 1<3, то элементы меняются местами. Далее сравнению подлежат числа 1 и 2 и, так как 1<2, снова происходит их обмена и т.д. Таким образом, самый маленький “пузырек” c весом 1 всплывает в самый верх очереди. Оставшийся неупорядоченный массив из 4-рех элементов (наименьший элемент 1 уже найден) продолжает сортироваться тем же способом.

Подпрограмма пузырьковой сортировки массива 1-байтовых чисел:

; Подпрограмма пузырьковой сортировки массива чисел ; YH:YL – указатель на элемент массив чисел ; R16,R17 – регистры для промежуточных операций ; R18 – счетчик итераций сравнения ; array – адрес начала массива сортируемых чисел ; ASIZE – размер массива (2…256) ; Время сортировки массива из 256 1-байтовых чисел: ; обратная последовательность (0…255) – 524287 циклов ; прямая последовательность (255…0) – 459007 циклов bubble_sort: ldi R18,ASIZE-1 ;инициализируем счетчик проходов bs1:push R18 ;сохраняем счетчик проходов в стеке ldi YH,high(array) ;заносим в указатель адрес начала ldi YL,low(array) ;сортируемого массива bs2:ld R16,Y ;в R16 заносим i элемент массива ldd R17,Y+ ;в R17 заносим i+1 элемент массива cp R16,R17 ;сравниваем элементы i с i+1 brcc bs3 ;если элемент с индексом i меньше элемента eor R16,R17 ;с индексом i+1, то меняем их местами eor R17,R16 eor R16,R17 bs3: st Y+,R16 ;заносим содержимое R16, R17 в массив st Y,R17 dec R18 ;декрементируем счетчик и если нуль brne bs2 ;проход закончен, pop R18 ;то восстанавливаем счетчик проходов и dec R18 ;продолжаем сортировку пока не будут brne bs1 ;упорядочено MEMSIZE элементов ret

Интересно отметить, что разница во времени сортировки массивов с прямой и обратной последовательностями элементов (наихудший и наилучший случаи соответственно), очень мала. Это объясняется тем, что операция обмена двух байтов местами потребуют для своего выполнения всего на 2 машинных цикла больше чем программный переход, когда в перестановке нет необходимости. В общем случае стоит ожидать, что пузырьковая сортировка будет работать эффективней с более упорядоченными последовательностями. Если в изначально упорядоченный массив добавляется новый элемент, то понадобится всего один проход для того, чтобы поставить его на свое место.

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


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

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

*
= 5 + 8

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

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