Quick Sort Algorithm Comparing Any Data Type 

General: 

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;

}