Last change
on this file since 338 was
134,
checked in by kane, 14 years ago
|
add multi write buffer in cc_xcache_v4
|
File size:
1.3 KB
|
Rev | Line | |
---|
[134] | 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.