diff options
Diffstat (limited to 'algorithms/quick_sort.cc')
-rw-r--r-- | algorithms/quick_sort.cc | 58 |
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; +} + |