quicksort logic?

[chiefsosa1]

hello,
i need to figure out what is going on step by step here, so if i were to be given a small list of roughly 10 numbers, i would be able to write them in how they would be after a couple loops through this quicksort function. here is the function:

template <class T>
int partition(vector<T>& set, int start, int end, bool (*compare)(const T&, const T&))
{
   int pivotIndex, mid;
   T pivotValue;

   mid = (start + end) / 2;

   T temp = set[start];
   set[start] = set[mid];
   set[mid] = temp;

   pivotIndex = start;
   pivotValue = set[start];

   for (int scan = start + 1; scan <= end; scan++)
      {
         if (compare(set[scan], pivotValue))
         {
            pivotIndex++;
            //pivotIndex and scan of the vector
            T newTemp = set[pivotIndex];
            set[pivotIndex] = set[scan];
            set[scan] = newTemp;
         }
      }

   T thirdTemp = set[start];
   set[start] = set[pivotIndex];
   set[pivotIndex] = thirdTemp;

   return pivotIndex;
}

[Duthomhas]

The goal of the partition function is this: given a predicate function, put every element for which the predicate returns true sequentially before every element for which the predicate returns false.

The predicate function works by comparing each element to a pivot value.

(Your predicate is expressed as a function call: compare( element, pivotValue ).)

So, let's assume for our purposes here that the predicate is true for any (x < pivot_value). Given a list like:

    2 6 4 1 3

We'll choose the middle element (index 2, value 4) as the pivot. Our partition function should then move every element < 4 to the left, and every element not < 4 to the right:

    2 1 3 4 6

Notice how the pivot's position (or index) moved? That happens.

Okay, not to work through your function:

template <class T>
int partition(
  vector<T>& set, // a horrible name, really
  int start,      // the index of the first sequential element to partition, inclusive
  int end,        // the index of the last sequential element to partition, inclusive
  bool (*compare)(const T&, const T&))  // function used to implement our predicate
{
   int pivotIndex, mid;  // indices: where the new pivot index currently will be, and where we'll get our pivot from
   T pivotValue;       // a value: the value of our pivot

   mid = (start + end) / 2;  // We'll choose the middle element as our pivot*

   // For the sorting, we'll move the element selected as our pivot to the 
   // very first element of our sub-array. That way we can conveniently 
   // exclude it from our partitioning. To make the move quick and painless, 
   // we'll just swap the two element values.
   T temp = set[start];
   set[start] = set[mid];
   set[mid] = temp;


   pivotIndex = start;  // Our initial pivot index is where we just moved the pivot value to.
   pivotValue = set[start];  // The pivot value, for convenient use. This will not change.

   // Now we'll loop through all the elements in the remaining spaces (not the pivot)
   for (int scan = start + 1; scan <= end; scan++)
      {
         if (compare(set[scan], pivotValue))  // our predicate: element ?? pivotValue
         {
            // okay, we got in here because this element is to be moved before the final pivot position

            // so we'll bump our final pivot index up by one (so that now it indexes 
            // the first element after the final pivot position)
            pivotIndex++;

            //pivotIndex and scan of the vector  // what? this comment does not help us understand the algorithm.

            // (scan --> element that goes before pivot, pivotIndex --> element that goes after)
            // swap them, so
            // (pivotIndex --> element that goes before pivot, scan --> element that goes after)
            T newTemp = set[pivotIndex];
            set[pivotIndex] = set[scan];
            set[scan] = newTemp;
         }
      }

   // Good so far. Now we have everything positioned -- except the actual 
   // pivot value is still sitting at the beginning of our sub-array. We need to 
   // move it back to the new pivot index. Simple enough: we'll just swap
   // again. (Remember, the thing under pivotIndex --> element that goes 
   // before pivot, so swapping will make that true for every 'before' element we found.)
   T thirdTemp = set[start];
   set[start] = set[pivotIndex];
   set[pivotIndex] = thirdTemp;

   // Now pivotIndex really does point to the pivot value.
   return pivotIndex;
}

* To avoid overflow problems, it should be calculated as mid = start + (end - start + 1) / 2;. Don't forget that off-by-one there.

Notice that the actual order of elements before and after the pivot don't matter.

More reading on quicksort:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/

Hope this helps.

[chiefsosa1]

hey thank you very much for the help, but im still a little confused as to what is going on in the if (come(set[scan], pivotValue)) loop. Which element are you referring to when you saying 'because this element it to be moved before the final pivot position. also, what is the final pivot position?

thank you i really appreciate it

[serge]

Duoas, which start and end values did you use? The array partitioned is going to be rather
3 2 1 4 6
which is quite evident. BTW, logics behind partitioner is explained amazingly clear.

[Duthomhas]

@chiefsosa1
I don't have time to explain right now. I'll do it a little later today.

[edit]
Okay, here we go.

For partitioning purposes, the array is organized thus:

          where to put the pivot value when we're done
          |
[p][b]...[b][a]...[a]
 |  |     |  |     |
 |  |     |  stuff that goes AFTER the pivot value
 |  |     |
 |  stuff that goes BEFORE the pivot value
 |
 pivot value

The thing to remember during all this time is that the thing under the so-called "pivot index" isn't the pivot. It's a "before". The pivot value is all the way in the front.

So when the partitioning is done, we need to actually adjust things so that the pivot is where the "pivot index" indicates it should be. That's why we swap the 0 and pivotIndex elements. After the swap, the array looks like it should:

          pivot
          |
[b][b]...[p][a]...[a]
 |     |     |    |
 befores     afters

Hope this helps.

[/edit]

@serge
In the example sequence I gave, I just moved things "by eye". The exact ordering doesn't actually matter. (There's more than one way to partition a cat.)