summaryrefslogtreecommitdiff
path: root/I_anno/Programmazione_2
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2020-07-13 18:03:50 +0200
committerSanto Cariotti <dcariotti24@gmail.com>2020-07-14 15:07:21 +0200
commitdc54a3392cd038e35dc9c24bdaa1644055b6813e (patch)
tree0895f9e70f37d431c1bbba7ee37b602104e2df23 /I_anno/Programmazione_2
parent5c89ba385cca47ffd34b402e102f279f73f82cb5 (diff)
feat: add algorithms
Diffstat (limited to 'I_anno/Programmazione_2')
-rw-r--r--I_anno/Programmazione_2/algorithms/insertionsort.cc42
-rw-r--r--I_anno/Programmazione_2/algorithms/selectionsort.cc46
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;
+}