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