diff options
author | Santo Cariotti <dcariotti24@gmail.com> | 2020-07-13 18:03:50 +0200 |
---|---|---|
committer | Santo Cariotti <dcariotti24@gmail.com> | 2020-07-14 15:07:21 +0200 |
commit | dc54a3392cd038e35dc9c24bdaa1644055b6813e (patch) | |
tree | 0895f9e70f37d431c1bbba7ee37b602104e2df23 /I_anno/Programmazione_2 | |
parent | 5c89ba385cca47ffd34b402e102f279f73f82cb5 (diff) |
feat: add algorithms
Diffstat (limited to 'I_anno/Programmazione_2')
-rw-r--r-- | I_anno/Programmazione_2/algorithms/insertionsort.cc | 42 | ||||
-rw-r--r-- | I_anno/Programmazione_2/algorithms/selectionsort.cc | 46 |
2 files changed, 88 insertions, 0 deletions
diff --git a/I_anno/Programmazione_2/algorithms/insertionsort.cc b/I_anno/Programmazione_2/algorithms/insertionsort.cc new file mode 100644 index 0000000..9b309d6 --- /dev/null +++ b/I_anno/Programmazione_2/algorithms/insertionsort.cc @@ -0,0 +1,42 @@ +#include<iostream> + +using namespace std; + +void insertionsort(int a[], int n) { + for(int i = 1; i < n; ++i) { + int j = i-1; + int key = a[i]; + while(j > -1 && a[j] > key) { + swap(a[j+1], a[j]); + --j; + } + a[j+1] = key; + } +} + +void insertionsort_rec(int a[], int n) { + if(n < 2) return; + insertionsort_rec(a, n-1); + + int key = a[n-1]; + int j = n-2; + + while(j > -1 && a[j] > key) { + swap(a[j+1], a[j]); + --j; + } + + a[j+1] = key; + +} + +int main() { + int arr[10] = {3, 450, 12, 4, -1, 0, 24, 95, 123, 0}; + for(int i = 0; i < 10; ++i) + cout << *(arr+i) << ' '; + cout << endl; + insertionsort_rec(arr, 10); + for(int i = 0; i < 10; ++i) + cout << *(arr+i) << ' '; + return 0; +} diff --git a/I_anno/Programmazione_2/algorithms/selectionsort.cc b/I_anno/Programmazione_2/algorithms/selectionsort.cc new file mode 100644 index 0000000..57dcc17 --- /dev/null +++ b/I_anno/Programmazione_2/algorithms/selectionsort.cc @@ -0,0 +1,46 @@ +#include<iostream> +#include<algorithm> + +using namespace std; + +void selectionsort(int a[], int n) { + for(int i = 0; i < n-1; ++i) { + int min = i; + for(int j = i+1; j < n; ++j) { + if(a[j] < a[min]) + min = j; + } + + swap(a[min], a[i]); + } +} + +int min_i(int a[], int i, int j) { + if(i == j) return i; + + int k = min_i(a, i+1, j); + return (a[i] < a[k]) ? i : k; +} + +void selectionsort_rec(int* a, int b, int e=0) { + if(b == e) return; + + int key = min_i(a, e, b-1); + if(key != e) + swap(a[key], a[e]); + + selectionsort_rec(a, b, e+1); +} + +int main() { + int arr[] = {3,450,12,4,-1,0,24,95,123,0}; + for(int i = 0; i < 10; ++i) { + cout << *(arr+i) << ' '; + } + cout << endl; + selectionsort_rec(arr, 10); + for(int i = 0; i < 10; ++i) { + cout << *(arr+i) << ' '; + } + return 0; +} |