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: May 11, 2015 @ 1:00 p.m. ET / 10:00 a.m. PT One of the languages that have always been supported with the Intel® RealSense™ SDK (Software Developer Kit) is JavaScript, specifically so that web-enabled apps could be created. Come hear from Intel Expert Bob Duffy as he reviews his own little "space shooting" game where the orientation of your face controls the aiming reticle to help teach developers how to write apps and games in JavaScript that can use facial and gesture …

  • There has been growing buzz about DevOps. DevOps is a methodology that unites the often separate functions of software development (Dev) and production and operations (Ops) into a single, integrated, and continuous process. DevOps is about breaking down the barriers between Dev and Ops. It leverages people, processes, and technology to stimulate collaboration and innovation across the entire software development and release process. Dev and Ops should always be part of an integrated process, but that's not …

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date