summaryrefslogtreecommitdiff
path: root/I_anno/Programmazione_2/algorithms/insertionsort.cc
blob: 9b309d6191389e9fc5b0e44ac66dc816bf859412 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
}