Quick Sort Algorithm Comparing Any Data Type

I wanted a way to sort any column in a CListCtrl, so I came to CodeGuru.com to get some ideas (and possible a solution) to solve my problem. Unfortunately, I had troubles understanding and getting some of the sorting examples to function. So did what any good programmer does. I took some code and attempted to improve upon it.

What I have come up with is my solution for using the quick sort alogrithm so that you can sort by any column of any data type.

Acknowledgements:

• Indicating sort order in header control - by Zafir Anjum
• Sorting the list when user clicks on column header - by Zafir Anjum
• CSortedListCtrl reuseable base class - by Staffe Christian

Source code:

I am only showing the relavent code to add into your derived CListCtrl class header and implementation files.

enum ListCompareType {  ELCT_INTEGER = 0,
ELCT_DOUBLE,
ELCT_STRING_CASE,
ELCT_STRING_NOCASE };
enum ListOperatorType { ELOT_LT = 0,    //  <   less than
ELOT_GT,  //  >   greater than
ELOT_LTE, //  <=  less than or equal
ELOT_GTE, //  >=  greather than or equal
ELOT_EQ}; //  ==  equal
class CMyListCtrl  : public CListCtrl
{
//////////////////////////////////////////////////////////////////////
// Constructors and Deconstructors
//////////////////////////////////////////////////////////////////////
..
//////////////////////////////////////////////////////////////////////
// Operations
//////////////////////////////////////////////////////////////////////
public:
BOOL SwapRow(int nRow1, int nRow2);
int GetColumnCount() const;
protected:
void QuickSort(int p, int r);
int Partition(int p, int r);

//////////////////////////////////////////////////////////////////////
// Overridables
//////////////////////////////////////////////////////////////////////
public:
virtual void Sort();
virtual void Sort(int nColumn, BOOL bAscending, ListCompareType
nCompareAs);
protected:
virtual BOOL CompareBy(CString str1, CString str2, ListOperatorType
op);
//////////////////////////////////////////////////////////////////////
// Message Maps
//////////////////////////////////////////////////////////////////////
protected:
//{{AFX_MSG(OGPuiODListCtrl)
afx_msg void OnHeaderClicked(NMHDR* pNMHDR, LRESULT* pResult);
//}}AFX_MSG
//////////////////////////////////////////////////////////////////////
// Attributes
//////////////////////////////////////////////////////////////////////
protected:
//sorting attributes
int m_nSortedColumn;
BOOL m_bSortAscending;
ListCompareType m_nCompareAs;
};
CMyListCtrl::CMyListCtrl() : CListCtrl(),
m_nSortedColumn(-1),
m_bSortAscending(TRUE),
m_nCompareAs(ELCT_STRING_CASE)
{
}
//////////////////////////////////////////////////////////////////////
// Message Maps
//////////////////////////////////////////////////////////////////////
BEGIN_MESSAGE_MAP(OGPuiODListCtrl, CListCtrl)
//{{AFX_MSG_MAP(OGPuiODListCtrl)
ON_NOTIFY(HDN_ITEMCLICK, 0, OnHeaderClicked)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
//////////////////////////////////////////////////////////////////////
// OnHeaderClicked()
// Parameters:  pNMHDR  - Contains information about a notification
message.
//        LRESULT - Contains the result from the message
// Action:     Sort the column that the user clicks on. If it is not
//        the same column as the last sorting then sorting ascending.
//        If is the same column then toggle the sorting style. The
//        list only recieves this message if the "no sort header" is
//        NOT checked in the resource.
// Returns:    Nothing.
//////////////////////////////////////////////////////////////////////
void OGPuiODListCtrl::OnHeaderClicked(NMHDR* pNMHDR, LRESULT* pResult)
{
HD_NOTIFY *phdNotify = (HD_NOTIFY *)pNMHDR;
if (phdNotify->iButton == 0)
{
m_bSortAscending = (phdNotify->iItem == m_nSortedColumn) ?
!m_bSortAscending : TRUE;
m_nSortedColumn = phdNotify->iItem;
Sort();
}
*pResult = 0;
}
//////////////////////////////////////////////////////////////////////
// Sort()
// Parameters:  None.
// Action:      This function is called when the user clicks on a column
//              header. Derived classes should override this function
//              if they want to change the m_nCompareAs based on the
//              the column that was selected.
// Returns:     Nothing.
//////////////////////////////////////////////////////////////////////
void OGPuiODListCtrl::Sort()
{
Sort(m_nSortedColumn, m_bSortAscending, m_nCompareAs);
}
//////////////////////////////////////////////////////////////////////
// Sort()
// Parameters:  nColumn - column to sort by
//              bAscending - TRUE ascending sort, FALSE descending
//              nCompareAs - How to compare the values as
// Action:      Set all the sorting attributes then do a quick sort
//              on the whole list. Derived class may want to override
//              this if they want to use a different sort algorithm or
//              want to use a different range
// Returns:     Nothing.
//////////////////////////////////////////////////////////////////////
void OGPuiODListCtrl::Sort(int nColumn, BOOL bAscending, ListCompareType
nCompareAs)
{
m_nSortedColumn = nColumn;
m_bSortAscending = bAscending;
m_nCompareAs = nCompareAs;
QuickSort(0, GetItemCount() - 1);
}
//////////////////////////////////////////////////////////////////////
// QuickSort()
// Parameters:  p - start position, usually index 0
//              q - end position, usually last index
// Action:      Standard quick sort algorthim
// Returns:     Nothing.
//////////////////////////////////////////////////////////////////////
void OGPuiODListCtrl::QuickSort(int p, int r)
{
if (p < r)
{
int q = Partition(p, r);
QuickSort(p, q);
QuickSort(q + 1, r);
}
}
//////////////////////////////////////////////////////////////////////
// Partition()
// Parameters:  p - start position
//              q - end position
// Action:      Partition of the array in the quick sort algorithm
// Returns:     Nothing.
////////////////
int CMyListCtrl::Partition(int p, int r)
{
    CString tmp;
    CString x = GetItemText( p, m_nSortedColumn);
    int i = p - 1;
    int j = r + 1;

    while (i < j)
    {
        do
        {
            j--;
            tmp = GetItemText(j,  m_nSortedColumn);
        } while (CompareBy(tmp, x, m_bSortAscending ? ELOT_GT :   
ELOT_LT));

        do
        {
            i++;
            tmp = GetItemText(i, m_nSortedColumn);
        } while (CompareBy(tmp, x, m_bSortAscending ? ELOT_LT :   
ELOT_GT));

        if (i < j)
        {
            SwapRow(i, j);
        }
    }

    return j;
}

