From 4f17cf1441ebbe13137bdd2acf4a7ba3228b80b5 Mon Sep 17 00:00:00 2001
From: mithe24 <mithe24@student.sdu.dk>
Date: Mon, 27 Oct 2025 09:08:22 +0100
Subject: fix(qsort): Quicksort errors. And why is length 1-indexed :(

---
 src/qsort.s | 80 +++++++++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 45 deletions(-)

(limited to 'src/qsort.s')

diff --git a/src/qsort.s b/src/qsort.s
index addcf5a..233ec34 100644
--- a/src/qsort.s
+++ b/src/qsort.s
@@ -13,40 +13,35 @@
 .globl qsort
 .type qsort, @function
 qsort:
+    pushq %rbx
     pushq %r12
     pushq %r13
-    pushq %r14
-    pushq %rbx
 
     cmp $1, %rsi
     jle .qsort_done
 
+    movq %rdi, %r12             # r12 = original array pointer
+    movq %rsi, %r13             # r13 = original length
     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
+    movq %rax, %rbx             # rbx = partition
 
     # --- left recursion ---
-    movq %r13, %rdi
-    movq %r12, %rsi             # n = p
-    movq %rbx, %rdx             # restore column
+    movq %r12, %rdi
+    movq %rbx, %rsi             # n = p
     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
+    leaq 1(%rbx), %rax          # rax = p + 1
+    leaq (%r12, %rax, 8), %rdi  # rdi = A + (p + 1)
+    movq %r13, %rsi             # rsi = original length
     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
+    movq %r12, %rax             # just returning the same buffer
+    popq %r13                   # as quicksort is inplace
     popq %r12
+    popq %rbx
     ret
 
 # --------------------------------------------
@@ -57,61 +52,56 @@ qsort:
 #           rdx = index of key to sort by
 # OUTPUTS : rax = Returns the partition index
 #           for quicksort.
+# NOTES   : rdx is preserved
 # --------------------------------------------
 .globl hoare_part
 .type hoare_part, @function
 hoare_part: 
+    pushq %rbx
     pushq %r12
     pushq %r13
+    pushq %r14
 
-    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
+    movq $-1, %rax              # i = -1
+    leaq 1(%rsi), %rbx          # j = n + 1
+    movq (%rdi), %r12           # pivot pointer = A[0]
+    movq (%r12, %rdx, 8), %r13  # value of pivot
 
 .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]
+    incq %rax
+    movq (%rdi, %rax, 8), %r12
+    movq (%r12, %rdx, 8), %r12  # value of arr[i]
 
-    cmpq %r11, %r12             # if arr[i] < pivot
+    cmpq %r13, %r12             # if arr[i] < pivot
     jl .hoare_Li
     
 # decrement j
 .hoare_Lj:
-    subq $1, %r9
+    decq %rbx
+    movq (%rdi, %rbx, 8), %r12  # r12 = arr[j]
+    movq (%r12, %rdx, 8), %r12  # value of arr[j]
 
-    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
+    cmpq %r13, %r12             # if arr[j] > pivot
     jg .hoare_Lj
 
     # check crossing
-    cmpq %r9, %r8               # if arr[i] > arr[j]
+    cmpq %rbx, %rax             # if i >= 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)
+    movq (%rdi, %rax, 8), %r12
+    movq (%rdi, %rbx, 8), %r14
+    movq %r14, (%rdi, %rax, 8)
+    movq %r12, (%rdi, %rbx, 8)
 
     jmp .hoare_loop
 
 .hoare_done:
-    popq %r11
+    movq %rbx, %rax              # return j as pivot
+    popq %r14
     popq %r13
     popq %r12
-    movq %r9, %rax
+    popq %rbx
     ret
-- 
cgit v1.2.3-70-g09d2