diff options
author | Santo Cariotti <santo@dcariotti.me> | 2021-02-06 19:56:36 +0100 |
---|---|---|
committer | Santo Cariotti <santo@dcariotti.me> | 2021-02-06 19:56:36 +0100 |
commit | d2edbc38cac8da52f58c5cd3da6c0c625fa05736 (patch) | |
tree | a51e9a4e56fc9d4c7c9e37576dceedca3a0c72b4 /Year_1/Programming_2/algorithms/quicksort.cc | |
parent | 98f34040820dc3a964b7be59a698323e8cc6c8a3 (diff) |
conf: rename
Diffstat (limited to 'Year_1/Programming_2/algorithms/quicksort.cc')
-rw-r--r-- | Year_1/Programming_2/algorithms/quicksort.cc | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/Year_1/Programming_2/algorithms/quicksort.cc b/Year_1/Programming_2/algorithms/quicksort.cc new file mode 100644 index 0000000..795bd7b --- /dev/null +++ b/Year_1/Programming_2/algorithms/quicksort.cc @@ -0,0 +1,38 @@ +#include<iostream> + +using namespace std; + +int partition(int A[], int l, int r) { + int x = A[r]; + int i = l-1; + + for(int j = l; j < r; ++j) { + if(A[j] <= x) { + swap(A[++i], A[j]); + } + } + swap(A[++i], A[r]); + return i; +} + +void quicksort(int A[], int l, int r) { + if(l < r) { + int q = partition(A, l, r); + quicksort(A, l, q-1); + quicksort(A, q+1, r); + } +} + +int main() { + int a[] = {7,1,22,3,2,12,27,31,6}; + for(int i = 0; i < 9; ++i) { + cout << a[i] << ' '; + } + cout << endl; + quicksort(a, 0, 8); + for(int i = 0; i < 9; ++i) { + cout << a[i] << ' '; + } + + return 0; +} |