CODEWITHSUNDEEP
javaalgorithmsorting
Claudiu Moise
Claudiu Moise

Reputation: 396

Why does quicksort need to recurse over "sorted" subsection?

still pretty new to alg/data structures been trying to learn how to apply quicksort.

I found the following implementation: https://www.geeksforgeeks.org/quick-sort/

The portion which confuses me:

/* The main function that implements QuickSort() 
      arr[] --> Array to be sorted, 
      low  --> Starting index, 
      high  --> Ending index */
    void sort(int arr[], int low, int high) 
    { 
        if (low < high) 
        { 
        /* pi is partitioning index, arr[pi] is  
          now at right place */
        int pi = partition(arr, low, high); 

        // Recursively sort elements before 
        // partition and after partition 
        sort(arr, low, pi-1); 
        sort(arr, pi+1, high); 
    } 
}

It seems to me that we shouldn't have to recurse over the sort(arr, low, pi-1) section because the algorithm is supposed to have sorted that portion already...

Upvotes: 0

Views: 83

Answers (1)

BishalG
BishalG

Reputation: 1434

In your implementation of quicksort, I commented out in some places to make it more clear about the idea behind quicksort. In your code where you calculated variable pi using partition function, all the elements before index pi are less than arr[pi] but these are not guaranteed that they are in sorted order.Also, all the elements after index pi are greater than arr[pi] but these are not guaranteed to be in sorted order. I have commented out in your code below:

int partition (arr[], low, high)
{
   // pivot (Element to be placed at right position)
   pivot = arr[high];  
   i = (low - 1)  // Index of smaller element
   for (j = low; j <= high- 1; j++)
   {
    // If current element is smaller than or equal to pivot
    /* But, it does not guaranteed that smaller elements will come in sorted fashion*/
    if (arr[j] <= pivot)
    {
        i++;    // increment index of smaller element
        swap arr[i] and arr[j]
     }
   }
   swap arr[i + 1] and arr[high])
   return (i + 1)
 }

/* The main function that implements QuickSort() 
  arr[] --> Array to be sorted, 
  low  --> Starting index, 
  high  --> Ending index */
 void sort(int arr[], int low, int high) 
 { 
    if (low < high) 
    { 
    /* pi is partitioning index, arr[pi] is  
      now at right place */
     int pi = partition(arr, low, high); 
     /*Here, all the elements before index pi are less than arr[pi] but 
       not guaranteed that they are in sorted order.
       Also, all the elements after index pi are greater than arr[pi] but 
       not guaranteed to be in sorted order.
     */
     // Recursively sort elements before 
     // partition and after partition 
     sort(arr, low, pi-1); 
     sort(arr, pi+1, high); 
  } 
}

Upvotes: 1

Related Questions