NASM - The Netwide Assembler
NASM Forum => Using NASM => Topic started by: arex 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.
-
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?
-
I am using bubble sort. This is what I have done so far
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)
-
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.
; 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:
; 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):
; 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...
; 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:
; 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:
; 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Ă !
-
Notice I am using amd64 mode here. Change it acoodingly...
-
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
-
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:
(https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif)
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.