# PROWAREtech

## x64 Assembly: Quick Sort (qsort) Procedure

*The famous quicksort algorithm in x86-64 (64-bit) assembly.*

*This code was compiled and tested on Visual Studio 2022.*

*This same procedure is available in x86 Assembly.*

Quicksort is a great, reliable general purpose sorting algorithm. The `TITLE`

is the C/C++ function declaration.

This short procedure can sort an array of pointers to strings or objects... or anything. `compare_func`

must return less than zero when `element1`

is less than `element2`

, zero when they are equal, and greater than zero when `element1`

is greater than `element2`

.This version of quick sort uses insertion sort to sort smaller sub arrays.

Quicksort is a highly efficient and widely used sorting algorithm that employs the divide-and-conquer strategy. Here are the key aspects of the quicksort algorithm:

### Basic Idea

Quicksort works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

### Steps of Quicksort

**Choose a Pivot**: Select an element from the array to serve as the pivot. Various strategies exist for choosing the pivot, such as picking the first element, the last element, a random element, or the median.**Partitioning**: Rearrange the array so that elements less than the pivot are on the left, elements greater than the pivot are on the right, and the pivot is in its final position. This process is called partitioning.**Recursively Sort Sub-arrays**: Apply the same process recursively to the sub-arrays of elements with smaller and larger values.

### Key Points

**Time Complexity**: The average-case time complexity is O(n•log(n)) O(n•log(n)), where n is the number of elements to be sorted. In the worst case, which occurs when the smallest or largest element is always chosen as the pivot, the time complexity is O(n^{2}). However, with good pivot selection (e.g., using the median-of-three rule), the average case is more likely.**Space Complexity**: Quicksort is an in-place sorting algorithm, meaning it requires only a small, constant amount of extra storage space (i.e., O(log(n)) due to the recursion stack).**Stability**: Quicksort is not a stable sort, meaning that the relative order of equal sort items is not preserved.

### Advantages and Disadvantages

**Advantages**:

- Generally faster than other (n•log(n)) algorithms like merge sort and heap sort for most inputs.
- In-place sorting, requiring minimal additional memory.

**Disadvantages**:

- Worst-case performance is O(n
^{2}), though this can be mitigated with good pivot selection. - Not stable, so it may not be suitable when the stability of equal elements is required.

### Practical Considerations

**Pivot Selection**: Strategies like random pivot, median-of-three (selecting the median of the first, middle, and last elements), and others help avoid the worst-case scenarios.

Quicksort is widely used due to its efficiency and simplicity, especially for large datasets. Its performance can be significantly improved with good pivot selection and implementation optimizations.

```
TITLE 'extern "C" void qisort(void* array_to_sort[], const unsigned long long array_size, long long (*compare_func)(const void* element1, const void* element2));'
PUBLIC qisort
_TEXT SEGMENT
array_to_sort = 40
array_size = 48
qisort PROC
mov QWORD PTR [rsp+16], rdx
mov QWORD PTR [rsp+8], rcx
sub rsp, 32
cmp QWORD PTR array_size[rsp], 30
ja quick_sort
insertion_sort:
mov r15, QWORD PTR array_to_sort[rsp]
mov r9, 1
insertion_sort_main_loop:
mov rax, QWORD PTR array_size[rsp]
cmp r9, rax
jae exit
mov r11, QWORD PTR [r15+r9*8]
mov r10, r9
insertion_sort_sub_loop:
cmp r10, 0
jbe SHORT exit_insertion_sort_sub_loop
mov rdx, QWORD PTR [r15+r10*8-8]
mov rcx, r11
call r8 ; call the compare_func function
test rax, rax
jge SHORT exit_insertion_sort_sub_loop
mov rdx, QWORD PTR [r15+r10*8-8]
mov QWORD PTR [r15+r10*8], rdx
dec r10 ; r10 is a local variable used for indexing
jmp SHORT insertion_sort_sub_loop
exit_insertion_sort_sub_loop:
mov QWORD PTR [r15+r10*8], r11
inc r9 ; r9 is a local variable used for indexing
jmp insertion_sort_main_loop
quick_sort:
mov rax, QWORD PTR array_size[rsp]
shr rax, 1 ; divide array_size by 2
mov r15, QWORD PTR array_to_sort[rsp]
mov r12, QWORD PTR [r15+rax*8]
mov r14, r15 ; move array_to_sort to left (r14)
mov rax, r15 ; load array_to_sort pointer value
mov r15, QWORD PTR array_size[rsp] ; load array_size
lea r13, QWORD PTR [rax+r15*8-8] ; the right (r13) equals array_to_sort + array_size - 8 bytes
quick_sort_sub_loop_1:
cmp r14, r13 ; compare left (r14) to right (r13)
ja SHORT quick_sort_sub_loop_2
mov rdx, r12 ; move pivot into rdx for call compare_func
mov rcx, QWORD PTR [r14] ; move left into rcx for call compare_func
call r8 ; call the compare_func function
test rax, rax
jge SHORT quick_sort_sub_loop_2
add r14, 8 ; increment left (r14) eight bytes
jmp SHORT quick_sort_sub_loop_1
quick_sort_sub_loop_2:
cmp r14, r13 ; compare left (r14) to right (r13)
ja SHORT quick_sort_check_left_greater_than_right
mov rdx, r12 ; move pivot into rdx for call compare_func
mov rcx, QWORD PTR [r13]
call r8 ; call the compare_func function
test rax, rax
jle SHORT quick_sort_check_left_greater_than_right
sub r13, 8 ; decrement right (r13) eight bytes
jmp SHORT quick_sort_sub_loop_2
quick_sort_check_left_greater_than_right:
cmp r14, r13 ; compare left (r14) to right (r13)
jbe SHORT quick_sort_swap
jmp SHORT call_quick_sort
quick_sort_swap:
mov r11, QWORD PTR [r14] ; move left (r14) value to temp varaible (r11)
mov rcx, QWORD PTR [r13] ; move right (r13) value to rcx
mov QWORD PTR [r14], rcx ; move ecx to left (r14) value
add r14, 8 ; increment left (r14) eight bytes
mov QWORD PTR [r13], r11
sub r13, 8 ; decrement right (r13) eight bytes
jmp quick_sort_sub_loop_1
call_quick_sort:
mov rax, QWORD PTR array_to_sort[rsp]
mov rcx, r13 ; move right (r13) to rcx
sub rcx, rax
mov rdx, rcx
sar rdx, 3
inc rdx ; rdx is the new array_size value (right - array_to_sort + 8 bytes)
mov rcx, QWORD PTR array_to_sort[rsp] ; rcx is the pointer to array_to_sort
call qisort ; r8 is already set to compare_func
mov rax, QWORD PTR array_to_sort[rsp]
mov rcx, QWORD PTR array_size[rsp]
lea rax, QWORD PTR [rax+rcx*8]
sub rax, r14 ; subtract left (r14 - pointer) from rax
sar rax, 3
mov rdx, rax ; set rdx to new array_size (array_to_sort - array_size * 8 - left (r14))
mov rcx, r14 ; set rcx to left (r14) which is the new array_to_sort value
call qisort ; r8 is already set to compare_func
exit:
add rsp, 32
ret 0
qisort ENDP
_TEXT ENDS
END
```