nucleus/library/algorithms/sorts.h

   1 #ifndef ASSORTED_SORTS_GROUP
   2 #define ASSORTED_SORTS_GROUP
   3
   4 //////////////
   5 // Name   : shell_sort
   6 // Author : Chris Koeritz
   7 //////////////
   8 // Copyright (c) 1991-$now By Author.  This program is free software; you can
   9 // redistribute it and/or modify it under the terms of the GNU General Public
  10 // License as published by the Free Software Foundation:
  11 //     http://www.gnu.org/licenses/gpl.html
  12 // or under the terms of the GNU Library license:
  13 //     http://www.gnu.org/licenses/lgpl.html
  14 // at your preference.  Those licenses describe your legal rights to this
  15 // software, and no other rights or warranties apply.
  16 // Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
  17 //////////////
  18
  19 namespace algorithms {
  20
  21 /*
  22  * general considerations:
  23  *
  24  * + Generic objects to be sorted must support comparison operators.
  25  *
  26  * + If the "reverse" flag is true, the arrays will be sorted in reverse order.
  27  *   Reverse order here means "descending", such that array element i is always greater than or equal to array element i+1.
  28  *   Normal order is "ascending", such that element i is always less than or equal to array element i+1.
  29  *
  30  */
  31
  32 //! shell sort algorithm.
  33 /*!
  34  * Sorts a C array of the "type" with "n" elements.
  35  * Operates on the original array.
  36  * Performs in O(n log(n)) time.
  37  * Algorithm is based on Kernighan and Ritchie's "The C Programming Language".
  38 */
  39 template <class type>
  40 void shell_sort(type v[], int n, bool reverse = false)
  41 {
  42   type temp;
  43   int gap, i, j;
  44   /* the gap sizes decrease quadratically(?).  they partition the array of
  45    * items that need to be sorted into first two groups, then four, then
  46    * eight, etc.  the inner loop iterates across each gap's worth of the array.
  47          */
  48   for (gap = n / 2; gap > 0; gap /= 2) {
  49     // the i indexed loop is the base for where the comparisons are made in
  50     // the j indexed loop.  it makes sure that each item past the edge of
  51     // the gap sized partition gets considered.
  52     for (i = gap; i < n; i++) {
  53       // the j indexed loop looks at the values in our current gap and ensures
  54       // that they are in sorted order.
  55       if (!reverse) {
  56         // normal ordering.
  57         for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j = j - gap) {
  58           // swap the elements that are disordered.
  59           temp = v[j]; v[j] = v[j + gap]; v[j + gap] = temp;
  60         }
  61       } else {
  62         // reversed ordering.
  63         for (j = i - gap; j >= 0 && v[j] < v[j + gap]; j = j - gap) {
  64           // swap the elements that are disordered.
  65           temp = v[j]; v[j] = v[j + gap]; v[j + gap] = temp;
  66         }
  67       }
  68     }
  69   }
  70 }
  71
  72 //////////////
  73
  74 /*!
  75  * sorted array merge
  76  *
  77  * merges two sorted arrays into a single sorted array.
  78  */
  79 template <class type>
  80 basis::array<type> merge(const basis::array<type> &first, basis::array<type> &second, bool reverse)
  81 {
  82         int first_iter = 0;
  83         int second_iter = 0;
  84         //hmmm: careful below; remember differences in heap allocated objects versus new-ed ones.
  85         //this might be really inefficient to return on stack..?
  86         basis::array<type> to_return;
  87         // operate until we've consumed both of the arrays.
  88         while ((first_iter < first.length()) && (second_iter < second.length())) {
  89                 if ( (!reverse && (first[first_iter] <= second[second_iter]))
  90                                 || (reverse && (first[first_iter] >= second[second_iter])) ) {
  91                         // next item from first array goes into the merged array next.
  92                         to_return += first[first_iter++];
  93                 } else {
  94                         // next item from second array goes into the merged array next.
  95                         to_return += second[second_iter++];
  96                 }
  97         }
  98         return to_return;
  99 }
 100
 101 /*!
 102  * merge sort
 103  *
 104  * operates in O(n log(n)) time.
 105  * returns a new array with sorted data.
 106  */
 107 template <class type>
 108 basis::array<type> merge_sort(const basis::array<type> &v, bool reverse = false)
 109 {
 110         if (v.length() <= 1) {
 111                 return new basis::array<type>(v);
 112         }
 113         int midway = v.length() / 2;
 114         basis::array<type> firstPart = merge_sort(v.subarray(0, midway - 1));
 115         basis::array<type> secondPart = merge_sort(v.subarray(midway, v.length() - 1));
 116         return merge(firstPart, secondPart, reverse);
 117 }
 118
 119 //////////////
 120
 121 /*
 122  * a heap is a structure that can quickly return the highest (or lowest) value,
 123  * depending on how the priority of the item is defined.  restructuring is
 124  * also fast, when new data are added.  the implicit structure is a binary tree
 125  * represented in a flat array, where the children of a node at position n are
 126  * in positions n * 2 + 1 and n * 2 + 2 (zero based).
 127  */
 128 //hmmm: move this class out to basis?.
 129 template <class type>
 130 class heap
 131 {
 132 public:
 133         heap(int max_elements, bool reverse) {
 134                 _max_elements = max_elements;
 135                 _reverse = reverse;
 136                 _heapspace = new basis::array<type> (_max_elements);
 137         }
 138
 139         virtual ~heap() {
 140                 WHACK(_heapspace);
 141         }
 142
 143         //! swaps the values in the heap stored at positions a and b.
 144         void swap(int a, int b)
 145         {
 146                 type temp = _heapspace[a];
 147                 _heapspace[a] = _heapspace[b];
 148                 _heapspace[b] = temp;
 149         }
 150
 151         //! re-sorts the heapspace to maintain the heap ordering.
 152         void heapify()
 153         {
 154
 155         }
 156
 157   void add(type to_add) {
 158         //
 159   }
 160
 161
 162 private:
 163         int _max_elements;
 164         bool _reverse;
 165         basis::array<type> *_heapspace = NULL_POINTER;
 166 };
 167
 168 /*!
 169  * heap sort
 170  *
 171  * operates in O(n log(n)).
 172  * sorts the original array.
 173  */
 174 template <class type>
 175 void heap_sort(type v[], int n, bool reverse = false)
 176 {
 177         // use heap.  do sorty.
 178 }
 179
 180 //////////////
 181
 182 template <class type>
 183 void partition(type v[], int start, int end)
 184 {
 185
 186 }
 187
 188 //! the recursive version of quick sort that does the work for our convenience method.
 189 template <class type>
 190 void inner_quick_sort(type v[], int n, int start, int end, bool reverse = false)
 191 {
 192         if (start >= end) {
 193                 // nothing to see here.
 194         } else {
 195                 // figure out where to pivot, and sort both halves around the pivot index.
 196                 int pivot = partition(v,        start, end);
 197                 quicksort(v, start, pivot - 1);
 198                 quicksort(v, pivot + 1, end);
 199         }
 200 }
 201
 202 /*!
 203  * quick sort
 204  *
 205  * operates in O(n log(n)) time on average, worst case O(n^2).
 206  * sorts the original array.
 207  */
 208 template <class type>
 209 void quick_sort(type v[], int n, bool reverse = false)
 210 {
 211         inner_quick_sort(v, n, 0, n-1, reverse);
 212 }
 213
 214 } // namespace.
 215
 216 #endif // outer guard.
 217