// see sortall.h // *************************** // // some of the sort functions here are implemented twice to // better illustrate how the Comparer template parameter is used. // In "production" versions, there would only be one sort, which would // use the Comparer template parameter and which would be called by // a one line version of a sort function without the Comparer // parameter --- see the SelectionSort function for how this is done // both InsertionSort and MergeSort use duplicated code // // *************************** const int CUTOFF = 20; // used in quick/merge sorts template void Swap(apvector & v,int j, int k) // precondition: v[j] references value A, v[k] references value B // postcondition: v[k] references value B, v[k] references value A { Type temp = v[j]; v[j] = v[k]; v[k] = temp; } template void Insert(apvector & a ,int left,int right, const Comparer & comp) // precondition: left <= right // postcondition: a[left] <= ... <= a[right] // // standard insertion sort between left/right // for use in small quick/merge cases as well { int k,loc; Type hold; for(k=left+1;k<=right;k++) { // shift elements to make room for a[k] hold = a[k]; // insert this element loc = k; // location for insertion while (left < loc && comp.compare(hold,a[loc-1]) < 0) { a[loc] = a[loc-1]; loc--; } a[loc] = hold; } } template void InsertSort(apvector & a, int size, const Comparer & comp) // precondition: size = # of elements of a // postcondition: a is sorted // // uses insertion sort { Insert(a,0,size-1,comp); } template void Insert(apvector & a ,int left,int right) // precondition: left <= right // postcondition: a[left] <= ... <= a[right] // // standard insertion sort between left/right // for use in small quick/merge cases as well { int k,loc; Type hold; for(k=left+1;k<=right;k++) { // shift elements to make room for a[k] hold = a[k]; // insert this element loc = k; // location for insertion while (left < loc && hold < a[loc-1]) { a[loc] = a[loc-1]; loc--; } a[loc] = hold; } } template void InsertSort(apvector & a, int size) // precondition: size = # of elements of a // postcondition: a is sorted // // uses insertion sort { Insert(a,0,size-1); } template void SelectSort(apvector & a, int size, const Comparer & comp) // precondition: size = # of elements of a // postcondition: a is sorted // // standard selection sort { int j,k,min; for(j=0; j< size-1;j++) { min = j; for(k=j+1; k void SelectSort(apvector & a, int size) // precondition: size = # of elements of a // postcondition: a is sorted // // standard selection sort { SelectSort(a,size,Comparer()); } template void BubbleSort(apvector & a, int n) // precondition: n = # of elements in a // postcondition: a is sorted // note: this is a dog of a sort { int j,k; for(j=n-1; j > 0; j--) { // find largest element in 0..k, move to a[j] for(k=0; k < j; k++) { if (a[k+1] < a[k]) { Swap(a,k,k+1); } } } } template void ShellSort(apvector & a, int n) // precondition: n = # elements in a // postcondition: a is sorted // // shell sort using Hibbard increments, see Weiss "Algorithms, Data Structures and // Problem Solving with C++" { int h,j,k,loc,increment; Type hold,temp; for(h=1; h <= n/2; h *= 2 ) { // found power of 2 closest to n/2 } h--; // went past n/2 in loop guard while (h > 0) { // insertion sort using jumps of 'size' h, see InsertSort above for(k=h; k < n; k++) { hold = a[k]; loc = k; while (h <= loc && hold < a[loc-h]) { a[loc] = a[loc-h]; loc -= h; } a[loc] = hold; } h /= 2; } } template void Merge(apvector & a, apvector & b, int left,int mid,int right) // precondition: a sorted from a[left] ... a[mid] and from // a[mid+1] to a[right] // extra storage passed in as vector b // postcondition: a sorted from a[left] ... a[right] { int lk=left; // a's left index int rk = mid+1; // a's right index int bk = left; // b's index while (lk <= mid && rk <= right) // both parts non-empty? { if (a[lk] <= a[rk]) { b[bk] = a[lk]; lk++; } else { b[bk] = a[rk]; rk++; } bk++; } // finish any leftovers in a (only one of loops below executes) while (lk <= mid) { b[bk] = a[lk]; bk++; lk++; } while(rk <= right) { b[bk] = a[rk]; bk++; rk++; } // copy b back to a for(lk=left; lk <= right; lk++) { a[lk] = b[lk]; } } template void Merge(apvector & a, apvector & b, int left,int mid,int right, const Comparer & comp) // precondition: a sorted from a[left] ... a[mid] and from // a[mid+1] to a[right] // extra storage passed in as vector b // postcondition: a sorted from a[left] ... a[right] { int lk=left; // a's left index int rk = mid+1; // a's right index int bk = left; // b's index while (lk <= mid && rk <= right) // both parts non-empty? { if (comp.compare(a[lk],a[rk]) <= 0) { b[bk] = a[lk]; lk++; } else { b[bk] = a[rk]; rk++; } bk++; } // finish any leftovers in a (only one of loops below executes) while (lk <= mid) { b[bk] = a[lk]; bk++; lk++; } while(rk <= right) { b[bk] = a[rk]; bk++; rk++; } // copy b back to a for(lk=left; lk <= right; lk++) { a[lk] = b[lk]; } } template void DoMerge(apvector & a, apvector & temp, int left,int right, const Comparer & comp) // postcondition: a[left] <= ... <= a[right], // temp.length() == a.length(), temp is temp array for merging { int mid = (left+right)/2; if (right - left > CUTOFF) { DoMerge(a, temp, left,mid,comp); DoMerge(a, temp, mid+1,right,comp); Merge(a, temp, left,mid,right,comp); } else { Insert(a,left,right,comp); } } template void MergeSort(apvector & a,int n) { MergeSort(a, n, Comparer()); } template void MergeSort(apvector & a, int n, const Comparer & comp) { apvector temp(a.length()); DoMerge(a,temp,0,n-1,comp); } template int Median(apvector & a,int first,int last) // postcondition: returns index of median element of // a[first],a[last],a[mid], mid = (first+last)/2 { int mid=(first+last)/2; if (a[first] < a[mid]) { if (a[mid] < a[last]) return mid; else if (a[first] < a[last]) return last; else return first; } else { if (a[first] < a[last]) return first; else if (a[last] < a[mid]) return mid; else return last; } } template int Pivot(apvector & a,int first,int last) // postcondition: returns piv such that // first <= k <= piv, a[k] <= a[piv] // piv < k <= last, a[piv] < a[k] // standard Bently/ola pivot routine { int k,p=first; Type piv; Swap(a,first,Median(a,first,last)); piv = a[first]; for(k=first+1;k<=last;k++) { if (a[k] <= piv) { p++; Swap(a,k,p); } } Swap(a,p,first); return p; } template void Quick(apvector & a,int first,int last) // postcondition: a[first] <= ... <= a[list] { int piv; if (last - first > CUTOFF) { piv = Pivot(a,first,last); Quick(a,first,piv-1); Quick(a,piv+1,last); } else { Insert(a,first,last); } } template void QuickSort(apvector & a, int size) // precondition: size = # of elements of a // postcondition: a is sorted { Quick(a,0,size - 1); }