include/heapsort.h

   1 // Copyright (C) 2002-2012 Nikolaus Gebhardt\r
   2 // This file is part of the "Irrlicht Engine".\r
   3 // For conditions of distribution and use, see copyright notice in irrlicht.h\r
   4 \r
   5 #ifndef __IRR_HEAPSORT_H_INCLUDED__\r
   6 #define __IRR_HEAPSORT_H_INCLUDED__\r
   7 \r
   8 #include "irrTypes.h"\r
   9 \r
  10 namespace irr\r
  11 {\r
  12 namespace core\r
  13 {\r
  14 \r
  15 //! Sinks an element into the heap.\r
  16 template<class T>\r
  17 inline void heapsink(T*array, s32 element, s32 max)\r
  18 {\r
  19         while ((element<<1) < max) // there is a left child\r
  20         {\r
  21                 s32 j = (element<<1);\r
  22 \r
  23                 if (j+1 < max && array[j] < array[j+1])\r
  24                         j = j+1; // take right child\r
  25 \r
  26                 if (array[element] < array[j])\r
  27                 {\r
  28                         T t = array[j]; // swap elements\r
  29                         array[j] = array[element];\r
  30                         array[element] = t;\r
  31                         element = j;\r
  32                 }\r
  33                 else\r
  34                         return;\r
  35         }\r
  36 }\r
  37 \r
  38 \r
  39 //! Sorts an array with size 'size' using heapsort.\r
  40 template<class T>\r
  41 inline void heapsort(T* array_, s32 size)\r
  42 {\r
  43         // for heapsink we pretend this is not c++, where\r
  44         // arrays start with index 0. So we decrease the array pointer,\r
  45         // the maximum always +2 and the element always +1\r
  46 \r
  47         T* virtualArray = array_ - 1;\r
  48         s32 virtualSize = size + 2;\r
  49         s32 i;\r
  50 \r
  51         // build heap\r
  52 \r
  53         for (i=((size-1)/2); i>=0; --i)\r
  54                 heapsink(virtualArray, i+1, virtualSize-1);\r
  55 \r
  56         // sort array, leave out the last element (0)\r
  57         for (i=size-1; i>0; --i)\r
  58         {\r
  59                 T t = array_[0];\r
  60                 array_[0] = array_[i];\r
  61                 array_[i] = t;\r
  62                 heapsink(virtualArray, 1, i + 1);\r
  63         }\r
  64 }\r
  65 \r
  66 } // end namespace core\r
  67 } // end namespace irr\r
  68 \r
  69 #endif\r
  70 \r