blob: d484f1151b362f71e695a3b30529d612684f17b6 (
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
|
#include "main.h"
#include "insertion.h"
/*
* dit algoritme heeft een for-lus in een for-lus, waarbij het aantal iteraties
* van beide for-lussen recht evenredig is met de grootte van de invoer-array.
* het aantal iteraties van de binneste lus is afhankelijk van de grootte van
* de 'sub'-array, die met 1 groeit per iteratie van de buitenste for-lus.
* hierdoor zou een 'exactere' manier om het aantal stappen te beschrijven
* O(0.5 * n^2) zijn, maar omdat constante factoren geen invloed hebben over de
* big-O notatie wordt dit vereenvoudigd tot O(n^2).
*/
void insertion_sort(int* arr, unsigned size) {
int tail, inner, temp;
for (tail = size - 2; tail >= 0; tail--) {
temp = arr[tail];
for (inner = tail + 1; inner < size; inner++) {
if (arr[inner] > temp) break;
arr[inner - 1] = arr[inner];
}
arr[inner - 1] = temp;
printf("outer: ");
print_arr(arr, size);
}
}
|