Author Topic: How to sort array in assending order in asm?  (Read 9825 times)

Offline arex

  • Jr. Member
  • *
  • Posts: 3
How to sort array in assending order in asm?
« on: August 27, 2020, 02:14:13 AM »
Greeting,  I am new in nasm. I want to know how to sort an array in assending order using nasm. I have zero idea what to do. I took help from many sites from internet but to no avail.

Offline fredericopissarra

  • Full Member
  • **
  • Posts: 368
  • Country: br
Re: How to sort array in assending order in asm?
« Reply #1 on: August 27, 2020, 11:52:07 AM »
Greeting,  I am new in nasm. I want to know how to sort an array in assending order using nasm. I have zero idea what to do. I took help from many sites from internet but to no avail.
A simple selection sort will do?

Offline arex

  • Jr. Member
  • *
  • Posts: 3
Re: How to sort array in assending order in asm?
« Reply #2 on: August 27, 2020, 01:02:53 PM »
I am using bubble sort. This is what I have done so far
Code: (asm) [Select]
section .data
   array dd 2,3,4,5,6
section .text
   global main
main:
  call check
  cmp eax, ebx
  jg swap
  call print
  call safe_exit
check:
  mov ecx, 0
  mov eax, [array + ecx]
  add eax, '0'
  mov ebx, [array + ecx + 4]
  add ebx, '0'
  ret
swap:
  mov edx, eax ; temp = a
  mov eax, ebx ; a = b
  mov ebx, edx ; b = temp
  call print
print:
  mov [array], eax
  mov ecx, array
  mov edx,1
  mov ebx,edx
  mov eax,4
  int 80h
  ret
safe_exit:
  mov ebx,0
  mov eax,1
  int 80h
 
But now, I want to add loops (inner and outer loop)

Offline fredericopissarra

  • Full Member
  • **
  • Posts: 368
  • Country: br
Re: How to sort array in assending order in asm?
« Reply #3 on: August 27, 2020, 01:58:18 PM »
Not much, huh? Ok, here's a step by step of an selection sorting routine.

1st- To sort an array you'll need the address of this array and its size (elements). Let's assume RSI holds the address and ECX its number of elements.

Code: [Select]
; Entry: RSI points to array, ECX has the number of elements.
selectsort:
  ; Something goes here.
  ret

2nd- You don't need to sort an array of 0 or 1 elements:

Code: [Select]
; Entry: RSI points to array, ECX has the number of elements.
selectionsort:
  cmp   ecx,1
  jbe   .exit

  ; Something goes here.

.exit:
  ret

3rd- In selection sort you use 2 pointers. One pointing to the selected element at the beginning of the array, which "travels" to the element before the last; and other pointer to point to the next element after the first, which "travels" to the last element. So you'll need to know the last element. Since we are dealing with DWORDs here, you must remember to multiply the number of elements by 4. Let's say this pointer to the last element is our "destination" ponteiro (hold it on RDI):

Code: [Select]
; Entry: RSI points to array, ECX has the number of elements.
selectionsort:
  cmp   ecx,1
  jbe   .exit

  mov   ecx,ecx         ; Just to make sure the upper 32 bits
                        ; are zeroed.

  lea   rdi,[rsi + rcx*4 - 4] ; RDI points to the last element now.

  ; Something goes here.

.exit:
  ret

We had to subtract 4 because if not, we'll point pass the last element.

4th- Now we can code the main loop, Incrementing RDI until it reaches the last element...

Code: [Select]
; Entry: RSI points to array, ECX has the number of elements.
selectionsort:
  cmp   ecx,1
  jbe   .exit

  mov   ecx,ecx         ; Just to make sure the upper 32 bits
                        ; are zeroed.

  lea   rdi,[rsi + rcx*4 - 4] ; RDI points to the last element now.

.loop:

  ; Something goes here.

  add   rsi,4
  cmp   rsi,rdi         ; Reached the last element?
  jb    .loop           ; No? loop.

.exit:
  ret

5th- Now we code the inner loop, setting up the other pointer (that which will point to the 'unsorted' elements) and keep in this inner loop util it passes the last element:

Code: [Select]
; Entry: RSI points to array, ECX has the number of elements.
selectionsort:
  cmp   ecx,1
  jbe   .exit

  mov   ecx,ecx         ; Just to make sure the upper 32 bits
                        ; are zeroed.

  lea   rdi,[rsi + rcx*4 - 4] ; RDI points to the last element now.

.loop:
  lea   rdx,[rsi+4]     ; Using RDX as pointer to unsorted elements
                        ; after selection.

.innerloop:

  ; Something goes here.

  add   rdx,4
  cmp   rdx,rdi         ; Reached pass the last element?
  jbe   .innerloop      ; No? keep in the inner loop.

  add   rsi,4
  cmp   rsi,rdi         ; Reached the last element?
  jb    .loop           ; No? loop.

.exit:
  ret

6th- Now we can compare elements pointed by RSI and RDX and swap them, if necessary:

Code: [Select]
; Entry: RSI points to array, ECX has the number of elements.
; Destroys: RAX, RCX, RDX, RSI and RDI.
selectionsort:
  cmp   ecx,1
  jbe   .exit

  mov   ecx,ecx         ; Just to make sure the upper 32 bits
                        ; are zeroed.

  lea   rdi,[rsi + rcx*4 - 4] ; RDI points to the last element now.

.loop:
  lea   rdx,[rsi+4]     ; Using RDX as pointer to unsorted elements
                        ; after selection.

.innerloop:
  mov   eax,[rsi]
  mov   ecx,[rdx]
  cmp   eax,ecx
  jle   .noswap         ; Change it to JBE if you are dealing with
                        ; 'unsigned' integers.
  mov   [rsi],ecx
  mov   [rdx],eax
.noswap:

  add   rdx,4
  cmp   rdx,rdi         ; Reached pass the last element?
  jbe   .innerloop      ; No? keep in the inner loop.

  add   rsi,4
  cmp   rsi,rdi         ; Reached the last element?
  jb    .loop           ; No? loop.

.exit:
  ret

VoilĂ !
« Last Edit: August 27, 2020, 02:03:44 PM by fredericopissarra »

Offline fredericopissarra

  • Full Member
  • **
  • Posts: 368
  • Country: br
Re: How to sort array in assending order in asm?
« Reply #4 on: August 27, 2020, 02:19:21 PM »
Notice I am using amd64 mode here. Change it acoodingly...

Offline arex

  • Jr. Member
  • *
  • Posts: 3
Re: How to sort array in assending order in asm?
« Reply #5 on: August 28, 2020, 02:17:51 AM »
Notice I am using amd64 mode here. Change it acoodingly...
Thank you alot for your support. But I am very new in nasm and using 32-bit. Can you optimize my above code to perform sorting? Also, I am trying to do bubble sort. But selection sort is also acceptable

Offline fredericopissarra

  • Full Member
  • **
  • Posts: 368
  • Country: br
Re: How to sort array in assending order in asm?
« Reply #6 on: August 28, 2020, 12:49:42 PM »
The traditional Bubble sort algorithm do the oposite of selection sort. Instead of dragging the smallest value to the front of the array, it drags the greatest value to the end, doing in pairs, as demonstrated in this animation:



So, the principle almost the same: You setup the pointers and do the swapping, if necessary. Half of the fun is to implement the algorithms, I'll not do this for you, sorry.