sort.c (1465B)
1 #include <math.h> 2 3 void 4 bubble_sort(unsigned int n, int a[n]) 5 { 6 int tmp; 7 for (unsigned int i = 0; i < n - 1; ++i) { 8 int swapped = 0; 9 unsigned int limit = n - i - 1; 10 for (unsigned int j = 0; j < limit; ++j) { 11 if (a[j] > a[j+1]) { 12 tmp = a[j]; 13 a[j] = a[j+1]; 14 a[j+1] = tmp; 15 swapped = 1; 16 } 17 } 18 if (!swapped) 19 break; 20 } 21 } 22 23 void 24 choice_sort(unsigned int n, int a[n]) /* it's actually selection_sort :nerd: */ 25 { 26 int tmp; 27 for (unsigned int i = 0; i < n - 1; ++i) { 28 unsigned int min = i; 29 for (unsigned int j = i + 1; j < n; ++j) { 30 if (a[j] < a[min]) 31 min = j; 32 } 33 if (min != i) { 34 tmp = a[i]; 35 a[i] = a[min]; 36 a[min] = tmp; 37 } 38 } 39 } 40 41 void 42 insert_sort(unsigned int n, int a[n]) 43 { 44 int key; 45 for (unsigned int i = 1; i < n; ++i) { 46 key = a[i]; 47 long j = i - 1; /* j has to be signed - use long */ 48 for (; j >= 0 && a[j] > key; --j) 49 a[j+1] = a[j]; 50 a[j+1] = key; 51 } 52 } 53 54 void 55 shell_sort(unsigned int n, int a[n]) 56 { 57 unsigned int gaps[32]; 58 unsigned int count = 0; /* Tokuda gaps */ 59 for (unsigned int k = 1;; ++k) { 60 double hk = ceil((pow(9.0,k)-pow(4.0,k))/(5.0*pow(4.0,k-1))); 61 if (hk >= n) 62 break; 63 gaps[count++] = (unsigned int)hk; 64 } 65 66 int tmp; 67 for (int gi = count - 1; gi >= 0; --gi) { 68 unsigned int gap = gaps[gi]; 69 for (unsigned int i = gap; i < n; ++i) { 70 tmp = a[i]; 71 unsigned int j = i; 72 for (; j >= gap && a[j-gap] > tmp; j -= gap) 73 a[j] = a[j-gap]; 74 a[j] = tmp; 75 } 76 } 77 }