nucleus/library/algorithms/sorts.h

   1 #ifndef ASSORTED_SORTS_GROUP
   2 #define ASSORTED_SORTS_GROUP
   3
   4 //////////////
   5 // Name   : sorts
   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         //! dumps the contents of the list out, assuming that the type can be turned into an int.
  33         template<class type>
  34         basis::astring dump_list(type v[], int size)
  35         {
  36                 basis::astring ret;
  37                 for (int i = 0; i < size; i++) {
  38                         ret += basis::a_sprintf("%d ", (int)v[i]);
  39                 }
  40                 return ret;
  41         }
  42
  43         //! shell sort algorithm.
  44         /*!
  45          * Sorts a C array of the "type" with "n" elements.
  46          * Operates on the original array.
  47          * Performs within O(n^2) time (depending on the gap size used).
  48          * Algorithm is based on Kernighan and Ritchie's "The C Programming Language".
  49          */
  50         template<class type>
  51         void shell_sort(type v[], int n, bool reverse = false)
  52         {
  53                 type temp;
  54                 int gap, i, j;
  55                 /* the gap sizes decrease quadratically(?).  they partition the array of
  56                  * items that need to be sorted into first two groups, then four, then
  57                  * eight, etc.  the inner loop iterates across each gap's worth of the array.
  58                  */
  59                 for (gap = n / 2; gap > 0; gap /= 2) {
  60                         // the i indexed loop is the base for where the comparisons are made in
  61                         // the j indexed loop.  it makes sure that each item past the edge of
  62                         // the gap sized partition gets considered.
  63                         for (i = gap; i < n; i++) {
  64                                 // the j indexed loop looks at the values in our current gap and ensures
  65                                 // that they are in sorted order.
  66                                 if (!reverse) {
  67                                         // normal ordering.
  68                                         for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j = j - gap) {
  69                                                 // swap the elements that are disordered.
  70                                                 temp = v[j];
  71                                                 v[j] = v[j + gap];
  72                                                 v[j + gap] = temp;
  73                                         }
  74                                 } else {
  75                                         // reversed ordering.
  76                                         for (j = i - gap; j >= 0 && v[j] < v[j + gap]; j = j - gap) {
  77                                                 // swap the elements that are disordered.
  78                                                 temp = v[j];
  79                                                 v[j] = v[j + gap];
  80                                                 v[j + gap] = temp;
  81                                         }
  82                                 }
  83                         }
  84                 }
  85         }
  86
  87 //////////////
  88
  89         /*!
  90          * sorted array merge
  91          *
  92          * merges two sorted arrays into a single sorted array.
  93          */
  94         template<class type>
  95         basis::array<type> merge(basis::array<type> &first, basis::array<type> &second, bool reverse)
  96         {
  97                 basis::array<type> to_return;
  98                 // operate until we've consumed both of the arrays.
  99                 while ((first.length() > 0) || (second.length() > 0)) {
 100                         if (first.length() <= 0) {
 101                                 // nothing left in first, so use the second.
 102                                 to_return += second[0];
 103                                 second.zap(0, 0);
 104                         } else if (second.length() <= 0) {
 105                                 to_return += first[0];
 106                                 first.zap(0, 0);
 107                         } else if ((!reverse && (first[0] <= second[0])) || (reverse && (first[0] >= second[0]))) {
 108                                 // the first list has a better value to add next.
 109                                 to_return += first[0];
 110                                 first.zap(0, 0);
 111                         } else {
 112                                 // the second list has a better value to add next.
 113                                 to_return += second[0];
 114                                 second.zap(0, 0);
 115                         }
 116                 }
 117                 return to_return;
 118         }
 119
 120         /*!
 121          * merge sort
 122          *
 123          * operates in O(n log(n)) time.
 124          * returns a new array with sorted data.
 125          */
 126         template<class type>
 127         basis::array<type> merge_sort(const basis::array<type> &v, bool reverse = false)
 128         {
 129                 if (v.length() <= 1) {
 130                         return basis::array<type>(v);
 131                 }
 132                 int midway = v.length() / 2;
 133                 basis::array<type> firstPart = merge_sort(v.subarray(0, midway - 1), reverse);
 134                 basis::array<type> secondPart = merge_sort(v.subarray(midway, v.length() - 1), reverse);
 135                 return merge(firstPart, secondPart, reverse);
 136         }
 137
 138 //////////////
 139
 140         /*!
 141          * a heap is a structure that can quickly return the highest (or lowest) value,
 142          * depending on how the priority of the item is defined.
 143          * a "normal" heap keeps the highest element available first; a reverse sorted heap
 144          * keeps the lowest element available first.
 145          * restructuring the heap is fast, and is O(n log(n)).
 146          * the implicit structure is a binary tree
 147          * represented in a flat array, where the children of a node at position n are
 148          * in positions n * 2 + 1 and n * 2 + 2 (zero based).
 149          */
 150 //hmmm: move this class out to basis?.
 151         template<class type>
 152         class heap
 153         {
 154         public:
 155                 heap(type to_sort[], int n, bool reverse)
 156                 {
 157                         _total = n;
 158                         _reverse = reverse;
 159                         _heapspace = to_sort;
 160                         heapify();
 161                 }
 162
 163                 //! swaps the values in the heap stored at positions a and b.
 164                 void swap_values(int a, int b)
 165                 {
 166                         type temp = _heapspace[a];
 167                         _heapspace[a] = _heapspace[b];
 168                         _heapspace[b] = temp;
 169                 }
 170
 171                 //! get the index of the parent of the node at i.
 172                 /*! this will not return the parent index of the root, since there is no parent. */
 173                 int parent_index(int i)
 174                 {
 175                         return i / 2;  // rely on integer division to shave off remainder.
 176                 }
 177
 178                 //! returns the left child of node at position i.
 179                 int left_child(int i)
 180                 {
 181                         return 2 * i + 1;
 182                 }
 183
 184                 //! returns the right child of node at position i.
 185                 int right_child(int i)
 186                 {
 187                         return 2 * i + 2;
 188                 }
 189
 190                 //! re-sorts the heapspace to maintain the heap ordering.
 191                 void heapify()
 192                 {
 193                         int start = parent_index(_total - 1);
 194                         // iterate from the back of the array towards the front, so depth-first.
 195                         while (start >= 0) {
 196                                 // sift down the node at the index 'start' such that all nodes below it are heapified.
 197                                 sift_down(start, _total - 1);
 198                                 start--;  // move the start upwards towards the root.
 199                         }
 200                 }
 201
 202                 void sift_down(int start, int end)
 203                 {
 204                         int root = start;
 205
 206                         // while the current root still has a kid...
 207                         while (left_child(root) <= end) {
 208                                 int child = left_child(root);
 209                                 // figure out which child to swap with.
 210                                 int swap = root;
 211                                 // check if the root should be swapped with this kid.
 212                                 if ((!_reverse && (_heapspace[swap] > _heapspace[child]))
 213                                     || (_reverse && (_heapspace[swap] < _heapspace[child])))
 214                                 {
 215                                         swap = child;
 216                                 }
 217                                 // check if the other child should be swapped with the root or left kid.
 218                                 if ((child + 1 <= end)
 219                                     && ((!_reverse && (_heapspace[swap] > _heapspace[child + 1]))
 220                                         || (_reverse && (_heapspace[swap] < _heapspace[child + 1]))))
 221                                 {
 222                                         swap = child + 1;
 223                                 }
 224                                 if (swap == root) {
 225                                         // the root has the largest (or smallest) element, so we're done.
 226                                         return;
 227                                 } else {
 228                                         swap_values(root, swap);
 229                                         root = swap;
 230                                         // repeat to continue sifting down the child now.
 231                                 }
 232                         }
 233                 }
 234
 235                 //! re-sorts the heapspace to maintain the heap ordering.  this uses sift_up.
 236                 void alt_heapify()
 237                 {
 238                         int end = 1;  // start at first child.
 239
 240                         while (end < _total) {
 241                                 // sift down the node at the index 'start' such that all nodes below it are heapified.
 242                                 sift_up(0, end++);
 243                         }
 244                 }
 245
 246                 //! start is how far up in the heap to sort.  end is the node to sift.
 247                 void sift_up(int start, int end)
 248                 {
 249                         int child = end;
 250                         // loop until we hit the starting node, where we're done.
 251                         while (child > start) {
 252                                 int parent = parent_index(child);
 253                                 if ((!_reverse && (_heapspace[parent] < _heapspace[child]))
 254                                     || (_reverse && (_heapspace[parent] > _heapspace[child])))
 255                                 {
 256                                         swap_values(parent, child);
 257                                         child = parent;
 258                                         // continue sifting at the parent now.
 259                                 } else {
 260                                         // done sorting.
 261                                         return;
 262                                 }
 263                         }
 264                 }
 265
 266         private:
 267                 bool _reverse = false;  // is the sorting in reverse?
 268                 int _total = 0;
 269                 int *_heapspace = NULL_POINTER;
 270         };
 271
 272         /*!
 273          * heap sort
 274          *
 275          * operates in O(n log(n)).
 276          * sorts the original array.
 277          */
 278         template<class type>
 279         void heap_sort(type v[], int n, bool reverse = false)
 280         {
 281                 // reverse the sense of "reverse", since our algorithm expects a normal heap (with largest on top).
 282                 heap<type> hap(v, n, !reverse);
 283
 284                 int end = n - 1;
 285                 while (end > 0) {
 286                         // a[0] is the root and largest value for a normal heap. The swap moves it to the real end of the list and takes it out of consideration.
 287                         hap.swap_values(end, 0);
 288                         // reduce the heap size by 1.
 289                         end--;
 290                         // that swap ruined the heap property, so re-heapify.
 291                         hap.sift_down(0, end);
 292                 }
 293         }
 294
 295 //////////////
 296
 297         //! swaps the values in the array stored at positions a and b.
 298         template<class type>
 299         void swap_values(type array[], int a, int b)
 300         {
 301                 type temp = array[a];
 302                 array[a] = array[b];
 303                 array[b] = temp;
 304         }
 305
 306         // hoare's partition implementation.
 307         template<class type>
 308         int partition(type a[], int start, int end, bool reverse)
 309         {
 310 //              printf("before partition: %s\n", dump_list(a + start, end - start + 1).s());
 311                 int pivot = a[start];
 312                 int i = start - 1;
 313                 int j = end + 1;
 314                 while (true) {
 315                         do {
 316                                 i++;
 317                         } while ((!reverse && (a[i] < pivot)) || (reverse && (a[i] > pivot)));
 318                         do {
 319                                 j--;
 320                         } while ((!reverse && (a[j] > pivot)) || (reverse && (a[j] < pivot)));
 321
 322                         if (i >= j) {
 323 //                              printf("after partition: %s\n", dump_list(a + start, end - start + 1).s());
 324                                 return j;
 325                         }
 326                         swap_values(a, i, j);
 327                 }
 328         }
 329
 330         //! the recursive version of quick sort that does the work for our convenience method.
 331         template<class type>
 332         void inner_quick_sort(type v[], int start, int end, bool reverse)
 333         {
 334                 if (start < end) {
 335                         // figure out where to pivot, and sort both halves around the pivot index.
 336                         int pivot = partition(v, start, end, reverse);
 337                         inner_quick_sort(v, start, pivot, reverse);
 338                         inner_quick_sort(v, pivot + 1, end, reverse);
 339                 }
 340         }
 341
 342         /*!
 343          * quick sort
 344          *
 345          * operates in O(n log(n)) time on average, worst case O(n^2).
 346          * sorts the original array.
 347          */
 348         template<class type>
 349         void quick_sort(type v[], int n, bool reverse = false)
 350         {
 351                 inner_quick_sort(v, 0, n - 1, reverse);
 352         }
 353
 354 }  // namespace.
 355
 356 #endif // outer guard.
 357