/* sorting.c Implementations of primary sorting algorithms by: Steven Skiena begun: February 5, 2002 */ /* Copyright 2003 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. This program appears in my book: "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information. This book can be ordered from Amazon.com at http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #include "bool.h" #include #include #include "priority_queue.h" #include "queue.h" #define NELEM 100 /* size of test arrays */ #define LESS_THAN -1 #define EQUAL_TO 0 #define GREATER_THAN 1 bool compare(item_type a, item_type b) { if (a < b) return(LESS_THAN); if (a > b) return(GREATER_THAN); return(EQUAL_TO); } /* Swap the ith and jth elements of array s. */ newswap(item_type s[], int i, int j) { item_type tmp; /* placeholder */ tmp = s[i]; s[i] = s[j]; s[j] = tmp; } insertion_sort(item_type s[], int n) { int i,j; /* counters */ for (i=1; i0) && (s[j] < s[j-1])) { swap(&s[j],&s[j-1]); j = j-1; } } } selection_sort(item_type s[], int n) { int i,j; /* counters */ int min; /* index of minimum */ for (i=0; i0) { p = partition(s,l,h); quicksort(s,l,p-1); quicksort(s,p+1,h); } } int partition(item_type s[], int l, int h) { int i; /* counter */ int p; /* pivot element index */ int firsthigh; /* divider position for pivot element */ p = h; firsthigh = l; for (i=l; i high) return (-1); /* key not found */ middle = (low+high)/2; if (s[middle] == key) return(middle); if (s[middle] > key) return( binary_search(s,key,low,middle-1) ); else return(binary_search(s,key,middle+1,high) ); } mergesort(item_type s[], int low, int high) { int i; /* counter */ int middle; /* index of middle element */ if (low < high) { middle = (low+high)/2; mergesort(s,low,middle); mergesort(s,middle+1,high); merge(s, low, middle, high); } } merge(item_type s[], int low, int middle, int high) { int i; /* counter */ queue buffer1, buffer2; /* buffers to hold elements for merging */ init_queue(&buffer1); init_queue(&buffer2); for (i=low; i<=middle; i++) enqueue(&buffer1,s[i]); for (i=middle+1; i<=high; i++) enqueue(&buffer2,s[i]); i = low; while (!(empty_queue(&buffer1) || empty_queue(&buffer2))) { if (headq(&buffer1) <= headq(&buffer2)) s[i++] = dequeue(&buffer1); else s[i++] = dequeue(&buffer2); } while (!empty_queue(&buffer1)) s[i++] = dequeue(&buffer1); while (!empty_queue(&buffer2)) s[i++] = dequeue(&buffer2); } main() { int s[NELEM+2]; int n; int i,j; /* counters */ for (i=0; i