• ### Popular Now

• 15
• 15
• 11
• 9
• 10

#### Archived

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

# Quicksort problem

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

## Recommended Posts

void sortFast( std::vector<Data> &v, int leftLimit, int rightLimit )
{
int pivot = leftLimit;
int i = leftLimit + 1;
int j = rightLimit;
int temp;
if ((rightLimit - leftLimit) >= 1)
{
while (j >= i)
{
while (v[i].number <= v[pivot].number && i < rightLimit)
i++;

while (v[j].number >= v[pivot].number && j > pivot)
j--;

if (i < j)
{
temp = v[i].number;
v[i].number = v[j].number;
v[j].number = temp;
}
else
{
temp = v[j].number;
v[j].number = v[pivot].number;
v[pivot].number = temp;
}
}

sortFast( v, leftLimit, (j - 1) );
sortFast( v, (j + 1), rightLimit );
}
}

Can someone tell me what's wrong with this quicksort algorithm? There is a slight amount of data that doesn't get sorted. [edited by - kelendil on September 23, 2003 10:25:03 PM]

##### Share on other sites
I''d hazzard a guess that...
sortFast( v, leftLimit, (j - 1) );sortFast( v, (j + 1), rightLimit );

...isn''t right.

You''ve stop sorting the element at location j.

##### Share on other sites
Hmm... I don''t sort the element at ''j'' because it is already sorted. All data to the left of it is smaller and all data to the right of it is greater.

##### Share on other sites
			if (i < j)			{				temp = v[i].number;				v[i].number = v[j].number;				v[j].number = temp;			}			else			{				temp = v[j].number;				v[j].number = v[pivot].number;				v[pivot].number = temp;			}

That part, along with other possible off-by-one errors, is wrong. You just want to swap the number field for v and v[j] at this point. You don''t want to change the value at the pivot index. Remember, the partition portion of this algorithm just moves values less than the value at the pivot index (v[pivot].number) to the left of the pivot index and values greater than the value at the pivot index to the right of the pivot index. It doesn''t impose any order on the values that are placed to the left or right. The partition algorithm only imposes the following rule:

n_i <= n_p for all i < p and n_j >= n_p for all j > p

This means the value at the pth index is sorted, although the rest of the array may not be. Recursion then takes over as sort(0, p-1) and sort(p+1, MAX) are called.