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:

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;
}


Comments

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: September 10, 2014 @ 11:00 a.m. ET / 8:00 a.m. PT Modern mobile applications connect systems-of-engagement (mobile apps) with systems-of-record (traditional IT) to deliver new and innovative business value. But the lifecycle for development of mobile apps is also new and different. Emerging trends in mobile development call for faster delivery of incremental features, coupled with feedback from the users of the app "in the wild". This loop of continuous delivery and continuous feedback is …

  • Learn how cloud-based master data management (MDM) empowers your fast-paced business to get the right data to the right place in real time, so you can remain competitive and agile.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds