Thread: 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 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();
*/
}

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!