From 0d2341999a9c844954aca9ed4cc739b8fde34584 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sun, 10 May 2020 18:57:13 +0200 Subject: chore: move algorithms file into self directory --- I_anno/Programmazione_2/algorithms/mergesort.cc | 52 +++++++++++++++++++++++++ I_anno/Programmazione_2/algorithms/quicksort.cc | 38 ++++++++++++++++++ 2 files changed, 90 insertions(+) create mode 100644 I_anno/Programmazione_2/algorithms/mergesort.cc create mode 100644 I_anno/Programmazione_2/algorithms/quicksort.cc (limited to 'I_anno/Programmazione_2/algorithms') diff --git a/I_anno/Programmazione_2/algorithms/mergesort.cc b/I_anno/Programmazione_2/algorithms/mergesort.cc new file mode 100644 index 0000000..68d28cb --- /dev/null +++ b/I_anno/Programmazione_2/algorithms/mergesort.cc @@ -0,0 +1,52 @@ +#include + +using namespace std; + +void merge(int A[], int l, int q, int r) { + int i = l; + int j = q+1; + int k = l; + int B[r]; + + while((i <= q) && (j <= r)) { + if(A[i] <= A[j]) + B[k] = A[i++]; + else + B[k] = A[j++]; + + k++; + } + + while(i <= q) + B[k++] = A[i++]; + + while(j <= r) + B[k++] = A[j++]; + + for(k = l; k <= r; ++k) + A[k] = B[k]; +} + +void mergesort(int A[], int l, int r) { + if(l < r) { + int q = (l+r)/2; + mergesort(A, l, q); + mergesort(A, q+1, r); + merge(A, l, q, 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; + mergesort(a, 0, 8); + for(int i = 0; i < 9; ++i) { + cout << a[i] << ' '; + } + + return 0; +} diff --git a/I_anno/Programmazione_2/algorithms/quicksort.cc b/I_anno/Programmazione_2/algorithms/quicksort.cc new file mode 100644 index 0000000..a646840 --- /dev/null +++ b/I_anno/Programmazione_2/algorithms/quicksort.cc @@ -0,0 +1,38 @@ +#include + +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, 9); + for(int i = 0; i < 9; ++i) { + cout << a[i] << ' '; + } + + return 0; +} -- cgit v1.2.3-18-g5258