CODEWITHSUNDEEP
ctextquicksort
Marius
Marius

Reputation: 9

quicksort code understanding

i have a quicksort code that is supposed to run on the text "B A T T A J U S" (ignore blanks). But i dont seem to understand the code that well. 

 void quicksort (itemType a[], int l, int r)
 {
    int i, j; itemType v;
    if (r>l)
    {
       v = a[r]; i = l-1; j = r;
       for (;;)
        {
           while (a[++i] < v);
           while (a[--j] >= v);
           if (i >= j) break;
           swap(a,i,j);
        }

        swap(a,i,r);
        quicksort(a,l,i-1);
        quicksort(a,i+1,r);

    }

 }

i can explain what i understand: the first if check if l < r which in this case it is since, s is greater than b. THen i get alittle confused: v is set to be equal to a[r], does this mean S? since S is all the way to the right? then l is set to outside the "array" since its -1. (so its undefined, i assume) then j is set to be equal to r, but is that the posision r? as in S?

I kinda dont understand what values are set to what, if the a[r] = the letter in the posision or the or anything else. Hopefully some1 can explain me how the first swap works, so i hopefully can learn this?

Upvotes: 1

Views: 172

Answers (3)

rtm
rtm

Reputation: 81

I can't offer a solution in that exact form. That code is overly complicated in my thinking.

Also not sure if what I'm proposing is a bubble sort, or modified bubble, but to me just easier. My added comment is that quicksort() is calling itself, therefore it is recursive. Not good in my book for something as simple as a sort. This all depends on what you need for size and efficiency. If you're sorting many terms, then my proposed sort is not the best.

for(i = 0; i < (n - 1); i++) {
    for(j = (i + 1); j < n; j++) {
        if(value[i] > value[j]) {
            tmp = value[i];
            value[i] = value[j];
            value[j] = tmp;
        }
    }
}

Where

  • n is the number of total elements.
  • i, j, and tmp are integers
  • value[] is an array of integers to sort

Upvotes: 0

Mad Physicist
Mad Physicist

Reputation: 114290

Quick sort works by separating your array into a "left" subarray which contains only values stricly less than an arbitrarily chosen a pivot value and a "right" subarray that contains only elements that are greater than or equal to the pivot. Once the array has been divided like this, each of the two subarrays are sorted using the same algorithm. Here is how this applies to your code:

v = a[r] sets the pivot value to the last element in the array. This works well since the array is presumably unsorted to begin with, so a[r] is as good a value as any.

while(a[++i] < v) ; keeps stopping at the first element of the left sub-array that is greater than or equal to the pivot, v. When this loop ends, i is the index of an element that should be in the right sub-array rather than the left.

while(a[--j] >= v) ; does the same thing, except that it stops at the last element of the right sub-array that is strictly less than the pivot, v. When this loop ends, j is the index of an element that should be in the left sub-array rather than the right.

Whenever we find a pair of elements that are in the wrong sub-arrays, we swap them.

When all of the elements in the array are sorted (i meets j), we swap the pivot with the element at index i (which is now guaranteed to be in the right sub-array).

Since the pivot is guaranteed to be in the right position (left sub-array is strictly less and right sub-array is greater than or equal), we need to sort the sub-arrays but not the pivot. That is why the recursive calls use indices l,i-1 and i+1,r, leaving the pivot at index i.

Upvotes: 1

John Bollinger
John Bollinger

Reputation: 180181

It is probably better to start with an understanding of the QuickSort algorithm, and then see how the code corresponds to it, than to study the code to try to figure out how QuickSort works. Basic QuickSort (which is what you have) is in fact a pretty simple algorithm. To sort an array A:

  1. If the length of A is less than 2 then the array is already sorted. Otherwise,
  2. Select any element of A to be a "pivot element".
  3. Rearrange the other elements as needed so that all those that are less than the pivot are at the beginning of A, and those that are greater than or equal to the pivot are at the end. (This particular version also puts the pivot itself between the two, which is common but not strictly necessary; it could simply be included in the upper subarray, and the algorithm would still work.)
  4. Apply the QuickSort procedure to each of the two sub-arrays produced by (3).

Your particular code chooses the right-most element of each (sub)array as the pivot element, and at step (4) it excludes the pivot from the sub-arrays to be recursively sorted.

Upvotes: 1

Related Questions