//////////////////////////////////////////////////////////////////////
// CompareBy()
// Parameters:  str1 - string 1 (left operand)
//              str2 - string 2 (right operand)
//              op - operator type
// Action:      Convert strings to new data type based on m_nCompareAs'
//              value. Compare the strings using the operator.
// Returns:     The result of (str1 op str2)
//////////////////////////////////////////////////////////////////////
BOOL CMyListCtrl::CompareBy(CString str1, CString str2, ListOperatorType   
op)
{
    BOOL bReturn = FALSE;

    switch (m_nCompareAs)
    {
        case ELCT_INTEGER:
        {
            int val1 = atoi(str1);
            int val2 = atoi(str2);

            if (op == ELOT_LT)
                bReturn =  (val1 < val2);
            else if (op == ELOT_GT)
                bReturn =  (val1 > val2);
            else if (op == ELOT_LTE)
                bReturn =  (val1 <= val2);
            else if (op == ELOT_GTE)
                bReturn =  (val1 >= val2);
            else
                bReturn =  (val1 == val2);
            break;
        }
        case ELCT_DOUBLE:
        {
            double val1 = atof(str1);
            double val2 = atof(str2);

            if (op == ELOT_LT)
                bReturn =  (val1 < val2);
            else if (op == ELOT_GT)
                bReturn =  (val1 > val2);
            else if (op == ELOT_LTE)
                bReturn =  (val1 <= val2);
            else if (op == ELOT_GTE)
                bReturn =  (val1 >= val2);
            else
                bReturn =  (val1 == val2);
            break;
        }
        case ELCT_STRING_NOCASE:
        {
            str1.MakeUpper();
            str2.MakeUpper();
        }
        case ELCT_STRING_CASE:
        default:
        {
            if (op == ELOT_LT)
                bReturn =  (str1 < str2);
            else if (op == ELOT_GT)
                bReturn =  (str1 > str2);
            else if (op == ELOT_LTE)
                bReturn =  (str1 <= str2);
            else if (op == ELOT_GTE)
                bReturn =  (str1 >= str2);
            else
                bReturn =  (str1 == str2);
            break;
        }
    }

    return bReturn;
}

//////////////////////////////////////////////////////////////////////
// GetColumnCount()
// Parameters:  None.
// Action:
// Returns:     The number of columns in the list control
//////////////////////////////////////////////////////////////////////
int CMyListCtrl::GetColumnCount() const
{
    //Get the header control
    CHeaderCtrl* pHeader = (CHeaderCtrl*)GetDlgItem(0);

    //Return the number of items in it (i.e. the number of columns)
    return pHeader->GetItemCount();
}

//////////////////////////////////////////////////////////////////////
// SwapRow()
// Parameters:  nRow1 - row index (zero based)
//              nRow2 - row index (zero based)
// Action:      Swap nRow1 with nRow2
// Returns:     TRUE if successful, else FALSE
//////////////////////////////////////////////////////////////////////
BOOL CMyListCtrl::SwapRow(int nRow1, int nRow2)
{
    BOOL bOk = FALSE;
      

    int nMaxRows = GetItemCount();

    if ((nRow1 >= 0) && (nRow1 < nMaxRows) &&
        (nRow2 >= 0) && (nRow2 < nMaxRows) &&
        (nRow1 != nRow2))
    {
        int nMaxColumns = GetColumnCount();

        //swap rows
        LV_ITEM lvItem1, lvItem2;

        //hold all text for a single row
        CStringArray rowText;
        rowText.SetSize(nMaxColumns);

        //save all the text in row
        for(int i = 0; i < nMaxColumns; i++)
        {
            rowText[i] = GetItemText(nRow1, i);
        }

        //setup parameters to get item data
        lvItem1.mask = LVIF_IMAGE | LVIF_PARAM | LVIF_STATE;
        lvItem1.iItem = nRow1;
        lvItem1.iSubItem = 0;
        lvItem1.stateMask = LVIS_CUT | LVIS_DROPHILITED |
                             LVIS_FOCUSED | LVIS_SELECTED |
                             LVIS_OVERLAYMASK | LVIS_STATEIMAGEMASK;
        lvItem2 = lvItem1;
        lvItem2.iItem = nRow2;

        //get item data
        GetItem(&lvItem1);
        GetItem(&lvItem2);

        //set the text for the lo (left)
        for(i = 0; i < nMaxColumns; i++)
        {
            SetItemText(nRow1, i, GetItemText(nRow2, i));
        }

        lvItem2.iItem = nRow1;
        SetItem(&lvItem2);

        for(i = 0; i < nMaxColumns; i++)
        {
            SetItemText(nRow2, i, rowText[i]);
        }

        lvItem1.iItem = nRow2;
        SetItem(&lvItem1);
    }

    return bOk;
}