Assembly - Selection Sort

Question

After reading various tutorials and Stackoverflow answers for hours on this topic, I tried to implement this algorithm in emu8086 in my own way; although I am very close to completing this but after fixing many errors, i am unable to understand where I went wrong, I would appreciate if anyone would help me with this.

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

My input : 534210

Output : 53421

Expected output : 12345

Although I think the logic of my selection sort algorithm is okay, I am not able understand why I am not getting the exact output.

Answer 1

It's not selection sort

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

If you're going to swap adjacent elements, then you're closer to BubbleSort. The idea of a SelectionSort is to swap elements over longer distances and benefit from it.

Why it didn't work

When your loop_inner finds a smaller element it should toggle the status to UNSORTED. Because you didn't, the algorithm ended too soon.

Selection sort

Below is a correct selection sort where we find the smallest element and bring it to the front of the unsorted partition. We then expand the sorted partition and shrink the unsorted partition. The BX register will keep pointing at the separation between them. This process keeps dividing the array in a growing sorted partition and a diminishing unsorted partition. We continue until there's only 1 element left in the unsorted partition.

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

This is what the sort does to your example input data (S=Sorted, U=Unsorted):

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