Quicksort.

laurentluce · laurentluce · commit ba47ae454f84 · 2015-11-30T11:08:41.000-05:00
diff --git a/README.md b/README.md
@@ -30,6 +30,8 @@ Generators
 Lists
   - Subset with highest sum.
   - Find integer in sorted list.
+  - Merge sort.
+  - Quicksort.
 
 ### Installation
 Get the source and run
diff --git a/algorithms/list.py b/algorithms/list.py
@@ -52,6 +52,8 @@ def find_max_sub(l):
 def merge_sort(l):
     """Sort list using merge sort.
 
+    Complexity: O(n log n)
+
     @param l list to sort.
     @returns sorted list.
     """
@@ -92,3 +94,29 @@ def merge(l1, l2):
     h2 = merge_sort(l[mid:])
 
     return merge(h1, h2)
+
+
+def quicksort(l):
+    """Sort list using quick sort.
+
+    Complexity: O(n log n).  Worst: O(n2)
+
+    @param l list to sort.
+    @returns sorted list.
+    """
+    if len(l) <= 1:
+        return l
+
+    pivot = l[0]
+    less = []
+    equal = []
+    greater = []
+    for e in l:
+        if e < pivot:
+            less.append(e)
+        elif e == pivot:
+            equal.append(e)
+        else:
+            greater.append(e)
+
+    return quicksort(less) + equal + quicksort(greater)
diff --git a/algorithms/tests/test_list.py b/algorithms/tests/test_list.py
@@ -45,5 +45,18 @@ def test_merge_sort_single_element(self):
         res = list.merge_sort([3])
         self.assertListEqual(res, [3])
 
+    def test_quicksort(self):
+        res = list.quicksort([3, 4, 1, 5, 0])
+        self.assertListEqual(res, [0, 1, 3, 4, 5])
+
+    def test_quicksort_duplicates(self):
+        res = list.quicksort([3, 4, 1, 5, 4, 0, 1])
+        self.assertListEqual(res, [0, 1, 1, 3, 4, 4, 5])
+
+    def test_quicksort_single_element(self):
+        res = list.quicksort([3])
+        self.assertListEqual(res, [3])
+
+
 if __name__ == '__main__':
     unittest.main()
