quicksort.c (1903B)
1 /* Exercise 7.24 */ 2 3 #include <stdio.h> 4 5 void quicksort(int array[], int sidx, int eidx); 6 int partition(int array[], int num, int size); 7 void iswap(int *a, int *b); 8 void i_pa(int a[], int size); 9 10 int main(void) 11 { 12 int a[] = { 13 8, 2, 25, 15, 31, 78, 23, 69, 19, 10, 41, 1, 1, 1, 14 33, 58, 9, 15, 19, 8, 100, 28, 12, 5, 234, 734, 9, 15 23, 12312, 21, 1231, 2123, 21321, 12, 123, 3, 432, 16 2, 354, 34, 2, 3, 4, 423, 34, 685, 65, 4, 22, 521 17 }; 18 19 int size = ( sizeof(a) / sizeof(int) ); 20 21 printf("The array before the order:\t"); 22 i_pa(a, size); 23 24 quicksort(a, 0, size - 1); 25 26 printf("\nThe array after the order:\t"); 27 i_pa(a, size); 28 29 return 0; 30 } /* E0F main */ 31 32 /* Sort an array using the quicksort algorithm */ 33 void quicksort(int array[], int sidx, int eidx) 34 { 35 int newidx; 36 37 if(sidx == eidx) 38 return; 39 40 newidx = partition(array, sidx, eidx); 41 42 if(newidx == sidx) { 43 quicksort(array, newidx + 1, eidx); 44 } 45 else if(newidx == eidx) { 46 quicksort(array, sidx, newidx - 1); 47 } 48 else { 49 quicksort(array, newidx + 1, eidx); 50 quicksort(array, sidx, newidx - 1); 51 } 52 53 } /* eof quicksort() */ 54 55 /* Partition a number to an array */ 56 int partition(int a[], int num, int size) 57 { 58 int l = 0, r = size; 59 60 while(1) { 61 62 for( ; r > num; r--) { 63 if(a[r] < a[num]) { 64 iswap(&a[r], &a[num]); 65 num = r; 66 break; 67 } 68 } 69 70 for(; l < num; l++) { 71 if(a[l] > a[num]) { 72 iswap(&a[l], &a[num]); 73 num = l; 74 break; 75 } 76 } 77 78 if(l == r) 79 break; 80 81 } 82 83 return num; 84 85 } 86 87 /* Swap two element */ 88 void iswap(int *a, int *b) 89 { 90 int hold = *a; 91 *a = *b; 92 *b = hold; 93 } /* eof iswap() */ 94 95 void i_pa(int a[], int size) 96 { 97 int i; 98 99 printf("\n"); 100 101 for(i = 1; i <= size; i++) { 102 printf("%6d ", a[i - 1]); 103 104 if( !(i % 10) ) 105 printf("\n"); 106 } 107 108 } /* end i_pa() */ 109