Recursion and Quick Sort

Hi! I've been studying quick sort. I stumbled across this piece of code:

Code:

void quicksort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
 
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
 
      /* recursion */
      if (left < j)
            quicksort(arr, left, j);

      if (i < right)
            quicksort(arr, i, right);
}

Was using the debugging feature in DevC++. Found some amusing behaviour which led me to the following conclusions..Am I right in assuming that during recursive calls to quicksort, the values of left and right passed by value rather than reference?
If not, I am seriously bugged! because I dont seem to get Quick Sort step by step at all although I get the general concept! Thanks!

Originally Posted by black_stallion

Am I right in assuming that during recursive calls to quicksort, the values of left and right passed by value rather than reference?

You don't have to assume. Look at the parameter list here:

Code:

void quicksort(int arr[], int left, int right) {

Clearly, the left and right parameters are of type int, i.e., the corresponding arguments are passed by value.

If they were of pointer type instead, then the corresponding arguments would still be passed by value, but we can conceptually regard what the pointers point to as being passed by reference.

Originally Posted by laserlight

You don't have to assume. Look at the parameter list here:

Code:

void quicksort(int arr[], int left, int right) {

Clearly, the left and right parameters are of type int, i.e., the corresponding arguments are passed by value.

If they were of pointer type instead, then the corresponding arguments would still be passed by value, but we can conceptually regard what the pointers point to as being passed by reference.

Ah you hit the nail on the head! Sometimes you just think so deep that you overlook the simpler things! That's why I saw a few anomalies while watching values of left,right,i,j,to name a few! Thanks! Btw, how good is this code? I mean, are there any better code examples for quick sort that this one?

The biggest improvement to Quicksort that I know of, is to add Insertion sort (and calls to it), when the sub arrays are small (say 15 to 60 or so, depending on your own system).

imo, no sorter is faster with a small array that is almost already sorted, than Insertion sort. Oddly, Bubble sort is also quick at this specialty.

This is the optimized Quicksort, I have found best (but still clear), so far. I know iMalc (a forum regular) has an optimized one as well, but I haven't tested his version yet.

Code:

//Optimzed Quicksort
void quicksortOpt(int A[], int lo, int hi) {
  int i, j, pivot, temp;
  if(lo == hi) return; 

  if((hi - lo) < InsertNum) {
    insertionSort(A, lo, hi+1); 
    return;
  }

  i=lo; 
  j=hi;
  pivot= A[(lo+hi)/2]; 

  /* Split the array into two parts */
  do {    
    while (A[i] < pivot) i++; 
    while (A[j] > pivot) j--;
    if (i<=j) {  
        /* using a swap() function gives the same time, as
         using the swap code below */
      temp= A[i];
      A[i]= A[j];
      A[j]=temp;
      i++;
      j--;
    }
  } while(i<=j);
  
  if (lo < j) quicksortOpt(A, lo, j);
  if (i < hi) quicksortOpt(A, i, hi);
}

I have read all kinds of misleading posts regarding fast sorters. They were misleading in the sense that they optimized a particular algorithm, to perform exceptionally well on a particular PC system, (and there are many such optimizations you can make), or their IDEA of a fast sorting algorithm, was untested, and just wasn't that fast.


Those algorithms and optimizations for specific data, or a specific type of computer system, don't interest me. I want to use it on any PC and, I need it to be clear enough that it can be optimized for the specific type of data that will be sorted, if necessary.

To use it, you need to also have an Insertion sort function, and some of those are funky, as well. The one's that don't "shuffle" are hardly different from Bubble sort, imo. Unfortunately, the Bible of C ("The C Programming Language by K&R), has an example of a funky Insertion sort, so it's become fairly commonplace.

Code:

/* a clearer version */
void insertionSort(int A[], int lo, int hi) {
  int i, j, val; 
  j=hi;   
  for(i=lo+1;i<hi;i++) {  
    val = A[i];
    j = i-1;
    while(A[j] > val) {
      A[j + 1] = A[j];
      --j;
      if(j<0) break;
    }   
    A[j+1] = val;
  }
/*
  puts("\nAfter Insertion Sort:\n");
  for(i=lo;i<hi;i++)
     printf(" %2d ",A[i]);
  getchar();
*/
}

In the original quicksort and also in how they teach it, the pivot value is swapped to the end of the array before partitioning and then swapped into the place between the high and low items afterwards. However a few of us have found that it is faster to not do that, but to instead make a copy of the pivot whilst also leaving the pivot in the array. This further simplifies the two inner while loops as well, giving even more speed. The code you posted has this modification. Just be aware that when you look at algorithm descriptions elsewhere then they may not have this modification. When it comes to any kind of exam or test, you're probably best to know about the classic way they do it.

The thing I dislike with the code posted here is that is that it fails if the number of items to sort is zero. A caller should not have to check if the number of items is zero before calling the sort function. However if this function were called from a stub that looked like this... then it is okay:

Code:

void quicksort(int arr[], int size) {
    if (size > 0)
        quicksort(arr, 0, size-1);
}

The other thing to be aware of is that with a specially crafted array with enough items that has the values in the exact worst ordering could cause this code to create a stack overflow. This would happen if say the smallest item were in the middle of each sub-array every time, which can be crafted by someone working backwards through the algorithm. The best way to protect against that is to only recurse on the partition that has fewer items and iterate on the one that has more. Picking the splitter randomly is another way, but that still isn't a guarantee that you wont get stack overflow.

Feel free to take a look at the quicksort or other sorting algorithms on my website if you like. Any feedback is welcome also.

Code:

If (low == high)
   return;

Will prevent a crash from an empty array, providing hi is the last index of the array, with good data to be sorted.

Before BASIC supported recursion - back when we were fighting the dinosaur's in our spare time, I picked up a book on programming, that had the best sorting example - Quicksort!

Just for fun, this is it, and you can see the beauty of recursion:

Code:

  //Quicksort, Iterative
void quicksortIter(int A[]) {
  int I, J, left, right, stack, pivot, maxStack, fault;
  int ST[48] = { 0 }; //uses 20 with N=25,000 and range of 0-999
  left = stack = 0; right = MAX-1; 
                                                
  while(1) {
    while(left >= right) {         //better with the >=
      if(stack != 0) {             //jump to insertion sort here
          right = ST[stack];         
          left = ST[stack - 1]; 
          stack -= 2;
        }
        else  //if T0 == 0, we're done sorting
          return;    //break won't do what it needs
      }
      pivot = A[left]; 
      I = left+1;    //forward loop counter //was left + 1
      J = right+1;   //backward loop counter //was right + 1
    
      /* these iterators are sooo incredibly touchy */                 
      do {
        while(A[--J] > pivot);    //Touchy, Touchy!!  
        while(A[I] < pivot) ++I;  // "        "

        if(J > I) {
          swap(A,I, J);
        }
      }while(J > I);

      A[left] = A[J];
      A[J] = pivot;
                                    
      if((J - left) < (right - J))  //take the smallest sub array first
        ST[stack + 1] = J + 1;
                                          
      if(ST[stack + 1] == J + 1) { 
        ST[stack + 2] = right; 
        right = J - 1; 
      }
      else {
        ST[stack + 1] = left; 
        ST[stack + 2] = J - 1; 
        left = J + 1;
      }
      stack = stack + 2;                      //push onto ST[]
                   //if(stack > maxStack) maxStack = stack;  debug aid 
                                          
    }//end of while(1) 
}

Which didn't move the partition. (and is VERY "fragile" in my C compiler. It was much more robust in my BASIC interpreter.) You had to adjust the size of the ST array, sometimes, however.

When I moved over to C and started reading up more on Quicksort, I couldn't understand what they were doing, moving the partition around. Later on, I learned that was just the way the early versions were done, so nearly everyone has been doing it that way, ever since.

That book wasn't much (very small), but it had some great info in it, and helped get some badly needed programs running in an office that was still using MANUAL typewriters, (one computer), for heaven's sake!