NASM 组装插入排序

Question

我是汇编语言的新手，但我仍然坚持这项任务。我需要插入排序汇编语言方面的帮助。我在汇编代码中没有得到 array[j+1] := array[j] 部分。
我的任务是：

编写一个汇编语言程序，使用插入排序算法对字节数组 (a) (a = {7, 5, 2, 3, 6}) 进行排序。请在内存中分配数组大小为 size = 5。
插入排序背后的基本原理很简单：将一个新数字插入到已排序数组的适当位置。为了应用这个算法，我们从一个空数组开始。然后插入第一个数字。现在数组已按排序顺序排列，只有一个元素。接下来将第二个数字插入到适当的位置。这会产生大小为 2 的排序数组。重复此过程，直到插入所有数字。该算法的伪代码如下所示，假设数组索引以 0 开头：

Insertion Sort (array, size)
for (i = 1; i < size −1; i + +) do
temp := array[i]
j := i −1
while ((temp < array[j]) and (j ≥0)) do
array[j + 1] := array[j]
j := j −1
end while
array[j + 1] := temp
end for

这里，索引 i 指向要插入的数字。 i 左边的数组是按排序顺序排列的。要插入的数字是位于索引 i 或其右侧的数字。下一个要插入的数字位于 i 处。

这是我得到的：

 segment .data
array    db   7,5,2,3,6
size     db   5
Sorted   times 5 db 0



            segment .text
            global main
main:   
        mov rsi, [Sorted]
      ;  mov edx,[size]
        sub edx,4                    ; size -1 
        mov ecx,1                    ;for (i = 1;
        
        for: cmp edx,ecx              ; i< size - 1; i++)
             je  finish               ; i = 0 then exit
             movsx rbx, byte[array + rcx] ; temp = array[i]
             mov rax, rcx          ; j = i - 1           
             sub rax,1  
           while:                  ;while ( temp < array[j] && j >= 0)
             cmp rax,0             ; j >= 0?   
             jl end_while     
             cmp rbx,[array + rax] ; temp < array[j]?
             jae end_while
           next:                     
             mov  r8, [array + rax + 1] ;????
             mov  r9, [array + rax]     ;????
             mov  r8,r9          ; array[j+1] := array[j]
             mov rsi,r8
             dec rax             ; j = j -1 
             inc rcx
             jmp 
             
            end_while:
             mov [Sorted + rax -1] ,rbx  ; array[j + 1] = temp
             inc rcx         
             jmp for 
             
          
       
   finish:

Answer 1

伪代码执行就地插入排序，而汇编代码选择将排序后的元素放在其他位置（不修改原始数组）。这是一个有效的选择，但是元素的比较应该在已排序的数组中完成，而不是像在未排序的数组中所做的那样！

汇编代码中有很多错误。

• mov rsi, [Sorted] 应该做什么？在您使用的 NASM 中，这将从内存中加载 8 个字节。也许您打算加载已排序数组的地址，那么它必须是 mov rsi, Sorted 或 lea rsi, [Sorted]。 （或者甚至与 RIP 相关......）

• 如果您将注释符号保留在 中； mov edx,[size] 没有希望建立正确的迭代计数。

• 第一次从源数组中获取元素时，您使用的是 ECX=1。对于某些高级语言来说这可能没问题，但在汇编中我们使用数组的偏移量（并且始终以字节为单位计数）。您应该已初始化 ECX=0。

• 因为您的数组包含字节大小的元素，所以像 cmp rbx,[array + rax] 这样的指令将比较 7 个字节太多！只需使用cmp bl，...。

• 类似地，mov [Sorted + rax -1] ,rbx ; array[j + 1] = temp 将覆盖 8 个字节，而您应该只插入一个字节。另外，我们将其视为拼写错误，但根据下面的注释，rax - 1 确实应该是 rax + 1。

插入排序背后的基本原理很简单：将一个新数字插入已排序数组的适当位置。为了应用这个算法，我们从一个空数组开始。然后插入第一个数字。现在数组已按排序顺序排列，只有一个元素。接下来将第二个数字插入到适当的位置。这会产生大小为 2 的排序数组。重复此过程，直到插入所有数字。该算法的伪代码如下所示，假设数组索引以 0 开头

。这是我的插入排序版本。我根本没有遵循伪代码。我研究了任务描述中提供的非常清晰的解释，并仅基于此编写了此解决方案。某些高级语言的代码版本对于尝试理解手头的任务当然很有用，但在我看来，将高级代码紧密地转换为汇编语言是朝着错误方向迈出的一步。你必须在组装时思考。这和你学外语没有什么不同...

    xor ecx, ecx                   ; i := 0
.Top:
    mov bl, [Array + rcx]          ; Array[i]
    mov edx, ecx                   ; j := i
.While:
    sub edx, 1                     ; j := j - 1
    jb  .EndWhile
    mov al, [Sorted + rdx]         ; AL := Sorted[j]
    cmp bl, al
    jae .EndWhile
    mov [Sorted + rdx + 1], al     ; Sorted[j + 1] := AL
    jmp .While
.EndWhile:
    mov [Sorted + rdx + 1], bl     ; Sorted[j + 1] := Array[i]
    inc ecx                        ; i := i + 1
    cmp ecx, 5
    jb  .Top