Quick Sort Question
Author
This question might be stupid but I can''t find the answer to it anywhere. I''ve written a quicksort routine that sorts a linked list of objects. Sometimes the data is sorted completely and sometimes it is not, it all depends on how the numbers fall. I can run the function twice though and that usually seems to clear it right up. Is this normal or am I doing something wrong. I''ve never done a quick sort so I honestly have no idea.
Its not normal, Quick Sort completely sorts the array just like any other sorting algo i''ve come across. Perhaps you could post your code here and i''m sure someone will point out your problem.
-CProgrammer
-CProgrammer
Author
Here it is:
I know for a fact that everything besides this function in particular is working fine, I have a bubble sort function and it works very effectively. Also, I know this is very unoptimized.
[edited by - Smack0007 on February 22, 2004 2:01:19 PM]
[edited by - Smack0007 on February 22, 2004 3:33:50 PM]
template<class T>void CLinkedList<T>::QuickSort(bool Compare(T *Item1, T *Item2), int low, int high){ if(low == -1 && high == -1) { low = 0; high = m_numItems - 1; } if(low < 0 || high < 0 || low > (int)(m_numItems - 1) || high > (int)(m_numItems - 1) || low == high) return; unsigned int pivot = low; unsigned int up = low; unsigned int down = high; if(up<down) { if(high == low+1) { if(Compare(GetItemInPos(low), GetItemInPos(high))) { SwapItems(low, high); return; } } while(up<down) { while((!Compare(GetItemInPos(up), GetItemInPos(pivot))) && (up<down)) up++; while((Compare(GetItemInPos(down), GetItemInPos(pivot))) && (up<down)) down--; if(up<down) SwapItems(up, down); up++; down--; } SwapItems(pivot, down); if((unsigned int)low<down) QuickSort(Compare, low, down-1); if((unsigned int)high>down) QuickSort(Compare, down+1, high); }}I know for a fact that everything besides this function in particular is working fine, I have a bubble sort function and it works very effectively. Also, I know this is very unoptimized.
[edited by - Smack0007 on February 22, 2004 2:01:19 PM]
[edited by - Smack0007 on February 22, 2004 3:33:50 PM]
Use [ source ] tags. Some of your code is being munged. Also note that for lists you should use mergesort because quicksort requires random access whereas mergesort requires access only to the head.
while((!Compare(GetItemInPos(up), GetItemInPos(pivot))) && (up<down)) up++;while((Compare(GetItemInPos(down), GetItemInPos(pivot))) && (up<down)) down--;Negating the result of a test changes a strict comparison (< or >) into a loose comparison (≥ or ≤).
[edited by - Fruny on February 22, 2004 5:58:11 PM]
Author
Would it be beneficail to change Compare to an int return function so I could return -1 if less then, 0 if equal, and 1 if greater than?
Author
I got it after a few hours and working it out on a piece of paper. Thanks for all of your input.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement