Что не так с моей сборкой Bubble Sort? - PullRequest
Новая
       88

Что не так с моей сборкой Bubble Sort?

2 голосов
/ 24 апреля 2020

Я реализую Bubble Sort в сборке с базовым c псевдокодом / контуром: 

for i in array
    if array[i] >= array[i+1]
        exchange array[i], array[i+1]

Мой код ASM: 

BubbleSort PROC
    mov     EBX, LENGTHOF myArr
    .REPEAT
        mov     ESI, 0
        mov     ECX, LENGTHOF myArr
        .REPEAT
            mov     EAX, [myArr + ESI]
            .IF EAX >= [myArr + ESI + TYPE myArr]       ; If (myArr[i] < myArr[i + 1])
                xchg    EAX, [myArr + ESI + TYPE myArr]
                mov     [myArr + ESI], EAX
            .ENDIF

            add     ESI, TYPE myArr
            dec     ECX
        .UNTIL ECX == 0
    dec     EBX
    .UNTIL EBX == 0
    ret
BubbleSort ENDP

Когда я показал свою реализацию моему профессору Он сказал, что это «своего рода пузырьковая сортировка» или «тип пузырьковой сортировки». Говоря нам о назначении, он сказал, что мы должны начать с задней части массива и двигаться вперед-назад. Все же я начинаю с фронта и двигаюсь спереди назад.

Мне кажется, что я на правильном пути, и код работает, но я хочу сделать это правильно.

Кто-нибудь видит, где я облажался?

1 Ответ

2 голосов
/ 24 апреля 2020

Если ваш код работает, это определенно Bubble Sort. Хорошо пузыриться к любому концу массива, поэтому не нужно оптимизировать, как использовать внешний счетчик l oop (EBX) в качестве верхней границы для внутреннего l oop.

Быть упрощенным c или наивный не мешает ему быть Bubble Sort. (Во всяком случае, простота c и наивность - это весь смысл Bubble Sort.)

См. Также Bubble Sort: археологический алгоритм c Анализ для получения дополнительной информации о история Bubble Sort, с некоторым обсуждением связанной JumpDown Sort и того, используете ли вы логическое значение как ранний выход.

Версия BubbleSort, которую она представляет, запускает внешнюю l oop из j=n-1 до 1 (включительно), поэтому внутренний l oop может использовать его в качестве верхней границы. Но внутренний l oop такой же, как и у вас, от k = 0 до j, условно меняя местами A[j] на A[j+1], и, таким образом, пузырьки элементов к концу массива.

Версия в Википедии также всплывает вверх, выполняя i от 1 до n-1 (включительно). На самом деле у Wiki есть 2 версии: первая наивная, такая как ваша, и вторая, которая уменьшается на n внутри l oop. (Обе версии Wiki используют логическую переменную для записи, если она делала какие-либо перестановки, усложняя алгоритм и подавляя единственную цель / преимущество Bubble Sort, которая должна быть очень простой и иметь крошечный код. (Например, около 20 байтов x86 машинный код , хотя он сильно оптимизирован по размеру и скорости. Более нормальная реализация будет аналогична размеру InsertionSort.)

В вашем коде используются макросы MASM, которые в конечном итоге приводят к потере инструкций по повторному выполнению проверок ( Я предполагаю, что .UNTIL ECX == 0 не использует тот факт, что dec ecx уже просто установил флаги в соответствии с ненулевым ECX), но у него действительно есть хорошая структура do{}while() l oop, которая является идиоматической c для asm .

Кстати, в вашем псевдокоде отсутствует внешний l oop. Это только один проход BubbleSort. Но да, итерация этого n раз приведет к сортировке массива n элементов.

...