Archived

This topic is now archived and is closed to further replies.

Quick Sort Question

This topic is 5047 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Here it is:


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]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites

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]

Share this post


Link to post
Share on other sites