Jump to content
  • Advertisement

Archived

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

Smack0007

Quick Sort Question

This topic is 5357 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
Advertisement
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

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
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?

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!