Implemented in-place quick sort.

2 files changed, 112 insertions, 0 deletions

diff --git a/quick-sort.cpp b/quick-sort.cpp
new file mode 100644
index 0000000..4e560a9
--- /dev/null
+++ b/quick-sort.cpp
@@ -0,0 +1,111 @@
+
+#include <cstdlib>
+#include <cstring>
+#include <iostream>
+#include <deque>
+
+using namespace std;
+
+typedef std::deque<int> list_t;
+
+size_t partition(list_t& lst, size_t left, size_t right, size_t pivot)
+{
+    list_t::value_type pivot_val = lst[pivot];
+    swap(lst[pivot], lst[right]); // move pivot to end.
+    size_t store_pos = left;
+    for (size_t i = left; i <= right-1; ++i)
+    {
+        if (lst[i] < pivot_val)
+        {
+            swap(lst[i], lst[store_pos]);
+            ++store_pos;
+        }
+    }
+    swap(lst[store_pos], lst[right]); // Move pivot to its final place.
+    return store_pos;
+}
+
+void quick_sort_run(list_t& lst, size_t left, size_t right)
+{
+    if (left >= right)
+        return;
+
+    if (right - left == 1)
+    {
+        // There is only 2 elements.
+        if (lst[left] > lst[right])
+            swap(lst[left], lst[right]);
+        return;
+    }
+
+    // There should be at least 3 elements in this segment.
+
+    size_t pivot = right - left == 2 ? left + 1 : (left+right) / 2;
+
+    pivot = partition(lst, left, right, pivot);
+
+    if (pivot == left)
+    {
+        quick_sort_run(lst, left, pivot);
+        quick_sort_run(lst, pivot+1, right);
+    }
+    else
+    {
+        quick_sort_run(lst, left, pivot-1);
+        quick_sort_run(lst, pivot+1, right);
+    }
+}
+
+void quick_sort(list_t& lst)
+{
+    size_t n = lst.size();
+    if (n <= 1)
+        // Nothing to do.
+        return;
+
+    quick_sort_run(lst, 0, n-1);
+}
+
+void print_list(const list_t& lst, const char* caption)
+{
+    cout << caption << ": ";
+    for (list_t::const_iterator i = lst.begin(), ie = lst.end(); i != ie; ++i)
+        cout << *i << " ";
+    cout << endl;
+}
+
+int main(int argc, char** argv)
+{
+    if (argc < 2)
+    {
+        cout << "needs at least one argument" << endl;
+        return EXIT_FAILURE;
+    }
+
+    const char* p = argv[1];
+    const char* pend = p + strlen(p);
+    char* endptr = NULL;
+    long list_size = strtol(p, &endptr, 10);
+    if (endptr != pend)
+    {
+        cout << "invalid number: " << p << endl;
+        return EXIT_FAILURE;
+    }
+
+    cout << "list size: " << list_size << endl;
+
+    list_t lst;
+    for (int i = 0; i < list_size; ++i)
+    {
+        double val = rand();
+        val /= RAND_MAX;
+        val *= 100;
+        lst.push_back(val);
+    }
+
+    print_list(lst, "original");
+    quick_sort(lst);
+    print_list(lst, "sorted");
+
+    return EXIT_SUCCESS;
+}
diff --git a/slickedit/algorithms.vpj b/slickedit/algorithms.vpj
index 4c86232..070ba10 100644
--- a/slickedit/algorithms.vpj
+++ b/slickedit/algorithms.vpj
@@ -131,6 +131,7 @@
 			Name="Source Files"
 			Filters="*.c;*.C;*.cc;*.cpp;*.cp;*.cxx;*.c++;*.prg;*.pas;*.dpr;*.asm;*.s;*.bas;*.java;*.cs;*.sc;*.e;*.cob;*.html;*.rc;*.tcl;*.py;*.pl;*.d">
 			<F N="../merge-sort.cpp"/>
+			<F N="../quick-sort.cpp"/>
 			<F N="../reverse-string.cpp"/>
 			<F N="../tree.cpp"/>
 			<F N="../unique-char.cpp"/>