# 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

```
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)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
//////////////////////////////////////////////////////////////////////
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.
//////////////////////////////////////////////////////////////////////
{
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
{
//Return the number of items in it (i.e. the number of columns)
}
//////////////////////////////////////////////////////////////////////
// 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 |
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;
}
```