feat: implement quick sort

3 files changed, 105 insertions, 4 deletions

diff --git a/src/03/sort.c b/src/03/sort.c
index e0eb9b6..c011733 100644
--- a/src/03/sort.c
+++ b/src/03/sort.c
@@ -1,7 +1,7 @@
 #include <stdio.h>
+#include <stdlib.h>
 
-void _merge(int *items, int min, int mid, int max)
-{
+void _merge(int *items, int min, int mid, int max) {
   int length = (max-min) + 1;
   int tmp[length];
   int j = min, k = mid;
@@ -23,8 +23,7 @@ void _merge(int *items, int min, int mid, int max)
     items[min+i] = tmp[i];
 }
 
-void _merge_sort(int *items, int min, int max)
-{
+void _merge_sort(int *items, int min, int max) {
   if (min >= max)
     return;
 
@@ -40,3 +39,39 @@ void merge_sort(int *items, int length) {
 
   _merge_sort(items, 0, length - 1);
 }
+
+int partition(int *items, int min, int max) {
+  int pivot = items[max];
+  int index = min - 1;
+  int tmp;
+
+  for (int j = min; j < max; j++) {
+    if (items[j] < pivot) {
+      index++;
+      tmp = items[index];
+      items[index] = items[j];
+      items[j] = tmp;
+    }
+  }
+  tmp = items[index+1];
+  items[index+1] = items[max];
+  items[max] = tmp;
+
+  return index + 1;
+}
+
+void _quick_sort(int *items, int min, int max) {
+  if (min >= max)
+    return;
+
+  int index = partition(items, min, max);
+  _quick_sort(items, min, index - 1);
+  _quick_sort(items, index + 1, max);
+}
+
+void quick_sort(int *items, int length) {
+  if (!items)
+    return;
+
+  _quick_sort(items, 0, length - 1);
+}
diff --git a/src/03/sort.h b/src/03/sort.h
index 4226490..5c0012f 100644
--- a/src/03/sort.h
+++ b/src/03/sort.h
@@ -1 +1,2 @@
 void merge_sort(int *items, int length);
+void quick_sort(int *items, int length);
diff --git a/src/03/sort_test.c b/src/03/sort_test.c
index 8c01b04..fabb4ee 100644
--- a/src/03/sort_test.c
+++ b/src/03/sort_test.c
@@ -64,6 +64,64 @@ Ensure(merge_sort_sorts_many_items) {
   assert_that(items[10], is_equal_to(9));
 }
 
+Ensure(quick_sort_sorts_a_null_list) {
+  quick_sort(NULL, 0);
+}
+
+Ensure(quick_sort_sorts_an_empty_list) {
+  int items[] = {};
+
+  quick_sort(items, 0);
+
+  assert_that(sizeof(items), is_equal_to(0));
+}
+
+Ensure(quick_sort_sorts_a_list_with_one_item) {
+  int items[] = {100};
+
+  quick_sort(items, 1);
+
+  assert_that(items[0], is_equal_to(100));
+}
+
+Ensure(quick_sort_sorts_a_list_with_two_items) {
+  int items[] = {100, 10};
+
+  quick_sort(items, 2);
+
+  assert_that(items[0], is_equal_to(10));
+  assert_that(items[1], is_equal_to(100));
+}
+
+Ensure(quick_sort_sorts_three_unique_items) {
+  int items[] = { 3, 1, 4 };
+
+  quick_sort(items, sizeof(items) / sizeof(int));
+
+  assert_that(items[0], is_equal_to(1));
+  assert_that(items[1], is_equal_to(3));
+  assert_that(items[2], is_equal_to(4));
+}
+
+Ensure(quick_sort_sorts_many_items) {
+  int items[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
+
+  quick_sort(items, sizeof(items) / sizeof(int));
+
+  assert_that(items[0], is_equal_to(1));
+  assert_that(items[1], is_equal_to(1));
+  assert_that(items[2], is_equal_to(2));
+  assert_that(items[3], is_equal_to(3));
+  assert_that(items[4], is_equal_to(3));
+  assert_that(items[5], is_equal_to(4));
+  assert_that(items[6], is_equal_to(5));
+  assert_that(items[7], is_equal_to(5));
+  assert_that(items[8], is_equal_to(5));
+  assert_that(items[9], is_equal_to(6));
+  assert_that(items[10], is_equal_to(9));
+}
+
+
 TestSuite *sort_tests() {
   TestSuite *x = create_test_suite();
   add_test(x, one_equals_one);
@@ -74,5 +132,12 @@ TestSuite *sort_tests() {
   add_test(x, merge_sort_sorts_a_list_with_two_items);
   add_test(x, merge_sort_sorts_three_unique_items);
   add_test(x, merge_sort_sorts_many_items);
+
+  add_test(x, quick_sort_sorts_a_null_list);
+  add_test(x, quick_sort_sorts_an_empty_list);
+  add_test(x, quick_sort_sorts_a_list_with_one_item);
+  add_test(x, quick_sort_sorts_a_list_with_two_items);
+  add_test(x, quick_sort_sorts_three_unique_items);
+  add_test(x, quick_sort_sorts_many_items);
   return x;
 }