/***************************************************************************** * sort.c * * Implementation for sort algorithms. * * Qch, 2011-05 *****************************************************************************/ #include#include typedef int bool; #define true 1 #define false 0 void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } /** * Bubble sort algorithm. * "a" ----> array of Comparable items. * "left" ----> the left-most index of the subarray. * "right" ----> the right-most index of the subarray. */ void bubbleSort(int *a, int left, int right) { bool cond = true; int i,j; for (i = left; i < right; ++i) { cond = false; for (j = right; j > i; --j) if (a[j] < a[j - 1]) { swap(&a[j], &a[j - 1]); cond = true; } if (!cond) return; } } /** * Selection sort algorithm. * "a" ----> array of Comparable items. * "left" ----> the left-most index of the subarray. * "right" ----> the right-most index of the subarray. */ void selectSort(int *a, int left, int right) { int minPos; int i,j; for (i = left; i < right; ++i) { minPos = i; for (j = i + 1; j <= right; ++j) if (a[j] < a[minPos]) minPos = j; if (i != minPos) swap(&a[i], &a[minPos]); } } /** * Insertion sort algorithm. * "a" ----> array of Comparable items. * "left" ----> the left-most index of the subarray. * "right" ----> the right-most index of the subarray. */ void insertSort(int *a, int left, int right) { int p; for (p = left + 1; p <= right; p++) { int tmp = a[p]; int j; for (j = p; j > left && tmp < a[j - 1]; --j) a[j] = a[j - 1]; a[j] = tmp; } } /** * Internal quicksort method that makes recursive calls. * Uses median-of-three partitioning and a cutoff of 20. * "a" ----> array of Comparable items. * "left" ----> the left-most index of the subarray. * "right" ----> the right-most index of the subarray. */ int median3(int *a, int left, int right); void quickSort(int *a, int left, int right) { if (left + 20 <= right) { int pivot = median3(a, left, right); // begin partitioning int i = left, j = right - 1; for (;;) { while (a[++i] < pivot) { } while (pivot < a[--j]) { } if (i < j) swap(&a[i], &a[j]); else break; } // Restore pivot swap(&a[i], &a[right - 1]); // Sort small elements quickSort(a, left, i - 1); // Sort large elements quickSort(a, i + 1, right); } else insertSort(a, left, right); } /** * Return median of left, center, and right. * Order these and hide the pivot. */ int median3(int *a, int left, int right) { int center = (left + right) / 2; if (a[center] < a[left]) swap(&a[left], &a[center]); if (a[right] < a[left]) swap(&a[left], &a[right]); if (a[right] < a[center]) swap(&a[center], &a[right]); swap(&a[center], &a[right - 1]); return a[right - 1]; } /** * Merg sort algorithm (nonrecursion). * "a" ----> array of Comparable items. * "start" ----> the left-most index of the subarray. * "end" ----> the right-most index of the subarray. */ void merge(int *a,int start, int mid, int end); void mergSort(int *a,int start, int end) { int mid; if (start < end) { mid = (start + end) / 2; //printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\n", // start, mid, mid+1, end, // a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); mergSort(a,start, mid); mergSort(a,mid+1, end); merge(a,start, mid, end); //printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d %d %d\n", // start, mid, mid+1, end, // a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); } } /** * Merg two subsequence to a bigger one. * The first subsequence is a[start] ... a[mid-1], and * The second subsqeuence is a[mid] ... a[end]. */ void merge(int *a,int start, int mid, int end) { int n1 = mid - start + 1; int n2 = end - mid; //int left[n1], right[n2]; int *left=(int *)malloc(n1*sizeof(int)); int *right=(int *)malloc(n2*sizeof(int)); int i, j, k; for (i = 0; i < n1; i++) /* left holds a[start..mid] */ left[i] = a[start+i]; for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */ right[j] = a[mid+1+j]; i = 0; j = 0; k = start; while (i < n1 && j < n2) if (left[i] < right[j]) a[k++] = left[i++]; else a[k++] = right[j++]; while (i < n1) /* left[] is not exhausted */ a[k++] = left[i++]; while (j < n2) /* right[] is not exhausted */ a[k++] = right[j++]; free(left); free(right); } /** * Heap sort algorthm. * "a" ----> array of Comparable items. * "left" ----> the left-most index of the subarray. * "right" ----> the right-most index of the subarray. */ void filterDown(int *a, int i, int n); void heapSort(int *a, int left, int right) { int n = right - left + 1; //int tmp[n]; int *tmp=(int *)malloc(n*sizeof(int)); int i,j; for (i = 0; i < n; ++i) tmp[i] = a[left + i]; for (i = n / 2; i >= 0; --i) filterDown(tmp, i, n); for (j = n - 1; j > 0; --j) { swap(&tmp[0], &tmp[j]); filterDown(tmp, 0, j); } for (i = 0; i < n; ++i) a[left + i] = tmp[i]; free(tmp); } /** * Percolate down the heap. * "i" ----> the position from which to percolate down. * "n" ----> the logical size of the binary heap. */ void filterDown(int *a, int i, int n) { int child; int tmp; for (tmp = a[i]; 2 * i + 1 < n; i = child) { child = 2 * i + 1; if (child != n - 1 && a[child] < a[child + 1]) child++; if (tmp < a[child]) a[i] = a[child]; else break; } a[i] = tmp; } int main() { int d[] = { 7, 5, 6, 4, 2, 3, 1, 9, 8 }; int n,opt=0; for (n = 0; n < sizeof(d) / sizeof(int); n++) printf("%d", d[n]); printf("\n"); //int opt = 0; printf("1 bubbleSort\n"); printf("2 selectSort\n"); printf("3 insertSort\n"); printf("4 quickSort\n"); printf("5 mergSort\n"); printf("6 heapSort\n"); printf("option:"); scanf("%d",&opt); printf("\n"); switch (opt) { case 1: bubbleSort(d, 0, 9); break; case 2: selectSort(d, 0, 9); break; case 3: insertSort(d, 0, 9); break; case 4: quickSort(d, 0, 9); break; case 5: mergSort(d, 0, 9); break; case 6: heapSort(d, 0, 9); break; default: printf("input error!\n"); exit(1); } for (n = 0; n < sizeof(d) / sizeof(int); n++) printf("%d", d[n]); }