Thread: How to print passes in quick sort

  1. #1
    Registered User
    Join Date
    Jul 2012
    Posts
    87

    How to print passes in quick sort

    I wrote in place quick sort, but I'm not sure how to print passes, here is a code I found online @ QUICKSORT (Java, C++) | Algorithms and Data Structures, I would like to learn how to print passes during each partition as well as the return trip, when each partition is sorted, e.g.

    given: 7,3,18,12,2,40,4 I'll choose first item as pivot so:
    level 0: left of pivot: 4,3,2
    level 0: pivot: 7
    level 0: right of pivot: 12,40,18
    level 1: left of pivot: 2,3
    level 1: pivot: 4
    level 1: left of pivot: empty
    level 1: pivot: 12
    level 1: right of pivot: 40,18
    (after)level 1: left of pivot: empty
    (after)level 1: pivot:12
    (after)level 1: right of pivot: 18,40
    (after)level 1: left of pivot:2,3
    (after)level 1: pivot: 4
    (after)level 1: left of pivot: empty
    (after)level 0: left of pivot: 2,3,4
    (after)level 0: pivot: 7
    (after)level 0: right of pivot: 12,18,40

    Code:
    void print_from_to(list, int lo, int hi)
    { 
       while ( lo <= hi )
       {
           cout << list[lo] << " ";
           lo++;
       }
    }
    
    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--;
                }
          };
    
          //print current pass
          cout << "Before: Level " << level << endl;
          cout << "left of pivot: " << print_from_to(list, left, pivot) << endl;
          cout << "pivot: " << pivot << endl;
          cout << "right of pivot: " << print_from_to(list, pivot + 1, right) << endl;
     
          /* recursion */
          if (left < j)
                quickSort(arr, left, j, level + 1);
          if (i < right)
                quickSort(arr, i, right, level + 1);
    }
    
    int main()
    {
     int list[] = {7,3,18,12,2,40,4};
     size_t size = sizeof(list)/sizeof(list[0]);
     quickSort(list, 0, size - 1);
     return 0;
    }
    Any suggestions where to print each level. I added a level parameter, but I'm stuck here...I added a print_from_to function to print left and right of pivot (so from elems @ left to pivot for left of pivot list, and elems @ pivot + 1 to right for elems right of pivot). I added the printing passes but I don't know how to print the after part for each level's partition when it's sorted, please see my example.
    Last edited by monkey_c_monkey; 09-26-2012 at 10:58 AM.

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    How about printing the "before" information at line 5 (in the code above) and the "after" at line 20.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 09-15-2011, 10:26 AM
  2. Quick question, print to two files
    By vutek0328 in forum Tech Board
    Replies: 4
    Last Post: 07-18-2007, 03:55 PM
  3. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 06:48 PM
  4. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM