The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Sorting

Problem :-
Implement the QuickSort algorithm.

Solution :-
Quicksort is also known as partition-exchange sort. This algorithm first divides the array into smaller sub-arrays which are recursively sorted to obtain the final sorted array.
Quicksort algorithm works as follows :-
Select a pivot element from the array & re-order all the elements of the array such that all elements less than pivot are placed towards the left of pivot & all elements greater than pivot are placed towards the right.
Now, pivot element is placed in its correct position in the sorted array and we have two sub-arrays.
Now recursively sort the sub-arrays using the same procedure.

Partitioning algorithm ( to find the pivot element ) :-
Consider an array of size n.
We select the last element of the array ( suppose its k ). Let 'j' be the iterator. We also maintain a variable 'i' which points to the last index in which a value less than k was found.
Initialization :: j = start_index & i = j - 1
Now, we iterate over the array and compare k with each element. If we see an element ( arr[ j ] ) <= k, we increment i & swap arr[ i ] & arr[ j ].
Finally, once the iteration is over, we swap arr[ i+1 ] & k. So, last element ( k ) is placed in its correct position i.e i+1 & it acts as the pivot element and the array is partitioned into two sub-arrays.
For e.g, consider the array { 7, 4, 5, 2, 3, 19, 11, 6, 9, 12, 8 }
Here, k = 8 ( last element ) [ Our aim is to place 8 into its correct position in the sorted array ]
Also, j = 0 ( start index of the array ) & i = ( j - 1 ) = -1
We iterate over the array and do increment of 'i' & swapping as illustrated above whenever arr[ j ] <= k.
After iteration is over, array becomes { 7, 4, 5, 2, 3, 6, 11, 19, 9, 12, 8 } with i = 5.
Now, we swap arr[ i+1 ] & k. So the array becomes { 7, 4, 5, 2, 3, 6, 8, 19, 9, 12, 11 }.
Thus, pivot element = 8 & pivot index = ( i + 1 ) = 6 and the array is partioned into two sub-arrays
{ 7, 4, 5, 2, 3, 6 } & { 19, 9, 12, 11 }

QuickSort Demonstration :-
Consider the same array { 7, 4, 5, 2, 3, 19, 11, 6, 9, 12, 8 }. Lets see how QuickSort works :-
After first partitioning :-
{ 7, 4, 5, 2, 3, 6 }       8      { 19, 9, 12, 11 } ( 8 is the pivot element )
After partitioning sub-arrays :-
{ 4, 5, 2, 3 } 6 { 7 }       8      { 9 } 11 { 12, 19 } ( 6 & 11 are pivot elements for the two sub-arrays )
As we partition further:-
{ 2 } 3 { 4, 5 } 6 { 7 }       8      { 9 } 11 { 12, 19 }

In this way, after repeated partitioning & recursively sorting the sub-arrays we get the final sorted array
{ 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 19 }

Complexity of the Quicksort algorithm is O(n log n) in average case. However, in worst case it is O(n2),
though this behaviour is very rare.

#include<iostream>
using namespace std;

// Display the Array
void displayArray(int arr[],int size) {
   int i;
   for (i=0;i<size;i++) {
      cout<<arr[i]<<" ";
   }
}

// swap elements in the array
void swap(int arr[],int idx1,int idx2) {
   int temp;
   temp = arr[idx1];
   arr[idx1] = arr[idx2];
   arr[idx2] = temp;
}

// partition the array into halves s.t that pivot element
// gets stored at it's correct position in the sorted subarray 
int partition(int arr[],int start_idx,int end_idx) {
   int k = arr[end_idx];
      int i = start_idx - 1;
      int j;
      // iterate over the subrray 
      for (j=start_idx;j<end_idx;j++) {
         if (arr[j] <= k) {
            i++;
            swap(arr,i,j);
         }
      }
      swap(arr,i+1,end_idx);
      // return the position of pivot element
      return i+1;
}

// quicksort the array recursively 
void quickSort(int arr[], int start_idx, int end_idx) {
   int pivot; // pivot element    
      if (start_idx < end_idx) {
         pivot = partition(arr, start_idx, end_idx);
         // recursively sort both the partitions
         quickSort(arr, start_idx, pivot - 1);
         quickSort(arr, pivot + 1, end_idx);
      }
}

// main
int main() {
   int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nOriginal Array :: ";
   displayArray(arr,size);
   quickSort(arr,0,size-1);
   cout<<"\nSorted Array   :: ";
   displayArray(arr,size);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Sorting
* Implement the Bubble Sort algorithm
* Implement the Selection Sort algorithm
* Implement the Insertion Sort algorithm
* Implement the Merge Sort algorithm
* Implement the Quick Sort algorithm