From dc54a3392cd038e35dc9c24bdaa1644055b6813e Mon Sep 17 00:00:00 2001
From: Santo Cariotti <dcariotti24@gmail.com>
Date: Mon, 13 Jul 2020 18:03:50 +0200
Subject: feat: add algorithms

---
 .../Programmazione_2/algorithms/insertionsort.cc   | 42 ++++++++++++++++++++++
 1 file changed, 42 insertions(+)
 create mode 100644 I_anno/Programmazione_2/algorithms/insertionsort.cc

(limited to 'I_anno/Programmazione_2/algorithms/insertionsort.cc')

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;
+}
-- 
cgit v1.2.3-18-g5258