Description
Quicksort is a very fast, very efficient “divide and conquer” sorting algorithm invented by Tony Hoare in 1960 in Moscow State University.
The algorithm works this way:
First, a pivot is chosen (for this example, we will use the low index. A more efficient pivot would be the median of the first, middle and last values, but we’ll keep it simple for this example). Then, the elements of the array are compared against that pivot and put on either the left or the right.
After this is done, the array will be divided into two smaller arrays, and the function will be called recursively until all elements are sorted.
It’s best and average case speeds are of O(n log n), but it’s worst case speed is of O(n^2).
Also, this is not a stable algorithm. In the case of sorting integers, this doesn’t matter, but if we were sorting a data type where the entire key is not the entire element, then stability would come into play.
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 QuickSort(void *pArray, int nItems);
QuickSort 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
;setting ECX to the number of items
;we multiply by 4 (size of the element) in order to put ECX
;at the last address of the array
mov EAX, [EBP+12]
mov ECX, 4
mul ECX
mov ECX, EAX
;EAX will be our 'low index', we initially set it to 0
xor EAX, EAX
;EBX will be our 'high index', we initially set it to
;the last element of the array (currently stored in ECX)
mov EBX, ECX
;We now call our recursive function that will sort the array
call QuickRecursive
;Restoring the registers
pop EDI
pop ESI
pop EBX
pop EBP
RET
QuickSort ENDP
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Recursive QuickSort function
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
QuickRecursive:
;if lowIndex >= highIndex, we exit the function
cmp EAX, EBX
jge PostIf
push EAX ;saving our low index, now EAX is 'i'
push EBX ;saving our high index, now EBX is 'j'
add EBX, 4 ;j = high + 1
;EDI is our pivot
;pivot = array[lowIndex];
mov EDI, [ESI+EAX]
MainLoop:
iIncreaseLoop:
;i++
add EAX, 4
;If i >= j, exit this loop
cmp EAX, EBX
jge End_iIncreaseLoop
;If array[i] >= pivot, exit this loop
cmp [ESI+EAX], EDI
jge End_iIncreaseLoop
;Go back to the top of this loop
jmp iIncreaseLoop
End_iIncreaseLoop:
jDecreaseLoop:
;j--
sub EBX, 4
;If array[j] <= pivot, exit this loop
cmp [ESI+EBX], EDI
jle End_jDecreaseLoop
;Go back to the top of this loop
jmp jDecreaseLoop
End_jDecreaseLoop:
;If i >= j, then don't swap and end the main loop
cmp EAX, EBX
jge EndMainLoop
;Else, swap array[i] with array [j]
push [ESI+EAX]
push [ESI+EBX]
pop [ESI+EAX]
pop [ESI+EBX]
;Go back to the top of the main loop
jmp MainLoop
EndMainLoop:
;Restore the high index into EDI
pop EDI
;Restore the low index into ECX
pop ECX
;If low index == j, don't swap
cmp ECX, EBX
je EndSwap
;Else, swap array[low index] with array[j]
push [ESI+ECX]
push [ESI+EBX]
pop [ESI+ECX]
pop [ESI+EBX]
EndSwap:
;Setting EAX back to the low index
mov EAX, ECX
push EDI ;Saving the high Index
push EBX ;Saving j
sub EBX, 4 ;Setting EBX to j-1
;QuickSort(array, low index, j-1)
call QuickRecursive
;Restore 'j' into EAX
pop EAX
add EAX, 4 ;setting EAX to j+1
;Restore the high index into EBX
pop EBX
;QuickSort(array, j+1, high index)
call QuickRecursive
PostIf:
RET
END
Results
Sorting a list of 10,000 random integers took an average time of 0.0007905865 seconds, which ended up being about 1% of the time of the Insertion Sort, and about 0.5% of the time of the Gnome Sort. Also, this assembly version of the quicksort is as fast as the compiled C++ version of it.