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

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

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

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

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

Теги:

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