assembly 装配件-选择排序

7kqas0il 于 2022-11-13 发布在其他

关注(0)|答案(1)|浏览(116)

在阅读了关于这个主题的各种教程和Stackoverflow答案几个小时后，我试图以自己的方式在emu 8086中实现这个算法;虽然我非常接近完成这一点，但在修复了许多错误后，我无法理解我哪里出错了，如果有人能帮助我，我将不胜感激。

select_sort    PROC
    pusha                ; push all register values
    mov    bp, sp
    mov    cx, [bp+20]        ; transfer no. of integers to cx
    mov    bx, [bp+18]        ; and integer array address to bx

loop_outer:
    dec    cx
    jz    done               ; if cx=0, done
    mov    di, cx            ; else another iteration
    mov    dx, SORTED        ; assume status of array as sorted
    mov    si, bx            ; transfer array address to si     
            

loop_inner:
    mov    al, [si]
    cmp    al, [si+2]
    jc     resume
    mov    ah, [si+2]              

resume:
    add    si, 2
    dec    di
    jnz    loop_inner
    cmp    dx, SORTED
    je    done
    jmp    swap

swap:    
    xchg    ax, [si+2]        ; swap integers at [si] and [si+2]
    mov    [si], ax
    mov    dx, UNSORTED        ; mark status of array as unsorted
    jmp    loop_outer

done:
    popa                ; pop to respective register locations
    ret    4
select_sort    ENDP

我的输入：534210
输出：53421
预期输出：12345
虽然我认为我的选择排序算法的逻辑是好的，但我不明白为什么我没有得到确切的输出。

assembly

来源：https://stackoverflow.com/questions/67554786/assembly-selection-sort

1条答案

按热度按时间

8ftvxx2r1#

不是选择排序

swap integers at [si] and [si+2]

如果你要交换相邻的元素，那么你就更接近BubbleSort了。SelectionSort的思想是交换距离更远的元素，并从中受益。
为什么不起作用
当你的 loop_inner 找到一个更小的元素时，它应该将状态切换为UNSORTED。

选择排序

下面是一个正确的选择排序，我们找到最小的元素，并把它放在未排序分区的前面。然后我们扩展已排序分区，并缩小未排序分区。BX寄存器将一直指向它们之间的分隔。这个过程将数组分为一个增长的已排序分区和一个缩小的未排序分区。我们继续，直到出现'在未排序的分区中只剩下1个元素。

select_sort    PROC
    pusha
    mov    bp, sp
    mov    cx, [bp+20] ; Number of integers
    mov    bx, [bp+18] ; Address of array

    sub    cx, 1       ; Ready if 0 or 1 element(s)
    jbe    Done

OuterLoop:
    mov    dx, cx      ; Number of comparisons to make
    mov    si, bx      ; Start of the unsorted partition
    mov    ax, [si]    ; Value of chosen minimum
    mov    di, si      ; Position of chosen minimum
InnerLoop:
    add    si, 2
    cmp    [si], ax
    jnb    NotSmaller
    mov    ax, [si]    ; Value of new minimum
    mov    di, si      ; Position of new minimum
NotSmaller:
    dec    dx
    jnz    InnerLoop

    mov    dx, [bx]    ; Swap elements
    mov    [bx], ax
    mov    [di], dx

    add    bx, 2       ; Move the dividing border
    dec    cx
    jnz    OuterLoop

Done:
    popa
    ret    4
select_sort    ENDP

以下是排序对示例输入数据的作用（S=已排序，U=未排序）：

UUUUUUUUUUUUUU
5, 3, 4, 2, 1     CX=4
^           ^
BX          DI

SSSUUUUUUUUUUU
1, 3, 4, 2, 5     CX=3
   ^     ^
   BX    DI

SSSSSSUUUUUUUU
1, 2, 4, 3, 5     CX=2
      ^  ^
      BX DI

SSSSSSSSSUUUUU
1, 2, 3, 4, 5     CX=1
         ^
         BX
         DI

SSSSSSSSSSSSUU
1, 2, 3, 4, 5     CX=0
            ^
            BX

SSSSSSSSSSSSSS
1, 2, 3, 4, 5

赞(0）回复(0）举报 2022-11-13

我来回答

assembly 装配件-选择排序

1条答案

不是选择排序

选择排序

相关问题

热门标签

最新问答