feat: complete some practice questionsHEADmaster

1 files changed, 31 insertions, 0 deletions

diff --git a/src/final/sort.rb b/src/final/sort.rb
new file mode 100644
index 0000000..7d299cf
--- /dev/null
+++ b/src/final/sort.rb
@@ -0,0 +1,31 @@
+def partition(items, lo, hi)
+  pos = ((hi-lo)/2) + lo
+  pivot = items[pos]
+  i = lo
+  items[hi], items[pos] = items[pos], items[hi]
+  for j in lo..hi
+    puts [items[j], pivot].inspect
+    if items[j] < pivot
+      items[i], items[j] = items[j], items[i]
+      i+=1
+    end
+    puts [pivot, items].inspect
+  end
+  items[i], items[hi] = items[hi], items[i]
+  puts [pivot, items].inspect
+  i
+end
+
+def quicksort(items, lo, hi)
+  if lo < hi
+    p = partition(items, lo, hi)
+    quicksort(items, lo, p - 1)
+    quicksort(items, p + 1, hi)
+  end
+end
+
+puts "Sorting"
+puts [6, 8, 4, 5, 3, 1, 7].inspect
+
+puts "quick sort"
+quicksort([6, 8, 4, 5, 3, 1, 7], 0, 6)