1 files changed, 137 insertions, 0 deletions
diff --git a/src/quicksort.s b/src/quicksort.s
new file mode 100755
index 0000000..78b9eea
--- /dev/null
+++ b/src/quicksort.s
@@ -0,0 +1,137 @@
+# --------------------------------------------
+# FUNCTION: quicksort
+# PURPOSE : Calls the _quicksort function with the right parameters
+# INPUTS  : rdi = address for A
+#           rsi = number of coordinates n
+#           rdx = index of key to sort by
+# OUTPUTS : rax = address for sorted A
+# NOTES   : preserves rdi, rdx
+# --------------------------------------------
+.section .text
+.globl quicksort
+.type quicksort, @function
+quicksort:
+    leaq -1(%rsi), %rcx
+    xorq %rsi, %rsi
+    call _quicksort
+    ret
+
+# --------------------------------------------
+# FUNCTION: _quicksort
+# 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 = low
+#           rdx = index of key to sort by
+#           rcx = high
+# OUTPUTS : rax = address for sorted A
+# NOTES   : preserves rdi, rdx
+# --------------------------------------------
+.section .text
+# .globl _quicksort
+.type _quicksort, @function
+_quicksort:
+    pushq %r12
+    pushq %r13
+    pushq %r14
+
+    cmpq $0, %rsi               # if 0 < low 
+    jl .qsort_exit
+    cmpq $0, %rcx               # if 0 < high 
+    jl .qsort_exit
+    cmpq %rcx, %rsi             # if high < low 
+    jge .qsort_exit
+
+    call hoare_part             # rax = p
+
+    movq %rsi, %r12             # save low
+    movq %rcx, %r13             # save high
+    movq %rax, %r14             # save p
+
+# --- left recursion ---
+    movq %r12, %rsi             # low
+    movq %r14, %rcx             # high = p
+    call _quicksort
+    
+# --- right recursion ---
+    leaq 1(%r14), %rsi          # low = p + 1
+    movq %r13, %rcx             # high
+    call _quicksort
+
+.qsort_exit:
+    movq %rdi, %rax
+
+    popq %r14
+    popq %r13
+    popq %r12
+    ret
+
+# --------------------------------------------
+# FUNCTION: hoare_part
+# 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 = low
+#           rdx = index of key to sort by
+#           rcx = high
+# OUTPUTS : rax = address for sorted A
+# NOTES   : preserves rdi, rdx
+# --------------------------------------------
+.section .text
+.globl hoare_part
+.type hoare_part, @function
+hoare_part:
+    pushq %rbx
+    pushq %r12
+    pushq %r13
+    pushq %r14
+
+    leaq -1(%rsi), %rax         # i = low - 1
+    leaq 1(%rcx), %rbx          # j = high + 1
+
+    # r12 = pivot
+    movq (%rdi, %rsi, 8), %r12  # &A[low]
+    movq (%r12, %rdx, 8), %r12  # A[low][idx]
+    
+# left index
+.hoare_part_left:
+    incq %rax
+
+    movq (%rdi, %rax, 8), %r13  # &A[i]
+    movq (%r13, %rdx, 8), %r13  # A[i][idx]
+
+    cmpq %r12, %r13             # while pivot < A[i][idx]
+    jl .hoare_part_left
+
+# right index
+.hoare_part_right:
+    decq %rbx
+
+    movq (%rdi, %rbx, 8), %r13  # &A[j]
+    movq (%r13, %rdx, 8), %r13  # A[j][idx]
+
+    cmpq %r12, %r13             # while pivot > A[j][idx] 
+    jg .hoare_part_right
+
+# check crossing
+    cmpq %rbx, %rax             # i >= j
+    jge .hoare_part_done
+
+# swap A[i] and A[j]
+    movq (%rdi, %rax, 8), %r13
+    movq (%rdi, %rbx, 8), %r14
+    movq %r14, (%rdi, %rax, 8)
+    movq %r13, (%rdi, %rbx, 8)
+
+    jmp .hoare_part_left
+
+.hoare_part_done:
+    movq %rbx, %rax             # return j as partion index
+
+    popq %r14
+    popq %r13
+    popq %r12
+    popq %rbx
+    ret