#### Archived

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

# 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.

## 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 on other sites
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 on other sites
From the abundant details you have provided in your post, I can tell you''ve implemented bogo-sort.

##### 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 on other sites
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 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 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 on other sites
I got it after a few hours and working it out on a piece of paper. Thanks for all of your input.

1. 1
Rutin
45
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 11
• 15
• 9
• 10
• 13
• ### Forum Statistics

• Total Topics
633004
• Total Posts
3009841
• ### Who's Online (See full list)

There are no registered users currently online

×