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