Quick Sort Algorithm Comparing Any Data Type
Posted
by David Flores
on July 31st, 1999
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:
- Indicating sort order in header control - by Zafir Anjum
- Sorting the list when user clicks on column header - by Zafir Anjum
- CSortedListCtrl reuseable base class - by Staffe Christian
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:00amOriginally posted by: HlpMe
Uh, no. You should rethink what is means to be a "good programmer".
Anyway, this is much better:
Replyhttp://www.codeguru.com/listview/sort_on_col_click.shtml
what is OGPuiODListCtrl ?
Posted by Legacy on 04/28/2003 12:00amOriginally posted by: hotdog
The are many errors when comping the file.
Replysuch as:
F:\Project\VC\new\HFTP\ctrlext.cpp(32) : error C2653: 'OGPuiODListCtrl' : is not a class or namespace name
Thanks!
Posted by Legacy on 09/25/2001 12:00amOriginally posted by: Jungle Lee
Reply
Sorting Image items
Posted by Legacy on 12/29/1999 12:00amOriginally posted by: Tony D. Abel
Two small corrections
Posted by Legacy on 10/07/1999 12:00amOriginally 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)