我的程序集冒泡排序有什么问题？

Question

我正在使用基本伪代码/大纲在汇编中实现冒泡排序：

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

当我向我的教授展示我的实现时，他说它 "kind of" 像冒泡排序或 "type of" 冒泡排序。在告诉我们作业时，他说我们应该从数组的后面开始，然后从后到前移动。然而，我是从前面开始，然后从前到后移动。

我觉得我走在正确的轨道上并且代码有效，但我想正确地执行它。

有人看到我哪里搞砸了吗？

Answer 1

假设您的代码有效，肯定是冒泡排序。向数组的任一端冒泡都很好，因此可以省略优化，例如使用外循环计数器 (EBX) 作为内循环的上限。

简单化或天真并不能阻止它成为冒泡排序。（如果有的话，简单化和天真就是冒泡排序的全部意义。）

另请参阅 Bubble Sort: An Archaeological Algorithmic Analysis 以了解有关冒泡排序历史的更多信息，以及对相关 JumpDown 排序的一些讨论，以及是否使用布尔值作为提前输出。

它提供的 BubbleSort 版本运行从 j=n-1 到 1（含）的外循环，因此内循环可以将其用作上限。但是内部循环与你的相同，从 k=0 到 j，有条件地将 A[j] 与 A[j+1] 交换，从而将元素冒泡到数组的末尾。

版本 on Wikipedia also bubbles upwards, running i from 1 to n-1 (inclusive). Wiki actually has 2 versions: that first naive one like yours, and a second that decrements n inside the loop. (Both Wiki's versions use a boolean variable to record if it did any swaps, complicating the algorithm and defeating the only purpose / advantage of Bubble Sort which is to be dead simple and have tiny code. (e.g. about 20 bytes of x86 machine code，尽管它针对大小而非速度进行了大量优化。更正常的实现将与 InsertionSort 的大小相似。）

您的代码使用 MASM 宏，最终会浪费指令重做检查（我假设 .UNTIL ECX == 0 没有利用 dec ecx 已经根据 ECX 设置标志的事实是非-零）。但它确实有良好的 do{}while() 循环结构，这是 asm 惯用的。

顺便说一句，您的伪代码缺少外循环。这只是 BubbleSort 的一次通过。但是，是的，迭代 n 次将对 n 元素数组进行排序。

我的程序集冒泡排序有什么问题？

What's wrong with my assembly Bubble Sort?

x86

assembly

masm

bubble-sort