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

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

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

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

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

Answer 1

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

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

---

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

它提供的 BubbleSort 版本运行从 j=n-1 到 1(含)的外层循环，因此内层循环可以将它用作上层循环边界。但是内层循环和你的一样，从k=0到j，有条件地将A[j]和A[j+1]交换>，因此将元素冒泡到数组的末尾。

版本on Wikipedia也向上冒泡，运行 i 从 1 到 n-1(含)。 Wiki 实际上有两个版本:第一个像你的那样天真，第二个在循环内递减 n。 (Wiki 的两个版本都使用 bool 变量来记录它是否进行了任何交换，这使算法复杂化并破坏了冒泡排序的唯一目的/优势，即非常简单并且代码很少。(例如 about 20 bytes of x86 machine code ，尽管它经过了大量优化对于大小而不是速度。更正常的实现将与 InsertionSort 的大小相似。)

---

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

---

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