From 600fa18324c21a162c50c40ae5f00c899a41dd24 Mon Sep 17 00:00:00 2001
From: dhuth <derickhuth@gmail.com>
Date: Wed, 17 Sep 2014 18:09:29 -0600
Subject: removed submodule, added test-chill
---
test-chill/unit-tests/cprog/QuickSorter.cc | 83 ++++++++++++++++++++++++++++++
1 file changed, 83 insertions(+)
create mode 100644 test-chill/unit-tests/cprog/QuickSorter.cc
(limited to 'test-chill/unit-tests/cprog/QuickSorter.cc')
diff --git a/test-chill/unit-tests/cprog/QuickSorter.cc b/test-chill/unit-tests/cprog/QuickSorter.cc
new file mode 100644
index 0000000..3ade346
--- /dev/null
+++ b/test-chill/unit-tests/cprog/QuickSorter.cc
@@ -0,0 +1,83 @@
+#include "QuickSorter.h"
+
+/* Python
+
+def swap(l, i, k):
+ v = l[i]
+ l[i] = l[k]
+ l[k] = v
+ print(str(l))
+
+def partition(l, start, end):
+ print("PARTITION {} [{}:{}]".format(l, start, end))
+ p_value = l[end]
+ p_index = end-1
+
+ for i in range(start, end):
+ while(i < p_index and l[i] >= p_value):
+ swap(l, i, p_index)
+ p_index -= 1
+ while(i >= p_index and l[i] < p_value):
+ swap(l, i, p_index)
+ p_index += 1
+ swap(l, p_index, end)
+ print("DONE {}|[{}]|{}:{}".format(l[start:p_index], l[p_index], l[p_index+1:end+1], p_value))
+ return p_index
+
+def qsort(l, i, k):
+ if i < k:
+ p = partition(l, i, k)
+ qsort(l,i,p-1)
+ qsort(l,p+1,k)
+
+if __name__ == "__main__":
+ import random as r
+ x = [int(r.random()*12) for i in range(12)]
+ print(x)
+ qsort(x, 0, len(x)-1)
+ print(x)
+
+*/
+
+static void swap(std::vector<int>& list, int i, int k) {
+ int v = list[i];
+ list[i] = list[k];
+ list[k] = v;
+}
+
+static int partition(std::vector<int>& list, int i, int k) {
+ int pivot_value = list[k];
+ int pivot_index = k - 1;
+
+ for(int index = i; index < k; index++) {
+ while((index < pivot_index) && (list[index] >= pivot_value)) {
+ swap(list, index, pivot_index);
+ pivot_index--;
+ }
+ while((index >= pivot_index) && (list[index] < pivot_value)) {
+ swap(list, index, pivot_index);
+ pivot_index++;
+ }
+ }
+ swap(list, pivot_index, k);
+ return pivot_index;
+}
+
+static void quicksort(std::vector<int>& list, int i, int k) {
+ if(i < k) {
+ int p = partition(list, i, k);
+ quicksort(list, i, p-1);
+ quicksort(list, p+1, k);
+ }
+}
+
+QuickSorter::QuickSorter() {
+ this->name = std::string("quicksort");
+}
+
+QuickSorter::~QuickSorter() {
+}
+
+void QuickSorter::sort(std::vector<int>& list) const {
+ quicksort(list, 0, list.size()-1);
+}
--
cgit v1.2.3-70-g09d2