dcsimg

Quick Sort Algorithm Comparing Any Data Type

WEBINAR:
On-Demand

Application Security Testing: An Integral Part of DevOps


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

  • Uh, no.

    Posted by Legacy on 08/08/2003 12:00am

    Originally posted by: HlpMe

    Uh, no. You should rethink what is means to be a "good programmer".

    Anyway, this is much better:
    http://www.codeguru.com/listview/sort_on_col_click.shtml

    Reply
  • what is OGPuiODListCtrl ?

    Posted by Legacy on 04/28/2003 12:00am

    Originally posted by: hotdog

    The are many errors when comping the file.
    such as:
    F:\Project\VC\new\HFTP\ctrlext.cpp(32) : error C2653: 'OGPuiODListCtrl' : is not a class or namespace name

    Reply
  • Thanks!

    Posted by Legacy on 09/25/2001 12:00am

    Originally posted by: Jungle Lee

    Your perfect code ought to be contained in the MS CListCtrl class.
    

    Reply
  • Sorting Image items

    Posted by Legacy on 12/29/1999 12:00am

    Originally posted by: Tony D. Abel

    I added the following code to handle Images.
    
    

    /******************************************************
    **
    ** This function will partition the CListCtrl array.
    **
    ** TDA
    */

    int CSortListCtrl::Partition( int iStartPosition, int iEndPosition )
    {

    CString TempStr;
    CString ItemStr = GetItemText( iStartPosition, m_iSortedColumn );

    LVITEM TempItem;
    LVITEM CurrentItem;

    // clear structs
    memset( &TempItem, 0, sizeof( LVITEM ) );
    memset( &CurrentItem, 0, sizeof( LVITEM ) );

    // setup parameters to set image data
    CurrentItem.mask = LVIF_IMAGE;
    CurrentItem.iImage = I_IMAGECALLBACK;
    CurrentItem.iItem = iStartPosition;
    GetItem( &CurrentItem );


    int iSortPositionStart = iStartPosition - 1;
    int iSortPositionStop = iEndPosition + 1;


    while( iSortPositionStart < iSortPositionStop )
    {

    if( m_iSortedColumn == ELECT_IMAGE )
    {
    do
    {
    iSortPositionStop--;

    TempItem.mask = LVIF_IMAGE;
    TempItem.iImage = I_IMAGECALLBACK;
    TempItem.iItem = iSortPositionStop;
    GetItem( &TempItem );

    }while( CompareBy( TempItem, CurrentItem, m_bSortAscending
    ? ELECTOPTYPE_GT : ELECTOPTYPE_LT ) );

    do
    {
    iSortPositionStart++;

    TempItem.mask = LVIF_IMAGE;
    TempItem.iImage = I_IMAGECALLBACK;
    TempItem.iItem = iStartPosition;
    GetItem( &TempItem );

    }while( CompareBy( TempItem, CurrentItem, m_bSortAscending
    ? ELECTOPTYPE_GT : ELECTOPTYPE_LT ) );
    }
    else
    {
    do
    {
    iSortPositionStop--;
    TempStr = GetItemText( iSortPositionStop,
    m_iSortedColumn );

    }while( CompareBy( TempStr, ItemStr, m_bSortAscending
    ? ELECTOPTYPE_GT : ELECTOPTYPE_LT ) );

    do
    {
    iSortPositionStart++;
    TempStr = GetItemText( iSortPositionStart,
    m_iSortedColumn );

    }while( CompareBy( TempStr, ItemStr, m_bSortAscending
    ? ELECTOPTYPE_LT : ELECTOPTYPE_GT ) );
    }

    if( iSortPositionStart < iSortPositionStop )
    SwapRow( iSortPositionStart, iSortPositionStop );

    }

    return iSortPositionStop;
    }


    Overload the CompareBy() function. A function template will also work nicely.

    /******************************************************
    **
    ** This function will compare the TempItem image and
    ** CurrentItem image the partition function sends down.
    **
    ** TDA
    */

    BOOL CSortListCtrl::CompareBy( const LVITEM& TempItem,
    const LVITEM& CurrentItem,
    LISTOPERATORTYPEenum kOperatorType )
    {

    BOOL bReturn = FALSE;

    switch( m_kCompareAs )
    {
    case ELECT_IMAGE:
    {
    int iIntVal1 = TempItem.iImage;
    int iIntVal2 = CurrentItem.iImage;

    if( kOperatorType == ELECTOPTYPE_LT )
    {
    bReturn = ( iIntVal1 < iIntVal2 );
    break;
    }
    else if( kOperatorType == ELECTOPTYPE_GT )
    {
    bReturn = ( iIntVal1 > iIntVal2 );
    break;
    }
    else if( kOperatorType == ELECTOPTYPE_LTE )
    {
    bReturn = ( iIntVal1 <= iIntVal2 );
    break;
    }
    else if( kOperatorType == ELECTOPTYPE_GTE )
    {
    bReturn = ( iIntVal1 >= iIntVal2 );
    break;
    }
    else
    {
    bReturn = ( iIntVal1 == iIntVal2 );
    break;
    }
    }

    // Should never get here
    default:
    ASSERT(0);
    }

    return bReturn;
    }

    Reply
  • Two small corrections

    Posted by Legacy on 10/07/1999 12:00am

    Originally posted by: Shekar Venkatappa

    Method ::SwapRows(...)

    This method does not return TRUE on success. Variable bOk is updated to do so.

    Platform: NT
    In Message mapping

    ON_NOTIFY(HDN_ITEMCLICKA, 0, OnHeaderClicked)
    ON_NOTIFY(HDN_ITEMCLICKW, 0, OnHeaderClicked)

    works better( for sure) than

    ON_NOTIFY(HDN_ITEMCLICK, 0, OnHeaderClicked)


    Reply
  • You must have javascript enabled in order to post comments.

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

Top White Papers and Webcasts

  • Discover the best practices from HPE’s IT Advisory Consulting Services for migrating and transforming applications in Hybrid IT by capitalizing on innovative platforms, modern application architectures, agile development tools and proven methodologies. There are a number of challenges our customers face when migrating and transforming applications for a Hybrid IT environment. This guide provide proven strategies and application approaches that can help them understand and reduce risks and complexity.

  • CEOs, CIOs, boards and shareholders are demanding digital transformation. They want their organizations to be more customer-focused, competitive and strategic to increase revenue. Data drives all of those aspects. A great first step in optimizing data use is moving data to the cloud. It can quickly show benefits. Here are six aspects of a cloud data management strategy that will help your organization more fully move, manage and use valuable data to successfully support digital transformation.

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date
×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.