old stuff: algorithms

1 files changed, 58 insertions, 0 deletions

diff --git a/algorithms/quick_sort.cc b/algorithms/quick_sort.cc
new file mode 100644
index 0000000..88d9e01
--- /dev/null
+++ b/algorithms/quick_sort.cc
@@ -0,0 +1,58 @@
+#include <iostream>
+
+#define N 4
+
+using namespace std;
+
+
+void
+quickSort(int *A, int l, int r)
+{
+  int i,j,v,t;
+  /* trivial case */
+  if (r <= l) return;
+  /* chose pivot */
+  v = A[r];
+  i = l-1;
+  j = r;
+  /* identify parts */
+  do {
+    /* left.. */
+    do {i++;} while(A[i]<v);
+    /* right.. */
+      do {j--;} while (A[j]>v);
+        if (i<j) {
+          /* swap */
+          t = A[i];
+          A[i] = A[j];
+          A[j] = t;
+        }
+        else {
+          /* pivot at [i] */
+          t = A[i];
+          A[i] = A[r];
+          A[r] = t;
+        }
+    } while (i<j);
+    /* sort parts */
+    quickSort(A,l,i-1);
+    quickSort(A,i+1,r);
+}
+
+int
+main (int argc, char * const argv[]) {
+  int A[N] = {3,1,1,2};
+
+  for(unsigned int i=0; i<N; i++) {
+    cout << A[i];
+  }
+  cout << endl << "sortiert:" << endl;
+  quickSort(A, 0, N);
+  for(unsigned int i=0; i<N; i++) {
+    cout << A[i];
+  }
+  cout << endl;
+
+  return 0;
+}
+