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

  • This white paper presents a handful of short stories about application programming interface (API) providers that have changed how we think about the industries they serve. They have built distributed ecosystems of thousands of trusted partners and developers, and invented entirely new industries and business models. Their data, content, and other digital assets have become part of the fabric of how we do business and govern in 2015. Read this white paper to learn how this simple, open technology has the …

  • Thanks to wide spread cloud hosting and innovations small businesses can meet and exceed the legacy systems of goliath corporations. Explore the freedom to work how you want, with a phone system that will adapt to your evolving needs and actually save you lots of expense—read Get an Enterprise Phone System without High Cost and Complexity. The article clearly illustrates: The only hardware you'll need is phone equipment for advanced voice and fax. How to join all your employees, mobile devices, …

Most Popular Programming Stories

More for Developers

RSS Feeds

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