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

More by Author

Must Read