[3] | 1 | #include "system.h" |
---|
| 2 | #include "stdio.h" |
---|
| 3 | #include "stdlib.h" |
---|
[85] | 4 | //#include "matrice.h" |
---|
[3] | 5 | |
---|
| 6 | #include "../segmentation.h" |
---|
| 7 | |
---|
| 8 | #define NPROCS 4 |
---|
[85] | 9 | #define SIZE 50 |
---|
[3] | 10 | #define SORT_TYPE 0 // shellSort |
---|
| 11 | |
---|
| 12 | volatile int nprocs=NPROCS; |
---|
| 13 | |
---|
[85] | 14 | |
---|
[3] | 15 | unsigned int gQSortNum0[200] = { |
---|
| 16 | 251, 24, 113, 170, 215, 60, 83, 30, 115, 48, 169, 210, 49, 92, 101, 58, 21, 184, 225, 6, |
---|
| 17 | 199, 244, 227, 146, 99, 96, 25, 222, 65, 140, 213, 22, 219, 136, 175, 182, 73, 36, 141, 190, |
---|
| 18 | 83, 112, 137, 114, 175, 188, 187, 102, 53, 168, 193, 154, 167, 172, 3, 242, 67, 64, 144, 137, |
---|
| 19 | 142, 175, 188, 69, 102, 53, 168, 193, 102, 89, 172, 253, 242, 67, 192, 7, 62, 159, 20, 181, |
---|
| 20 | 182, 187, 216, 207, 22, 105, 132, 109, 162, 205, 16, 151, 18, 113, 228, 37, 6, 85, 8, 161, |
---|
| 21 | 58, 135, 76, 35, 174, 35, 224, 39, 158, 127, 180, 149, 86, 155, 200, 239, 118, 119, 28, 77, |
---|
| 22 | 254, 19, 176, 183, 78, 145, 132, 5, 90, 117, 152, 127, 218, 153, 20, 67, 178, 3, 128, 185, |
---|
| 23 | 254, 95, 172, 139, 246, 123, 104, 15, 42, 169, 68, 211, 98, 243, 80, 41, 174, 79, 36, 27, |
---|
| 24 | 186, 149, 86, 155, 200, 239, 118, 119, 28, 77, 254, 19, 176, 183, 78, 145, 132, 5, 90, 117, |
---|
| 25 | 152, 127, 218, 153, 20, 67, 178, 3, 128, 185, 254, 95, 172, 139, 246, 123, 104, 15, 42, 169 }; |
---|
| 26 | |
---|
| 27 | |
---|
[85] | 28 | unsigned int SortArr0[NPROCS*(SIZE+50)]; |
---|
| 29 | |
---|
[3] | 30 | void shellSortPhase(unsigned int a[],unsigned int length, int gap); |
---|
| 31 | void shellSort(unsigned int *base, unsigned int n); // type 0 |
---|
| 32 | |
---|
| 33 | int main() |
---|
| 34 | { |
---|
| 35 | register int p; |
---|
| 36 | |
---|
| 37 | p=procnum(); |
---|
| 38 | |
---|
| 39 | puts("Hello from processor "); |
---|
| 40 | putchar(p+'0'); |
---|
| 41 | putchar('\n'); |
---|
| 42 | |
---|
| 43 | int i; |
---|
| 44 | int j; |
---|
| 45 | unsigned int* SortArray; |
---|
| 46 | |
---|
| 47 | if(p+1 <= nprocs) |
---|
| 48 | { |
---|
| 49 | i=1; |
---|
| 50 | puts("Memory copy \n"); |
---|
[85] | 51 | SortArray = SortArr0 + p*(SIZE+50); |
---|
| 52 | // memcpy(SortArray, gQSortNum0 + p*SIZE,SIZE*4); |
---|
| 53 | memcpy(SortArray, gQSortNum0,SIZE*4); |
---|
[3] | 54 | |
---|
| 55 | puts("Sort... \n"); |
---|
[85] | 56 | shellSort((unsigned int *) (SortArray), (unsigned int) SIZE); |
---|
[3] | 57 | |
---|
| 58 | for (j = 1; j < SIZE; j++) |
---|
| 59 | { |
---|
| 60 | if (SortArray[j] < SortArray[j-1]) |
---|
| 61 | { |
---|
| 62 | puts("ucbqsort: failed\n"); |
---|
| 63 | while(1); |
---|
| 64 | } |
---|
| 65 | |
---|
| 66 | } |
---|
| 67 | |
---|
| 68 | puts("ucbqsort: success\n"); |
---|
| 69 | } |
---|
| 70 | |
---|
| 71 | while(1); |
---|
| 72 | } |
---|
| 73 | |
---|
| 74 | //------------------------------------------------------ |
---|
| 75 | /* |
---|
| 76 | * Exécute un tri par insertion avec la séparation donnée |
---|
| 77 | * If gap == 1, on fait un tri ordinaire. |
---|
| 78 | * If gap >= length, on ne fait rien. |
---|
| 79 | */ |
---|
| 80 | void shellSortPhase(unsigned int a[],unsigned int length, int gap) { |
---|
| 81 | int i; |
---|
| 82 | |
---|
| 83 | puti(gap); |
---|
| 84 | for (i = gap; i < length; ++i) { |
---|
| 85 | unsigned int value = a[i]; |
---|
| 86 | int j; |
---|
| 87 | for (j = i - gap; j >= 0 && a[j] > value; j -= gap) { |
---|
| 88 | putchar('+'); |
---|
| 89 | a[j + gap] = a[j]; |
---|
| 90 | putchar('-'); |
---|
| 91 | } |
---|
| 92 | a[j + gap] = value; |
---|
| 93 | } |
---|
| 94 | } |
---|
| 95 | |
---|
| 96 | void shellSort(unsigned int *base, unsigned int n) { |
---|
| 97 | /* |
---|
| 98 | * gaps[] doit approximer une Série géométrique. |
---|
| 99 | * La sequence suivante est la meilleure connue en terme |
---|
| 100 | * de nombre moyen de comparaisons. voir: |
---|
| 101 | * http://www.research.att.com/~njas/sequences/A102549 |
---|
| 102 | */ |
---|
| 103 | static const int gaps[] = { |
---|
| 104 | 1, 4, 10, 23, 57, 132, 301, 701 |
---|
| 105 | }; |
---|
| 106 | int sizeIndex; |
---|
| 107 | |
---|
| 108 | puts("Shell Sort\n"); |
---|
| 109 | for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1; |
---|
| 110 | sizeIndex >= 0; |
---|
| 111 | --sizeIndex) |
---|
| 112 | shellSortPhase(base, n, gaps[sizeIndex]); |
---|
| 113 | } |
---|
| 114 | |
---|