0

I am trying to search for any explanation on how Quick sort works with middle element as pivot but I couldn't find any. What I am trying to look for is there any demo on how the numbers are sorted step by step because its really hard understanding the algorithms. Thanks.

Sesha Swarup
  • 19
  • 1
  • 1
  • Possible duplicate of https://stackoverflow.com/questions/27886150/quick-sort-with-middle-element-as-pivot – Caldazar Jun 06 '18 at 15:34
  • 4
    Possible duplicate of [Quick sort with middle element as pivot](https://stackoverflow.com/questions/27886150/quick-sort-with-middle-element-as-pivot) – Caldazar Jun 06 '18 at 15:34
  • I can hardly imagine that the linked duplicate wasn't suggested to you by SO when creating your question. The title is literally the same (excluding typos). Also, always do research prior to asking here, see [ask], thanks. – Zabuzard Jun 06 '18 at 15:36
  • Perhaps OP is looking for something like [visualgo](https://visualgo.net/en/sorting), which visually shows you the sorting algorithm step-by-step. Unfortunately, they don't have middle element pivot -- only first element and random element. – Thomas Cohn Jun 06 '18 at 15:49
  • It's in van Emden's 1970 paper on Quicksort. https://dl.acm.org/citation.cfm?id=362803 – stark Jun 07 '18 at 22:11

2 Answers2

2

The vertical bars are around the pivot:

 61 11 93 74 75 21 12|55|81 19 14 86 19 79 23 44
 44 11 23|19|14 21 12 19                        
 19|11|12 14                                    
 11                                             
    19|12|14                                    
    12                                          
      |19|14                                    
       14                                       
          19                                    
             19|21|23 44                        
            |19|21                              
             19                                 
                21                              
                  |23|44                        
                   23                           
                      44                        
                         81 55 75|86|74 79 93 61
                         81 55|75|61 74 79      
                         74|55|61               
                         55                     
                           |74|61               
                            61                  
                               74               
                                  75|81|79      
                                 |75|79         
                                  75            
                                     79         
                                        81      
                                          |93|86
                                           86   
                                              93
 11 12 14 19 19 21 23 44 55 61 74 75 79 81 86 93

Based on this variation of Hoare partition scheme:

void QuickSort(int a[], int lo, int hi) {
    int i, j, p;
    if (lo >= hi)
        return;
    i = lo - 1;
    j = hi + 1;
    p = a[(lo + hi)/2];
    while (1)
    {
        while (a[++i] < p) ;
        while (a[--j] > p) ;
        if (i >= j)
            break;
        swap(a+i, a+j);
    }
    QuickSort(a, lo, j);
    QuickSort(a, j + 1, hi);
}

Note that the pivot can end up in either the left or right part after partition step.

rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • Isn't it supposed to work if I replace last two lines with, `QuickSort(a, lo, i-1); QuickSort(a, i, hi);` ? In my case its giving segmentation fault. – Sazzad Hissain Khan Oct 02 '18 at 07:08
0

Quicksort chooses a pivot value and moves the smaller elements to the beginning of the array and the larger elements to end. This is done by repeatedly scanning from both ends until a pair large/small is found, and swapped.

After such a partition process, all elements smaller than the pivot are stored before those larger than the pivot. Then the process is repeated on both subarrays, recursively. Of course when a subarray reduces to one or two elements, sorting them is trivial.

Recall that the pivot value can be chosen arbitrarily, provided there exist at least one element smaller and one larger in the array.