Explanation of this quicksort please?

[Tset Tsyung]

Hi there,

I don't want to waste the time of everyone with an incorrect post but...

If I was to display a quicksort example that comes from Herbert Schildt's book "C++ a beginners guide" would anyone be able to help me understand it?

I've come across it whilst reading into recursion... but there are parts that just confuse me!

If I can post it let me know - of course if this has been covered elsewhere please let me know as well, lol.

So, can I post the example and ask for an explanation?

Mike

[Bo Pace]

Go for it. Post the code. :)

[Tset Tsyung]

Many thanks ;)

My questions are pretty much in the comments of the code section... can't think of anymore RIGHT now, lol.

Many thanks!

// This function is simply the "interface" for the rest of the 
// users code
void recursive_sort(char* arraytosort, int len)
{
    // this is the starting call to the recursive function
    qs(arraytosort, 0, len-1);
}

void qs(char* items, int left, int right)
{
    int a, b;
    a = left, b = right;

    char x, y;
    // this take the boundaries that were passed and then
    // cuts the section in 2.
    //  But is this the numerical values of the first and
    // last characters added together then divided by 2
    // (Mean average)?  Or is it the positional value of the
    // elements?
    x = items[(left+right)/2];

    do
    {
        // 1) Is this "Keep incrementing the leftside pointer until
        // we find a character that should be above halfway point"?
        while((items[a] < x) && (a < b))
        {
            a++;
        }

        // 2) And then would this be "Decrement rightside pointer until we
        // find a character that should be below the halfway point"?
        while((x < items[b]) && (b > left))
        {
            b--;
        }

        // 3) therefore because these 2 characters are both on the wrong side
        // of the halfway line simply swap them? Is that right?
        // 4) But then what if B never found a suitable swapping character and
        // just hit the x/mid point?
        // Do we just swap anyway?
        // and when it say "A <= B" is it referencing the positions of the pointers
	// or the numerical values of the character they are pointing to?
        if(a <= b)
        {
            y = items[a];
            items[a] = items[b];
            items[b] = y;
            a++;
            b--;
        }
    // This part I understand "Keep doing the above until the pointers meet"!
    // 5) Except if B doesn't get reset, how can it carry on? Won't just stop
    // at x/mid point again and have the same problem from my last question (Q4)?
    }while(a <= b);

    // 6) this will keep calling the function, each call reduces the
    // partition in a leftward-direction fashion, continually swapping?
    if(left < b) qs(items, left, b);

    // 7) once the above recursion has been exhausted it does the same
    // again, only this way going to the right, continually swapping?
    if(a < right) qs(items, a, right);
}

[mgupta]

As for your very first question in line 17, it is the positional value of the elements.
Quicksort starts here by dividing the array into half irrespective of their numerical values.

Now in line 21, x gets the numerical value of the item halfway the array.

The objective is to put the numerically smaller items on the left side and greater on the right side by finding a pivot value.
So we find any item numerically bigger than halfway point in step 1 and numerically smaller than halfway value in step 2.

After dividing the array into two parts, we sort the parts individually and recursively and then join the two halves together.

So, if a smaller value is at a higher position as checked by question 3, we swap them.

For question 4, yes we swap because we have found a higher value than the halfway value in the left side of array. If b hits the mid point, that means that the halfway value is smaller than every value to the right and does not need to be swapped.

In question 5, I am not clear by what do you mean by b not being reset as it is a pointer which is kept moving. And as for stopping at mid point, there will be a new mid point on either side of the array sorted recursively.

Question 6 and 7 : answer is yes.

For a detailed explanation on quicksort, http://en.wikipedia.org/wiki/Quicksort

and

http://ww3.algorithmdesign.net/handouts/QuickSort.pdf

Hope this helps.

[Tset Tsyung]

Many thanks mgupta!

Don't worry about the question 5 - relised I was overlooking summit.

As for the answer to question 4 I'm still not clear on it. Consider the following.

The string is "abbaa|bbabb".

The "|" is to represent the midpoint.

First swap happens with the second and eighth characters meaning we then have "aabaa|bbbbb".

The left pointer is now looking at the third character whilst the right pointer now travels down to the midpoint looking for a suitable swap... but it can't! They all belong there!

So are we saying that once the right pointer reaches the last allowed character (in this case the sixth) even if the swap shouldn't take place (because they are the same) it will anyway? I ask because that's what the code looks like...

I apologise for it NOT QUITE sinking in... ;)

[mgupta]

See, we swap if we found a pair of values if any of the following conditions is true:
- value left from the midpoint is greater than midpoint
- value right from midpoint is lesser than midpoint

the do-while loop keeps on swapping for once till the left pointer and right pointer meet each other.
By this time there is no value left to the left pointer which is greter than the midpoint value.

This also means we get the new point a = b, from where all the smaller values are to the left and greater values to the right. Now, we split these two sets of lesser and greater values and sort again.

The example you took is difficult to explain as it contains many duplicates. (And I am quite bad at explaining).
But still, let us take it step by step.

First the array is abbaabbabb. The mid point is the fifth character (a).
Here, first item (a) is not "less than mid" (a), but first item "greater than mid" (a) is found at eight position (b).
So we swap first and eighth character, not second and eight character.
So, now the array is abbaababb

Now the next "greater than mid" character is second (b) and "less than mid" character is fifth (a).
Now we swap the second and fifth character making the array as aababbbabb.

Now the next "greater than mid" character is third (b) and "less than mid" character is fourth (a).
Now we swap the second and fifth character making the array as aaabbbbabb.

Now the next "greater than mid" character is fourth (b) and "less than mid" character is third (a).
This completes the first walk throught the array.

But this violates the condition in line 57 that means to execute till we have completed 1 iteration.

So now we split the array as two arrays -
First from first to third character
Second from fourth to last character.

Now, we sort the two arrays recursively resulting in all the "less than mid" values to the left and "greater than mid" values to the right of the midpoint.

--------------------------------------------------------------------------------------------------------------

I suggest to take an array of numbers rather than characters and print the array and when it is swapped to see the working.

Hope it helped.

P.S. Dont apologize for not getting it. If you ever need to, then apologize for not trying to.