Quicksort in Python.

jwasham · jwasham · commit c5d765d1a8be · 2016-07-20T21:44:14.000-07:00
diff --git a/quick_sort/main.py b/quick_sort/main.py
@@ -0,0 +1,52 @@
+from quick_sort import QuickSort
+
+
+def is_sorted(numbers):
+    last_num = float("-inf")
+
+    for num in numbers:
+        if num < last_num:
+            return False
+        else:
+            last_num = num
+
+    return True
+
+
+def contain_same_ints(arr1, arr2):
+    for i in arr1:
+        found = False
+        for j in arr2:
+            if i == j:
+                found = True
+        if not found:
+            return False
+
+    return True
+
+def main():
+    original = [325432, 989, 547510, 3, -93, 189019, 5042, 123,
+                597, 42, 7506, 184, 184, 2409, 45, 824,
+                4, -2650, 9, 662, 3928, -170, 45358, 395,
+                842, 7697, 110, 14, 99, 221]
+
+    numbers = original[:]
+
+    qs = QuickSort(numbers)
+    output = qs.sort()
+
+    if is_sorted(output):
+        print("** SUCCESS! **")
+    else:
+        print("Uh oh - not in order.")
+
+    if contain_same_ints(original, numbers):
+        print("** Contain the same elements! **")
+    else:
+        print("Uh oh - something is missing.")
+
+    print(output)
+
+
+if __name__ == "__main__":
+    main()
diff --git a/quick_sort/quick_sort.py b/quick_sort/quick_sort.py
@@ -0,0 +1,41 @@
+import random
+
+
+class QuickSort(object):
+
+    def __init__(self, numbers):
+        self.values = numbers
+        self.count = len(self.values)
+
+    def sort(self):
+        self.quick_sort(0, self.count - 1)
+        return self.values
+
+    def quick_sort(self, left, right):
+        if left == right:
+            return
+
+        i = left
+        j = right
+
+        pivot_index = random.randint(left, right)
+
+        pivot = self.values[pivot_index]
+
+        while i <= j:
+            while self.values[i] < pivot:
+                i += 1
+            while self.values[j] > pivot:
+                j -= 1
+            if i <= j:
+                if i < j:
+                    temp = self.values[i]
+                    self.values[i] = self.values[j]
+                    self.values[j] = temp
+                i += 1
+                j -= 1
+
+        if left < j:
+            self.quick_sort(left, j)
+        if right > i:
+            self.quick_sort(i, right)
