flipcode - QuickSort Routine

QuickSort Routine
Submitted by

Recently I needed a quicksort routine that would allow me to sort based on multiple factors. Previously in our projects the runtime library function qsort was used to do a quicksort, but it has limitations:

1. It requires a static callback function (not very oop friendly)
2. If you wanted to sort based off of differing details then either multiple functions (a pain and messy) or static data (not very oop friendly and also not thread-safe) were required.

So I created the following template:

    template <class T struct TQuickSort
    {
        virtual bool OnSortItem(T & aItem1, T & aItem2) = NULL;

        void Sort(T * pData, Slong nFirst, Slong nLast)
        {
            if (nFirst < nLast)
            {
                T & aItem = pData[nLast];
                Slong nLeft = nFirst - 1;
                Slong nRight = nLast;

                while (true)
                {
                    while (OnSortItem( pData[++nLeft], aItem ))
                    {
                        if (nLeft = nLast)
                        {
                            break;
                        }
                    }

                    while (OnSortItem( aItem, pData[--nRight] ))
                    {
                        if (nRight <= nFirst)
                        {
                            break;
                        }
                    }

                    if (nLeft = nRight)
                    {
                        break;
                    }

                    swap( pData[nLeft], pData[nRight] );
                }

                swap( pData[nLeft], pData[nLast] );

                Sort( pData, nFirst, nLeft - 1 );
                Sort( pData, nLeft + 1, nLast );
            }
        }
    };

Then you could derive a class from this template, pass the now thread-safe, oop friendly data to the class, and then override the OnSortItem function (this example shows how a multicolumn tree control could use this):

    struct TQuickSortAscending : public TQuickSort<TVarTreeItem *
    {
        TQuickSortAscending(CVarTreeCtrl * pVarTreeCtrl) { m_pVarTreeCtrl = pVarTreeCtrl; }

        virtual bool OnSortItem(TVarTreeItem *& pTreeItem1, TVarTreeItem *& pTreeItem2)
        {
            return m_pVarTreeCtrl-OnSortItem( pTreeItem1, pTreeItem2,
                                               m_pVarTreeCtrl-GetHeader().GetSortColumn() );
        }

        CVarTreeCtrl * m_pVarTreeCtrl;
    };

Of course adding another template to our libraries might have given our PS2 programmers a coronary so I decided to see if all this could be done without the use of templates. So I created the following class:

    // In TQuickSort.h
    struct TQuickSortImpl
    {
    public:
        TQuickSortImpl(Slong nSize);
        ~TQuickSortImpl();

        virtual bool OnSortItemImpl(Byte * pItem1, Byte * pItem2) = NULL;

        void SwapImpl(Byte * pItem1, Byte * pItem2);
        void SortImpl(Byte * pData, Slong nFirst, Slong nLast);

    protected:
        Slong m_nSize;
        Byte * m_pTemp;
    };

    and:

    // In TQuickSort.cpp
    TQuickSortImpl::TQuickSortImpl(Slong nSize)
    {
        m_nSize = nSize;
        m_pTemp = new Byte[m_nSize];
    }

    TQuickSortImpl::~TQuickSortImpl()
    {
        delete m_pTemp;
    }

    void TQuickSortImpl::SwapImpl(Byte * pItem1, Byte * pItem2)
    {
        ::MemCpy( m_pTemp, pItem1, m_nSize );
        ::MemCpy( pItem1, pItem2, m_nSize );
        ::MemCpy( pItem2, m_pTemp, m_nSize );
    }

    void TQuickSortImpl::SortImpl(Byte * pData, Slong nFirst, Slong nLast)
    {
        if (nFirst < nLast)
        {
            Byte * pItem = &pData[nLast * m_nSize];
            Slong nLeft = nFirst - 1;
            Slong nRight = nLast;

            while (true)
            {
                while (OnSortItemImpl( &pData[++nLeft * m_nSize], pItem ))
                {
                    if (nLeft = nLast)
                    {
                        break;
                    }
                }

                while (OnSortItemImpl( pItem, &pData[--nRight * m_nSize] ))
                {
                    if (nRight <= nFirst)
                    {
                        break;
                    }
                }

                if (nLeft = nRight)
                {
                    break;
                }

                SwapImpl( &pData[nLeft * m_nSize], &pData[nRight * m_nSize] );
            }

            SwapImpl( &pData[nLeft * m_nSize], &pData[nLast * m_nSize] );

            SortImpl( pData, nFirst, nLeft - 1 );
            SortImpl( pData, nLeft + 1, nLast );
        }
    }

Of course I then proceeded to add the following wrapper template (couldn't resist):

    // In TQuickSort.h
    template <class T struct TQuickSort : public TQuickSortImpl
    {
        TQuickSort() : TQuickSortImpl( sizeof( T ) ) { }

        virtual bool OnSortItem(T & aItem1, T & aItem2) = NULL;
        void Sort(T * pData, Slong nFirst, Slong nLast)
        { SortImpl((Byte *) pData, nFirst, nLast ); }

    protected:
        virtual bool OnSortItemImpl(Byte * pItem1, Byte * pItem2)
        { return OnSortItem( (T &) *pItem1, (T &) *pItem2 ); }
    };

The non-template class can take up less memory and has the added benefit of likely being faster for larger data. The reason it should be faster is that the ::MemCpy and extra function calls will generally be faster when compared to possible operator= overload where the elements of a struct might try to copy themself.