Hendrik Lipka / irrxml

A port of the irrlicht XML parser library.

heapsort.h@0:41a49a73580c, 2010-11-17 (annotated)

Committer:
hlipka
Date:
Wed Nov 17 20:19:41 2010 +0000
Revision:
0:41a49a73580c
initial version

Who changed what in which revision?

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