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?
User | Revision | Line number | New 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 |