Description
The Gnome sort is a very basic sorting algorithm that combines the Insertion sort and the Bubble sort.
The code size is very small and easy to understand, uses only one loop and it’s a stable algorithm. Unfortunately, it’s not very fast compared to other algorithms.
It was invented by Hamid Sarbazi-Azad in 2000.
The algorithm works this way:
It iterates through the array, comparing the current element with the previous one. If it finds that they are out of order, it swaps them and then it moves backwards one space, if not, it just moves forward.
This algorithm has a best case speed of O(n), and an average and worst case speeds of O(n^2).
For faster algorithms look at Insertion sort or, even faster, the Quicksort.
Code
NOTE: This is used to sort an array of 4 byte data types. In order to keep the algorithm as simple as possible for this example, the array is traversed in increments and decrements of 4.
If you want to use this algorithm to sort items of smaller or larger data types, the solution would be to send the size of the data as a parameter and use that when traversing the array.
.model flat, c
.code
;Code by Miguel Casillas.
;This code can be used and reproduced, please give credit
;void GnomeSort(void *pArray, int nItems);
GnomeSort PROC
;These registers must be restored at the end
push EBP
mov EBP, ESP
push EBX
push ESI
push EDI
;EBP + 8 is the array
;EBP + 12 is the number of items in the array
mov ESI, [EBP+8] ;ESI is the array
mov ECX, [EBP+12] ;setting ECX to the number of items
xor EAX, EAX ;Setting EAX to 0, it'll be our iterator
MainLoop:
;If 'i' >= the number of items, exit the loop
cmp EAX, ECX
jge EndLoop
;If 'i' == 0, move to the next element
cmp EAX, 0
je IncreaseCounter
;If array[i-1] <= array[i], it means they are
;sorted, so move to the next element
mov EBX, [ESI] ;EBX = array[i]
mov EDX, [ESI-4] ;EDX = array[i-1]
cmp EDX, EBX
jle IncreaseCounter
;else, swap array[i-1] with array[i]
push [ESI]
push [ESI-4]
pop [ESI]
pop [ESI-4]
;Move to the previous element in the array
;and decrease 'i'
sub ESI, 4
dec EAX
;Loop back to the top
BackToMainLoop:
jmp MainLoop
;Moving to the next element in the array
;and increasing 'i'
IncreaseCounter:
inc EAX
add ESI, 4
jmp BackToMainLoop
EndLoop:
;Restoring the registers
pop EDI
pop ESI
pop EBX
pop EBP
RET
GnomeSort ENDP
END
Results
Sorting a list of 10,000 random integers took an average time of 0.1484936 seconds, which ended up being pretty much the same as the compiled C++ version of this algorithm.