Sort an array with emu8086 (Assembler)

Question

I have to type and array (only with numbers) and when a introduce it, it must be sorted in a second one. All I have to do is to implement the PROC which has to sort them. My problem is that I don't know how, because the only thing I have achieved is to copy the first one into the second one. Thanks for your help and sorry for my English.

;mov ax, vector[si]
;mov vector[di], ax
;this loop copy all elements
; start code
Sort_DecreasingOrder: 

cmp si, 0
mov ax, vector1[si] 

bCompare:
xor di, di
mov bx, vector2[di]
cmp ax, bx
jge IntroduceBefore

An example for "bubble" sort is [here](http://stackoverflow.com/a/26324630/3512216). — rkhb, Apr 08 '17 at 12:43

Ahtisham · Answer 1 · 2017-11-30T12:03:27.187

1

There is another way of Sorting know as Selection Sort and here its:

Data segment is defined as:

 elements db 7,1,0,5,'$'
 size dw $-elements - 1      ; size stores 5 (including '$') so we subtract one now it stores 4 ( which is the actual number of elements )
 msg db 10,13,'Unsorted Array: $'        
 msg2 db 10,13,'Sorted Array: $'

Procedure to sort an array:

sort proc    

    mov cx, size      
    mov si, 0 
    mov di, 0
    mov ax, 1 ; this is done 
    dec cx    ; to avoid the last comparison

    outerLoop:        

        push cx  ; store the limit of outerLoop in stack  

        mov bl, elements[si]    ; store the element in bl pointed by si                                                  

        mov cx, size   ; store the value of size in cx for innerLoop        
        sub cx, ax     ; this is done so that the limit does not proceed the limit of array elements.

        innerLoop:

             inc di                   

             cmp bl, elements[di]  ; compare the if BL is not greater than  
             jna continue          ; content of element pointed by DI if yes then continue otherwise swap the value by executing below statements  

             mov dl, elements[di]   ; get the element pointed by DI into DL
             mov elements[di], bl   ; swap the 
             mov elements[si], dl   ; elements
             mov bl, dl             ; store the smallest element in BL                              

             continue: 

        loop inner 

        inc ax                                                         

        pop cx  ; get the limit of outerLoop

        inc si  ; increment the index of outerLoop to point to the next element  

        mov di, si 

        loop outer                        

    return2:    

         ret     

sort endp                

end

edited Nov 30 '17 at 12:03

answered Nov 22 '17 at 04:14

Ahtisham

9,170
4
43
57

1

That's a lot of swapping every time you find a new candidate element. That's barely SelectionSort anymore. Just record where you found the element and swap at the end with the final max. Also, using [atomic `xchg` (i.e. xchg with a memory operand)](http://felixcloutier.com/x86/XCHG.html) makes this *much* slower than it needs to be. Also, `jna continue` would make more sense than `ja` / `jmp`. Or better, a branch structure that optimizes for the compare being false and not needing a swap. – Peter Cordes Nov 22 '17 at 09:08
1

You don't need the CPU to swap registers with `xchg dl,bl`, just store the opposite register. Also, you already have `bl` = `elements[si]`, so you don't need to load it again. (But then you will need a `mov bl,dl` instruction I guess) – Peter Cordes Nov 22 '17 at 09:29
@Peter Cordes I was a bit hurry when i wrote that code so didn't had time for optimization. I am still hurry though because i have to prepare for exam that is day after tomorrow. – Ahtisham Nov 22 '17 at 09:35
BTW, swapping with the new min-candidate is not Selection Sort, but I recently found out it has a name: JumpDown Sort. It's sort of half way between BubbleSort and SelectionSort. See [Bubble Sort: An Archaeological Algorithmic Analysis](https://users.cs.duke.edu/~ola/papers/bubble.pdf). (And also my [19-byte implementation of JumpDown Sort](https://codegolf.stackexchange.com/questions/77836/sort-an-integer-list/149038#149038) for x86-16/32/64, sorting 16 or 32-bit integers, or bytes.) Also, mine has comments, yours doesn't... – Peter Cordes Nov 30 '17 at 03:43
@PeterCordes How is it different than selection sort ? In selection sort we compute the minimum element and place it at first position ( if sorting is in ascending order ) and that is exactly what my code does so how is it different than selection sort ? – Ahtisham Nov 30 '17 at 12:16
The difference is interesting, actually, if you watch the array change in a debugger. e.g. `display *(int[12] *)$ebx` in GDB to have it print the array pointed to by `ebx` every time you stop at a breakpoint. Then set a breakpoint at the end of the inner loop, and "continue". You'll notice that towards the end of the sort, the remaining "unsorted" portion is sorted in reverse order (by the process of dropping off a higher number every time you find a new min). It starts to degenerate into a worst-case bubble-sort towards the end. (Or earlier if the array is far from sorted). – Peter Cordes Nov 30 '17 at 19:04
In an algorithm theoretical sense, JumpDown sort does more swaps than SelectionSort, and swaps are generally more expensive. (Selection does `O(n)` swaps, IDK if JumpDown's swap count is a higher complexity class, but probably.) But with branch prediction, it's expensive to find a new min whether you actually swap or not (unless most elements are a new min, then not-new-min will mispredict). The problem with JumpDown is what I said before: it leaves the unsorted part more and more in decreasing order, so later scans find a new min more often than with Selection Sort. – Peter Cordes Nov 30 '17 at 19:08
re: the comments: `mov cx, size` is a *load*. Never use the word "store" when describing a load from memory, it's confusing. And BTW, using AX as an up-counter is pretty clunky. Using push/pop lets you use CX as two separate counters, without having to reload it inside either loop. See how [my code-golfed JumpDown sort manages `rcx`](https://codegolf.stackexchange.com/questions/77836/sort-an-integer-list/149038#149038) with just two nested `loop`s and `push`/`pop` around the inner one. An increasing AX to set CX=size-AX for the inner just seems more complex. – Peter Cordes Nov 30 '17 at 19:46

Sort an array with emu8086 (Assembler)

1 Answers1

Linked