Sorting through an array after filling in x86 MASM assembly language

Question

can anyone help me with this problem, I'm new to assembly language and somewhat stuck on what to do next. Here's the code:

.data
evenStart    dword          11h
oddStart     dword          20h
darray       dword          15 dup (?)
.code
main PROC
    mov esi, OFFSET darray
    xor ecx, ecx
    
L1: 
    mov ebx, OFFSET evenStart
    test cl,1
    jz iseven
    mov ebx, OFFSET oddStart
    
iseven:
    mov eax, [ebx]
    inc dword ptr [ebx]
    mov dword ptr [esi + 4*ecx],eax
    inc ecx
    cmp ecx,15
    jb L1
    
    exit
main ENDP
END main

So the project requires me to fill the uninitilized array, which I did. But then it also ask me to sort through this array in descending order and then put the middle elements of the array into the eax register and call DumpRegs. This is the part where I got stuck in. Any help on how to proceed would be great. Thank you!

Do you mean loop backwards over it, since you know it has this alternating ascending order from filling it, so going backwards would be descending? Or are you supposed to actually modify the array by just sorting it, like with InsertionSort? (Rather than "sorting through"; that English phrasing could mean searching it). — Peter Cordes, Sep 28 '20 at 00:13
@PeterCordes I meant actually sorting the array, like for example if the array consists of 15 20 11 14, after sorting, it would be 20 15 14 11. Something like that. — , Sep 28 '20 at 01:03
Ok, that's a common problem that's been solved boatloads of times. Google up an answer if you want to see how someone else implements sorting of a dword array. Unless you're supposed to take advantage of the known contents based on the odd/even initializers, and rewrite the array into a sorted order with a single loop? — Peter Cordes, Sep 28 '20 at 01:04
@PeterCordes yes, that is exactly what I'm trying to achieve here, because most of the array sorting have a whole array already initialized. In this case, I have to fill the array with values based on the odd/even initializers, so I don't know how to approach it. I figure there would another loop inside of my code, but I'm not exactly sure. — , Sep 28 '20 at 01:12
Well the simple thing is just to fill the array and then sort it. Yes, after the end of the first loop, just write a 2nd loop (this one will be a nested loop; simple sort algorithms are O(n^2)). Same as other programming languages, you can put 2 separate things one after the other. — Peter Cordes, Sep 28 '20 at 01:25
But if you want to do something based on how it was initialized, save the starting values of the odd/even initializers. Then calculate the difference to see whether the sorted result will be all-odd then all-even, or whether there's a part in the middle where they overlap. (You can develop the algorithm in some other language to get it correct before implementing in asm) After some decisions, this can get done in O(N) steps. — Peter Cordes, Sep 28 '20 at 01:27
@PeterCordes can you show me a snippet of code of how to implement that nested loop? Much appreciated! — , Sep 28 '20 at 02:47

score 1 · Answer 1 · answered Sep 28 '20 at 22:47

1

Next Bubble Sort uses nested loops. Because your array has 15 elements, the outer loop can do 14 comparisons during its 1st iteration. With each iteration of the outer loop it has to do 1 comparison less because the smallest element has bubbled towards the end of the array.

    mov ebx, 15-1      ; Outer loop iteration count
OuterLoop:
    mov esi, offset darray

    mov ecx, ebx       ; Inner loop iteration count
InnerLoop:
    lodsd
    mov edx, [esi]
    cmp eax, edx
    jge Skip
    mov [esi-4], edx   ; Swap these 2 elements
    mov [esi], eax
Skip:
    dec ecx
    jnz InnerLoop

    dec ebx
    jnz OuterLoop

The unsorted array: 11h, 20h, 12h, 21h, 13h, 22h, 14h, 23h, 15h, 24h, 16h, 25h, 17h, 26h, 18h

The sorted array: 26h, 25h, 24h, 23h, 22h, 21h, 20h, 18h, 17h, 16h, 15h, 14h, 13h, 12h, 11h

In this array with an odd number of elements (15), the element indexes range from 0 to 14. There is a true middle element at index 7.

answered Sep 28 '20 at 22:47

Sep Roland

33,889
7
43
76

1

Why pick Bubble Sort? Insertion Sort is a better algorithm and also easy to implement. – Peter Cordes Sep 28 '20 at 23:21
@PeterCordes I think what we call 'easy', could still be challenging in this case. – Sep Roland Sep 28 '20 at 23:28
I meant "easy for us", who know asm and are writing answers. Since you're choosing which sorting algorithm to show as an example, why show [the worst one](https://stackoverflow.com/questions/61997897/why-bubble-sort-is-not-efficient)? Especially since there are existing examples of it all over the place on Stack Overflow so we could just close it as a duplicate of a bubblesort question. If you just wanted to write a clean and compact Bubble Sort, there are other Q&As where you could post this, e.g. [Assembly bubble sort swap](https://stackoverflow.com/q/11497966) – Peter Cordes Sep 28 '20 at 23:48
Jerry Coffin posted a similar Insertion Sort in a comment there: [Assembly bubble sort swap](https://stackoverflow.com/posts/comments/83151822) – Peter Cordes Sep 28 '20 at 23:51

Sorting through an array after filling in x86 MASM assembly language

1 Answers1