Recursion and Quick Sort

This is a discussion on Recursion and Quick Sort within the C Programming forums, part of the General Programming Boards category; Hi! I've been studying quick sort. I stumbled across this piece of code: Code: void quicksort(int arr[], int left, int ...

  1. #1
    Registered User black_stallion's Avatar
    Join Date
    Aug 2011
    Location
    India
    Posts
    22

    Question 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!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User black_stallion's Avatar
    Join Date
    Aug 2011
    Location
    India
    Posts
    22

    Lightbulb :)

    Quote Originally Posted by laserlight View Post
    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?

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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();
    */
    }

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quick Sort
    By e66n06 in forum C++ Programming
    Replies: 13
    Last Post: 08-21-2007, 08:02 AM
  2. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 05:48 PM
  3. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  4. Quick Sort Help
    By NavyBlue in forum C Programming
    Replies: 1
    Last Post: 03-02-2003, 09:34 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21