Line | |
---|
1 | #include "sort.h" |
---|
2 | #include "system.h" |
---|
3 | #include "stdio.h" |
---|
4 | |
---|
5 | //------------------------------------------------------ |
---|
6 | /* |
---|
7 | * Exécute un tri par insertion avec la séparation donnée |
---|
8 | * If gap == 1, on fait un tri ordinaire. |
---|
9 | * If gap >= length, on ne fait rien. |
---|
10 | */ |
---|
11 | void sort_shell_phase(unsigned int a[],unsigned int length, int gap) { |
---|
12 | int i; |
---|
13 | |
---|
14 | /* puti(gap); */ |
---|
15 | for (i = gap; i < length; ++i) { |
---|
16 | unsigned int value = a[i]; |
---|
17 | int j; |
---|
18 | for (j = i - gap; j >= 0 && a[j] > value; j -= gap) { |
---|
19 | #if VERBOSE_SORT |
---|
20 | printf("+"); |
---|
21 | #endif |
---|
22 | a[j + gap] = a[j]; |
---|
23 | #if VERBOSE_SORT |
---|
24 | printf("-"); |
---|
25 | #endif |
---|
26 | } |
---|
27 | a[j + gap] = value; |
---|
28 | } |
---|
29 | } |
---|
30 | |
---|
31 | void sort_shell(unsigned int *base, unsigned int n) { |
---|
32 | /* |
---|
33 | * gaps[] doit approximer une Série géométrique. |
---|
34 | * La sequence suivante est la meilleure connue en terme |
---|
35 | * de nombre moyen de comparaisons. voir: |
---|
36 | * http://www.research.att.com/~njas/sequences/A102549 |
---|
37 | */ |
---|
38 | static const int gaps[] = { |
---|
39 | 1, 4, 10, 23, 57, 132, 301, 701 |
---|
40 | }; |
---|
41 | int sizeIndex; |
---|
42 | |
---|
43 | for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1; |
---|
44 | sizeIndex >= 0; |
---|
45 | --sizeIndex) |
---|
46 | sort_shell_phase(base, n, gaps[sizeIndex]); |
---|
47 | #if VERBOSE_SORT |
---|
48 | printf("\n"); |
---|
49 | #endif |
---|
50 | } |
---|
Note: See
TracBrowser
for help on using the repository browser.