CODEWITHSUNDEEP
algorithmsortingquicksort
Sesha Swarup
Sesha Swarup

Reputation: 19

QuickSort with middle elemenet as pivot

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.

Upvotes: 0

Views: 3925

Answers (2)

rcgldr
rcgldr

Reputation: 28828

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.

Upvotes: 2

user1196549
user1196549

Reputation:

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.

Upvotes: 0

Related Questions