/*Hello flipcoders, here's my recently completed assortment of usefultemplated array routines, mostly sorting routines.I know some of these are quite basic routines, but they are good to have handy.I'm fairly sure these are bug free, (I've tested them thoroughly)but if you find a bug, or have other suggestions or comments, let me know.Yeah I know you could just use STL for these things, but you might learnmore from this code. If nothing more these should be very useful to beginners.To use these all you need to do is have an array (any type) anddefine a few operators for that data type.For example given the following data type:typedef unsigned short keyType;typedef struct item { keyType key; long foo; char bar;};The routines below will require that you define some or all of the following:(unless you're using built in data types)inline int operator < (item &a, item &b) {return a.key < b.key;}inline int operator == (item &a, item &b) {return a.key == b.key;}inline int operator & (item &a, unsigned long b) {return ((unsigned long)a.key) & b;}If the key is not the entire item, also define these:inline int operator == (item &a, keyType b) {return a.key == b;}inline int operator < (item &a, keyType b) {return a.key < b;}Also if necessary, define a copy constructor.You can now use the routines below like this:const int arraysize = 1000;item myarray[arraysize];...QuickSort(myarray, arraysize);I hope the rest is mostly self-explanatory.Written on a Mac using Symantec C++ v8.6.Permission to use/copy/modify/distribute hereby granted.Later on I'll post a similiar thing for lists.[NZ]_i/\/\alc(Malcolm)*/#ifndef MyArrayUtils#define MyArrayUtils#define CutOff 16 //final Insertionsort cutoff size. Set to zero or more#define MEDIAN_OF_THREE //Better Quicksort splitter method option. Comment out if you like#define SMALLEST_FIRST //Reduces stack memory usage. Comment out if you like//If search fails this is returned#define NotFound -1//Basic item swap macro#define Swap(a,b) do{TItem x=(a);(a)=(b);(b)=x;}while(false)// *** Utilities ***// Return true if the array is sortedtemplate <class TItem, class TSize>int Sorted(TItem a[], TSize n) { for (TSize i = n-1; i > 0; --i) if (a[i] < a[i-1]) return false; return true;}// Reverses the arraytemplate <class TItem, class TSize>void Reverse(TItem a[], TSize n) {; for (TSize i = (--n-1)>>1; i >= 0; --i) Swap(a[i], a[n-i]);}// *** Searching ***// O(logn) : sorted onlytemplate <class TItem, class TSize, class TKey>TSize BinarySearch(TItem a[], TSize n, TKey find) { TSize l = 0, r = n-1; while (l <= r) { TSize m = (l + r)>>1; if (a[m] < find) l = m + 1; else r = m - 1; } if (a[l] == find) return l; else return NotFound;}// O(n) : sorted onlytemplate <class TItem, class TSize, class TKey>TSize SortedSequentialSearch(TItem a[], TSize n, TKey find) { for (TSize i=0; i < n; ++i) if (a[i] < find) continue; else if (a[i] == find) return i; else return NotFound; return NotFound;}// O(n) : sorted onlytemplate <class TItem, class TSize, class TKey>inline TSize SequentialSearch(TItem a[], TSize n, TKey find) { for (TSize i=0; i < n; ++i) if (a[i] == find) return i; return NotFound;}// *** Sorting ***// O(nlogn) : uses stack memory : only integer keystemplate <class TItem, class TSize>void RadixExchangeSortAux(TItem a[], TSize l, TSize r, unsigned long mask) { while (r - l > CutOff) { TSize i = l, j = r-1; while (i <= j) { while (((a[i] & mask) <=0) && i<=j) ++i; while (((a[j] & mask) > 0) && i<=j) --j; if (i < j) { Swap(a[i], a[j]); ++i; --j; } } if ((mask>>=1) == 0) break;#ifdef SMALLEST_FIRST if (i-l <= r-j) {#endif RadixExchangeSortAux(a, l, i, mask); l = i;#ifdef SMALLEST_FIRST } else { RadixExchangeSortAux(a, i, r, mask); r = i; }#endif }}template <class TItem, class TSize>void RadixExchangeSort(TItem a[], TSize n) { RadixExchangeSortAux(a, (TSize)0, n, (unsigned long)0x80000000);#if CutOff > 0 InsertionSort(a, n);#endif}// O(nlogn) .. O(n^2)template <class TItem, class TSize>void QuickSortAux(TItem a[], TSize l, TSize r) { while (r - l > CutOff) { TSize i = (l+r)>>1, j;#ifdef MEDIAN_OF_THREE if (a[i] < a[l]) Swap(a[i], a[l]); if (a[r] < a[l]) Swap(a[r], a[l]); if (a[r] < a[i]) Swap(a[r], a[i]); TItem x = a[i]; i = l, j = r;#else TItem x = a[i]; i = l-1, j = r+1;#endif do { while (a[++i] < x) ; while (x < a[--j]) ; if (j < i) break; Swap(a[i], a[j]); } while (true); #ifdef SMALLEST_FIRST if (j-l <= r-i) {#endif QuickSortAux(a, l, j); l = i;#ifdef SMALLEST_FIRST } else { QuickSortAux(a, i, r); r = j; }#endif }}template <class TItem, class TSize>void QuickSort(TItem a[], TSize n) { QuickSortAux(a, (TSize)0, n-1);#if CutOff > 0 InsertionSort(a, n);#endif}// O(nlogn)template <class TItem, class TSize>void HeapSortAux(TItem a[], TSize l, TSize r) { TSize j = l*2; TItem x = a[l]; while (j <= r) { if (j < r) if (a[j] < a[j + 1]) ++j; if (! (x < a[j])) break; a[l] = a[j]; l = j; j*=2; } a[l] = x;}template <class TItem, class TSize>void HeapSort(TItem a[], TSize n) { --n; TSize k = n>>1; while (k >= 0) HeapSortAux(a, k--, n); k = n; while (k > 0) { Swap(a[0], a[k]); HeapSortAux(a, 0, --k); }}// O(nlogn) : Stable : uses double storage heap memorytemplate <class TItem, class TSize>void MergeSortAux(TItem a[], TItem temp[], TSize l, TSize r) { if (l < r) { TSize m = (l + r)>>1; MergeSortAux(a, temp, l, m); MergeSortAux(a, temp, m + 1, r); TSize i=l, j=m+1, c=l; while (i <= m && j <= r) temp[c++] = (a[j] < a[i]) ? a[j++] : a[i++]; while (i <= m) temp[c++] = a[i++]; for (TSize k=l; k < c; ++k) a[k]=temp[k]; }}template <class TItem, class TSize>void MergeSort(TItem a[], TSize n) { TItem *temp = new TItem[n]; if (temp == NULL) return; MergeSortAux(a, temp, (TSize)0, --n); delete[] temp;}template <class TItem, class TSize>void ShellSort(TItem a[], TSize n) { const int incs[15] = { 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768, 463792, 1391376 }; for (int l = 14; l > 0; --l) { TSize m = incs[l]; for (TSize j = m; j < n; ++j) { TSize i = j - m, k = j; while (a[k] < a[i]) { Swap(a[i], a[k]); if (i < m) break; k = i; i-=m; } } } InsertionSort(a, n);}template <class TItem, class TSize>void CombSort(TItem a[], TSize n) { Boolean swapped = false; TSize gap = n, top; do { gap = (gap*10)/13; switch (gap) { case 0: gap = 1; break; case 9: case 10: gap = 11; break; default: break; } swapped = false; top = n - gap; for (TSize i = 0; i < top; i++) { TSize j = i + gap; if (a[j] < a[i]) { Swap(a[i], a[j]); swapped = true; } } } while (swapped || (gap > 1));}// O(n^2) : Stabletemplate <class TItem, class TSize>void BinaryInsertionSort(TItem a[], TSize n) { for (TSize i = 1; i < n; ++i) { TSize l=0, r=i-1, j=r; item x = a[i]; while (l <= r) { TSize m = (l + r)>>1; if (x < a[m]) r = m - 1; else l = m + 1; } while (j >= l) { a[j + 1] = a[j]; --j; } a[l] = x; }}// O(n^2) : Stabletemplate <class TItem, class TSize>void InsertionSort(TItem a[], TSize n) { --n; for (TSize i = 0; i < n; ++i) { item x = a[i + 1]; TSize j = i; while ((x < a[j]) && (j >= 0)) { a[j + 1] = a[j]; --j; } a[j + 1] = x; }}// O(n^2)// (Dual SelectionSort)template <class TItem, class TSize>void ShakerSort2(TItem a[], TSize n) { TSize i = 0; --n; while (i < n) { TSize min = i; TSize max = i; for (TSize j = i + 1; j <= n; j++) { if (a[j] < a[min]) min = j; if (a[max] < a[j]) max = j; } Swap(a[min], a[i]); if (max == i) Swap(a[min], a[n]); else Swap(a[max], a[n]); i++; n--; }}// O(n^2)template <class TItem, class TSize>void SelectionSort(TItem a[], TSize n) { --n; for (TSize i = 0; i < n; ++i) { TSize m = i; for (TSize j = n; j > i; --j) if (a[j] < a[m]) m = j; Swap(a[i], a[m]); }}// O(n^2): Stable// (Bidirectional BubbleSort)template <class TItem, class TSize>void ShakerSort(TItem a[], TSize n) { TSize j, l=1, r=n-1, k=r; do { for (j = r; j >= l; --j) if (a[j] < a[j - 1]) { Swap(a[j - 1], a[j]); k = j; } l = k + 1; for (j = l; j <= r; ++j) if (a[j] < a[j - 1]) { Swap(a[j - 1], a[j]); k = j; } r = k - 1; } while (l <= r);}// O(n^2) : Stabletemplate <class TItem, class TSize>void BubbleSort(TItem a[], TSize n) { --n; for (TSize i = 0; i < n; ++i) for (TSize j = n; j > i; --j) if (a[j] < a[j - 1]) Swap(a[j - 1], a[j]);}#endif |
