True Axis Physics SDK 1.2.0.1 Beta Documentation
www.trueaxis.com

---

HeapSort.h

//---------------------------------------------------------------------------------
// File Name: HeapSort.h
// Description:
//
// Copyright (C) 2004 - 2005 True Axis Pty Ltd, Australia. 
// All Rights Reserved.
//
// History:
//      Luke Ryan:      Created
//---------------------------------------------------------------------------------

#ifndef TA_HEAPSORT_H
#define TA_HEAPSORT_H

template <class Item>
class HeapSort
{
public:
    static void DoHeapSort(Item* pList, int nSize)
    {
        HeapSort(pList, nSize);
    }

private:

    Item* m_pList;
    int m_nSize;
    
    HeapSort(Item* pList, int nSize)
    {
        m_pList = pList;
        m_nSize = nSize;

        // Build heap
        for (int i = (m_nSize >> 1) - 1; i >= 0; i--)
            DownHeap(i);

        // Sort
        while (m_nSize > 1)
        {
            m_nSize--;
            Swap(0, m_nSize);
            DownHeap(0);
        } 
    }

    void DownHeap(int i)
    {
        int j = (i << 1) + 1; 
        while (j < m_nSize)
        {
            if (j + 1 < m_nSize)
            {
                if (m_pList[j + 1].value > m_pList[j].value) 
                    j++;
            }
            if (m_pList[i].value >= m_pList[j].value) 
                return; 
            Swap(i, j);
            i = j;
            j = (i << 1) + 1;
        }
    }

    void Swap(int i, int j)
    {
        Item tmpItem = m_pList[i];
        m_pList[i] = m_pList[j];
        m_pList[j] = tmpItem;
    }
};


#endif // TA_HEAPSORT_H

---

© Copyright 2004-2006 TRUE AXIS PTY LTD Australia. All rights reserved.