sort.cpp

chronolaw · chronolaw · commit fe0aac012876 · 2020-08-05T09:42:20.000+08:00
diff --git a/section0/sort.cpp b/section0/sort.cpp
@@ -6,23 +6,56 @@
 
 #include <iostream>
 #include <algorithm>
+#include <functional>
 #include <vector>
 
 using namespace std;
 
+template<typename T>
+void quick_sort_impl(T& v, int left, int right)
+{
+    auto quick_partition = [](decltype(v)& arr, int left, int right)
+    {
+        int key = arr[right];
+        int i = left - 1;
+        int j = left;
+
+        for (; j < right; j++)
+        {
+            if (arr[j] < key)
+            {
+                std::swap(arr[j], arr[++i]);
+            }
+        }
+
+        std::swap(arr[right], arr[++i]);
+
+        return i;
+    };
+
+    if (left > right)
+    {
+        return;
+    }
+
+    int mid = quick_partition(v, left, right);
+
+    quick_sort_impl(v, left, mid - 1);
+    quick_sort_impl(v, mid + 1, right);
+}
+
 int main()
 {
     std::vector<int> v = {42,9,4,2,5,10,1,0};
+    int len = v.size();
 
     // -----------------------------
 
     auto bubble_sort = [=]() mutable
     {
-        int len = v.size();
-
         for(int i = 0;i < len - 1; i++)
         {
-            for(int j = 0; j < len - i - 1; j ++)
+            for(int j = 0; j < len - i - 1; j++)
             {
                 if (v[j] > v[j + 1])
                 {
@@ -45,8 +78,6 @@ int main()
 
     auto select_sort = [=]() mutable
     {
-        int len = v.size();
-
         for (int i = 0; i < len - 1; i++)
         {
             int min = i;
@@ -75,8 +106,6 @@ int main()
 
     auto insert_sort = [=]() mutable
     {
-        int len = v.size();
-
         int i, j;
         for(i = 0;i < len; i++)
         {
@@ -98,4 +127,20 @@ int main()
     };
 
     insert_sort();
+
+    // -----------------------------
+
+    auto quick_sort = [=]() mutable
+    {
+        quick_sort_impl(v, 0, len - 1);
+
+        for(auto& x : v)
+        {
+            cout << x << ',';
+        }
+
+        cout << endl;
+    };
+
+    quick_sort();
 }
