git.cworth.org Git - vogl/blob - src/voglcore/vogl_sort.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_sort.h
  28 // FIXME: The comparison functions are non-standard (they take an extra void * for user data, which is both good and bad).
  29 // Also, most of the sorts here are kinda useless in practice (either use vogl_introsort.h or vogl_mergesort.h), except maybe the index sorts.
  30 #pragma once
  31
  32 #include "vogl_core.h"
  33 #include "vogl_rand.h"
  34
  35 namespace vogl
  36 {
  37     template <typename T>
  38     inline bool default_compare_func(const T &lhs, const T &rhs, const void *pData)
  39     {
  40         VOGL_NOTE_UNUSED(pData);
  41         return lhs < rhs;
  42     }
  43
  44     template <typename T, typename F>
  45     inline void insertion_sort(int size, T *a, F compare_func, void *pCompare_func_data = NULL)
  46     {
  47         for (int i = 1; i < size; i++)
  48         {
  49             const T value(a[i]);
  50
  51             int j = i - 1;
  52             while ((j >= 0) && (compare_func(value, a[j], pCompare_func_data)))
  53             {
  54                 a[j + 1] = a[j];
  55                 j--;
  56             }
  57
  58             a[j + 1] = value;
  59         }
  60     }
  61
  62     template <typename T>
  63     inline void insertion_sort(int size, T *a)
  64     {
  65         insertion_sort(size, a, default_compare_func<T>, NULL);
  66     }
  67
  68     template <typename T, typename F>
  69     inline void shell_sort(int size, T *a, F compare_func, void *pCompare_func_data = NULL)
  70     {
  71         static const uint sequence[] = { 1, 4, 10, 23, 57, 132, 301, 701, 1577, 3548 };
  72         const uint cSequenceSize = sizeof(sequence) / sizeof(sequence[0]);
  73
  74         int s = cSequenceSize - 1;
  75
  76         do
  77         {
  78             int increment = sequence[s];
  79
  80             for (int i = increment; i < size; i++)
  81             {
  82                 const T temp(a[i]);
  83
  84                 int j = i;
  85                 while ((j >= increment) && (compare_func(temp, a[j - increment], pCompare_func_data)))
  86                 {
  87                     a[j] = a[j - increment];
  88                     j = j - increment;
  89                 }
  90
  91                 a[j] = temp;
  92             }
  93
  94         } while (--s >= 0);
  95     }
  96
  97     template <typename T>
  98     inline void shell_sort(int size, T *a)
  99     {
 100         shell_sort(size, a, default_compare_func<T>, NULL);
 101     }
 102
 103     template <typename T, typename F>
 104     inline void heap_sort(int size, T *a, F compare_func, void *pCompare_func_data = NULL)
 105     {
 106         int start = (size - 2) >> 1;
 107         while (start >= 0)
 108         {
 109             int root = start;
 110
 111             for (;;)
 112             {
 113                 int child = (root << 1) + 1;
 114                 if (child >= size)
 115                     break;
 116
 117                 if (((child + 1) < size) && (compare_func(a[child], a[child + 1], pCompare_func_data)))
 118                     child++;
 119
 120                 if (compare_func(a[root], a[child], pCompare_func_data))
 121                 {
 122                     utils::swap(a[root], a[child]);
 123                     root = child;
 124                 }
 125                 else
 126                     break;
 127             }
 128
 129             start--;
 130         }
 131
 132         int end = size - 1;
 133         while (end > 0)
 134         {
 135             utils::swap(a[end], a[0]);
 136
 137             int root = 0;
 138
 139             for (;;)
 140             {
 141                 int child = (root << 1) + 1;
 142                 if (child >= end)
 143                     break;
 144
 145                 if (((child + 1) < end) && (compare_func(a[child], a[child + 1], pCompare_func_data)))
 146                     child++;
 147
 148                 if (compare_func(a[root], a[child], pCompare_func_data))
 149                 {
 150                     utils::swap(a[root], a[child]);
 151                     root = child;
 152                 }
 153                 else
 154                     break;
 155             }
 156
 157             end--;
 158         }
 159     }
 160
 161     template <typename T>
 162     inline void heap_sort(int size, T *a)
 163     {
 164         heap_sort(size, a, default_compare_func<T>, NULL);
 165     }
 166
 167     template <typename T, typename F>
 168     inline void indexed_heap_sort(int size, const T *a, uint *pIndices, F compare_func, void *pCompare_func_data = NULL)
 169     {
 170         int start = (size - 2) >> 1;
 171         while (start >= 0)
 172         {
 173             int root = start;
 174
 175             for (;;)
 176             {
 177                 int child = (root << 1) + 1;
 178                 if (child >= size)
 179                     break;
 180
 181                 if (((child + 1) < size) && (compare_func(a[pIndices[child]], a[pIndices[child + 1]], pCompare_func_data)))
 182                     child++;
 183
 184                 if (compare_func(a[pIndices[root]], a[pIndices[child]], pCompare_func_data))
 185                 {
 186                     utils::swap(pIndices[root], pIndices[child]);
 187                     root = child;
 188                 }
 189                 else
 190                     break;
 191             }
 192
 193             start--;
 194         }
 195
 196         int end = size - 1;
 197         while (end > 0)
 198         {
 199             utils::swap(pIndices[end], pIndices[0]);
 200
 201             int root = 0;
 202
 203             for (;;)
 204             {
 205                 int child = (root << 1) + 1;
 206                 if (child >= end)
 207                     break;
 208
 209                 if (((child + 1) < end) && (compare_func(a[pIndices[child]], a[pIndices[child + 1]], pCompare_func_data)))
 210                     child++;
 211
 212                 if (compare_func(a[pIndices[root]], a[pIndices[child]], pCompare_func_data))
 213                 {
 214                     utils::swap(pIndices[root], pIndices[child]);
 215                     root = child;
 216                 }
 217                 else
 218                     break;
 219             }
 220
 221             end--;
 222         }
 223     }
 224
 225     template <typename T>
 226     inline void indexed_heap_sort(int size, const T *a, uint *pIndices)
 227     {
 228         indexed_heap_sort(size, a, pIndices, default_compare_func<T>, NULL);
 229     }
 230
 231     inline bool sort_test()
 232     {
 233         uint num_failures = 0;
 234
 235         vogl::random r;
 236         r.seed(2);
 237         for (uint trial = 0; trial < 50000; trial++)
 238         {
 239             uint sz = r.irand_inclusive(1, 8192);
 240             uint z = r.irand_inclusive(2, 8192);
 241             printf("%u\n", sz);
 242
 243             vogl::vector<uint> x(sz);
 244             for (uint i = 0; i < x.size(); i++)
 245                 x[i] = r.irand(0, z);
 246
 247             vogl::vector<uint> indices(sz);
 248             for (uint i = 0; i < sz; i++)
 249                 indices[i] = i;
 250
 251             bool used_indices = false;
 252
 253             switch (r.irand_inclusive(0, 3))
 254             {
 255                 case 0:
 256                     vogl::insertion_sort(x.size(), x.get_ptr());
 257                     break;
 258                 case 1:
 259                     vogl::shell_sort(x.size(), x.get_ptr());
 260                     break;
 261                 case 2:
 262                     vogl::heap_sort(x.size(), x.get_ptr());
 263                     break;
 264                 case 3:
 265                     vogl::indexed_heap_sort(x.size(), x.get_ptr(), indices.get_ptr());
 266                     used_indices = true;
 267                     break;
 268             }
 269
 270             if (used_indices)
 271             {
 272                 for (uint i = 1; i < x.size(); i++)
 273                 {
 274                     if (x[indices[i - 1]] > x[indices[i]])
 275                     {
 276                         num_failures++;
 277                         break;
 278                     }
 279                 }
 280             }
 281             else
 282             {
 283                 for (uint i = 1; i < x.size(); i++)
 284                 {
 285                     if (x[i - 1] > x[i])
 286                     {
 287                         num_failures++;
 288                         break;
 289                     }
 290                 }
 291             }
 292         }
 293
 294         return num_failures == 0;
 295     }
 296
 297 } // namespace vogl