Quick sort algorithm

Joined
Jun 29, 2022
Messages
28
Reaction score
0
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[0]="1994," and copyOfWords[1]="a," then hash[0]=549456039 and hash[1]=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
 
Joined
Sep 21, 2022
Messages
156
Reaction score
22
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)
 

Ask a Question

Want to reply to this thread or ask your own question?

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.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,920
Messages
2,570,038
Members
46,449
Latest member
onedumbsquirrel

Latest Threads

Top