Working qsort I think

So far looks like it is working, cannot be tested with 'test.sh' since
quick sort is not a stable sorting algorithm

2 files changed, 118 insertions, 1 deletions

diff --git a/src/main.s b/src/main.s
index c0d6e85..318bb02 100644
--- a/src/main.s
+++ b/src/main.s
@@ -17,7 +17,7 @@ _start:
     movq %rax, %rdi             # Select address of array
     movq %r15, %rsi             # Select length of array
     movq $1, %rdx               # Sort by key 1
-    call insertion_sort         # Sort the array
+    call qsort                  # Sort the array
     
     # Print array
     movq %rax, %rdi             # Select the pointer to the array
diff --git a/src/qsort.s b/src/qsort.s
new file mode 100644
index 0000000..addcf5a
--- /dev/null
+++ b/src/qsort.s
@@ -0,0 +1,117 @@
+# --------------------------------------------
+# FUNCTION: qsort
+# PURPOSE : Sorts array A, with references to arrays A_i,
+#           based on the given key in A_i,
+#           address and size of A.
+# INPUTS  : rdi = address for A
+#           rsi = number of coordinates n
+#           rdx = index of key to sort by
+# OUTPUTS : rax = address for sorted A
+# CLOBBERS: none
+# --------------------------------------------
+.section .text
+.globl qsort
+.type qsort, @function
+qsort:
+    pushq %r12
+    pushq %r13
+    pushq %r14
+    pushq %rbx
+
+    cmp $1, %rsi
+    jle .qsort_done
+
+    call hoare_part
+    movq %rax, %r12             # r8 = partition
+    movq %rdi, %r13             # r13 = original array pointer
+    movq %rsi, %r14             # r14 = original n
+    movq %rdx, %rbx             # rbx = column index
+
+    # --- left recursion ---
+    movq %r13, %rdi
+    movq %r12, %rsi             # n = p
+    movq %rbx, %rdx             # restore column
+    call qsort
+
+    # --- right recursion ---
+    leaq 1(%r12), %rax          # rax = p + 1
+    leaq (%r13, %rax, 8), %rdi  # rdi = A + (p + 1)
+    movq %r14, %rsi             # rsi = original n
+    subq %rax, %rsi             # rsi = n - (p + 1)
+    movq %rbx, %rdx             # restore column
+    call qsort
+
+.qsort_done:
+    movq %r13, %rax
+    popq %rbx
+    popq %r14
+    popq %r13
+    popq %r12
+    ret
+
+# --------------------------------------------
+# FUNCTION: hoare_part
+# PURPOSE : 
+# INPUTS  : rdi = address for A
+#           rsi = number of coordinates n
+#           rdx = index of key to sort by
+# OUTPUTS : rax = Returns the partition index
+#           for quicksort.
+# --------------------------------------------
+.globl hoare_part
+.type hoare_part, @function
+hoare_part: 
+    pushq %r12
+    pushq %r13
+
+    movq $-1, %r8               # i = -1
+    movq %rsi, %r9              # j = arr.len
+    movq (%rdi), %r10           # pivot = &arr[0]
+    movq (%r10, %rdx, 8), %r11  # value of pivot
+    pushq %r11
+
+.hoare_loop:
+# increment i
+.hoare_Li:
+    addq $1, %r8
+
+    cmpq %r9, %r8
+    jge .hoare_done
+
+    movq (%rdi, %r8, 8), %r13
+    movq (%r13, %rdx, 8), %r12  # value of arr[i]
+
+    cmpq %r11, %r12             # if arr[i] < pivot
+    jl .hoare_Li
+    
+# decrement j
+.hoare_Lj:
+    subq $1, %r9
+
+    cmpq $0, %r9
+    jl .hoare_done
+
+    movq (%rdi, %r9, 8), %r13
+    movq (%r13, %rdx, 8), %r12  # value of arr[j]
+
+    cmpq %r11, %r12             # if arr[j] > pivot
+    jg .hoare_Lj
+
+    # check crossing
+    cmpq %r9, %r8               # if arr[i] > arr[j]
+    jge .hoare_done
+    
+    # swap a[i] and a[j]
+    movq (%rdi, %r8, 8), %r12
+    movq (%rdi, %r9, 8), %r13
+    movq %r13, (%rdi, %r8, 8)
+    movq %r12, (%rdi, %r9, 8)
+
+    jmp .hoare_loop
+
+.hoare_done:
+    popq %r11
+    popq %r13
+    popq %r12
+    movq %r9, %rax
+    ret