# Quick sort algorithm

#### Onam

I'm attempting to create a rapid sort that sorts integers and phrases depending on their numerical worth. I can't figure out how to make the following code operate properly.

C++:
``````if (high!=low&& high>low)//compares hashes and finds the number in the middle. swaps hashes and corresponding words
{

long one=hash[low];
long two=hash[high];
long three = hash[high/2];
if((one<=two&&one>=three)||(one<=three&&one>=two))
{
swap(hash[low], hash[high]);
swap(copyOfWords[low], copyOfWords[high]);
}
else if((three<=one&&three>=two)||(three<=two&&three>=one))
{

swap(hash[high/2], hash[high]);
swap(copyOfWords[high/2], copyOfWords[high]);
}
else
{

}
int i=low;
int j=high-1;
while(i!=j&&i<j)
{

while(hash[i]<hash[high]&&i<j)// find higher numbers and lower numbers then the middlle and swaps them
{
i++;
}
while(hash[j]>hash[high]&&i<j)
{
j--;
}
if(i==j||i>j)
{
}
else
{
swap(hash[i],hash[j]);
swap(copyOfWords[i],copyOfWords[j]);
i++;
j--;
}
}
swap(hash[i],hash[high]);
swap(copyOfWords[i], copyOfWords[high]);

quickSort(low, j-1);//recursive
quickSort(j+1, high);

}

}``````

I know the values in hash and copyOfWords are accurate after reading this post since shell sort sorts them correctly. For example, if there are two words, copyOfWOrds="1994," and copyOfWords="a," then hash=549456039 and hash=197000000, but the sort places them as a 1994, a rather than a 1994,. With additional components, it produces greater complications. Any assistance would be much appreciated.
Thanks

#### WhiteCube

Put the pivot value, in a variable called pivot.

consider the case when low=100 and high=180

high/2 = 90 (out of range)

Looks like you're trying to do a median of 3 pivot.

Use 3 RANDOM positions from low to high.

Randomness ensures that if the worst-case performance happens, it is very unlikely to happen again the next time the program runs.
Code:
``````Compute the median of A,B,C
by doing an insertion sort.

pseudocode:

IF C<B
SWAP C,B
IF B<A
SWAP A,B
IF C<B
SWAP C,B

median is B``````

To make the logic easier to read, and to make i and j more meaningful, at any time, these two statements are true:

hash[low to i] <= pivot
hash[j to high] >= pivot

initialise
i = low - 1
j = high + 1

Note: hash[low to low-1] has length 0

swap when hash[i+1]>=pivot and hash[j-1]<=pivot

The = is important, so that when a lot of the data has the same value as pivot, roughly half goes left, and roughly half goes right.

IF i+1 = j THEN the partition is done, exit.

IF i+1 = j-1 THEN they're both pointing to the same pivot, no need to swap, inc i (or dec j), exit.

Now recurse.

IF low < i THEN quicksort(low,i)

IF j < high THEN quicksort(j,high)

IF high-low is small THEN the quicksort should call a non recursive sort instead of pivoting.

By the way, the condition (i!=j&&i<j) is the same as (i<j)

• Ian

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

### Members online

No members online now.