AppDividend
Latest Code Tutorials

Quick Sort in C++ Tutorial With Example | C++ Quick Sort Program

0

Quick Sort in C++ Tutorial With Example | C++ Quick Sort Program is today’s topic. Like Merge Sort, Quick Sort is also a recursive sorting algorithm which uses Divide and Conquer method. If you don’t know what Divide and Conquer are, then please read our Merge Sort tutorial first.  British computer scientist Tony Hoare developed the QuickSort algorithm in 1959 and published in 1961. Quicksort is that algorithm which is being used most of the compiler in their sort().

Quick Sort in C++ Tutorial With Example

In Quick Sort first, we need to choose a value, called pivot (preferably the last element of the array). Then, we arrange the smaller values towards the left side of the pivot and higher values towards the right side of the pivot. These two operations are performed recursively until there is only one element left at both the side of the pivot. Another word, quicksort algorithm is following.

QuickSort is a sorting algorithm, which is commonly used in computer science. QuickSort is a divide and conquers algorithm. It creates two empty arrays to hold elements less than the pivot value and elements more significant than the pivot value, and then recursively sort the sub arrays. There are two basic operations in the algorithm, swapping items in place and partitioning the section of an array.

Example of QuickSort Algorithm

Now, see the following example.

Suppose we are given an array.

15 85 32 4 21 24

 

So here our pivot =24. Now after arranging all smaller elements to the left side of 24 and more significant elements to the right side of 24, the array will be the following.

Quick Sort in C++ Tutorial With Example | C++ Quick Sort Program

 

So after the first pass, 24 is placed its correct position. Now, we will again perform the partition operation to the left sub-array and the right sub-array and so on.

So, the operations will be at each step like the following.

C++ Quick Sort Program

 

What happened here is:

First, it called Quicksort(Array,start_index,end_index), then the partition() was called, and it arranged the smaller number at the left side of the pivot and higher numbers at the right side of the pivot. And again Quicksort() was called recursively. Like this way, we got 15 at last.

Example of QuickSort Algorithm

 

After that, the Quicksort() returned the sorted subarray at each step and then again the operations on right subarray was performed like the below image.

Quick Sort Algorithm

 

So, here I have shown you in these three pictures how Quicksort is performed recursively.

  1. Find a “pivot” element in an array. The pivot item is the basis for comparison for a single round.
  2. Start the pointer (the left pointer) at the first item in the array.
  3. Start the pointer (the right pointer) at the last item in the array.
  4. While the value at the left pointer in the array is less than the pivot value, move the left pointer to the right (add 1). Continue until the value at the left pointer is greater than or equal to the pivot value.
  5. While the value at the right pointer in the array is greater than the pivot value, move the right pointer to the left (subtract 1). Continue until the value at the right pointer is less than or equal to the pivot value.
  6. If the left pointer is less than or equal to the right pointer, then swap the values at these locations in an array.
  7. Move the left pointer to the right by one and the right pointer to the left by one.
  8. If the left pointer and right pointer don’t meet, go to step 1.

Pseudo Code for Quicksort Algorithm

QUICKSORT(A, start, end)

  1. if start < end
  2. P_indx =PARTITION(A, start, end)
  3. QUICKSORT(A, start, P_indx-1)
  4. QUICKSORT(A, P_indx +1, end)
  5. Exit

PARTITION(A, start, end)

  1.  Set pivot = A[end]
  2. Set P_indx = start
  3. Repeat step 4 to 7 for j = start to end – 1
  4. if A[j]<=pivot
  5. exchange A[P_index] with A[j]
  6. Set P_index=P_index+1   

 [End of If block]

  1. exchange A[P_index] with A[end]

[End of For Loop]

     8. return P_index

C++ Program of QuickSort

See the below C++ Quicksort code.

#include<bits/stdc++.h>
using namespace std;
int partition(int *a,int start,int end)
{
    int pivot=a[end];
    //P-index indicates the pivot value index
    
    int P_index=start;
    int i,t; //t is temporary variable
    
    //Here we will check if array value is 
    //less than pivot
    //then we will place it at left side
    //by swapping 
    
    for(i=start;i<end;i++)
    {
    	if(a[i]<=pivot)
        {
            t=a[i];
            a[i]=a[P_index];
            a[P_index]=t;
            P_index++;
        }
     }
     //Now exchanging value of
     //pivot and P-index
      t=a[end];
      a[end]=a[P_index];
      a[P_index]=t;
    
     //at last returning the pivot value index
     return P_index;
 }
 void Quicksort(int *a,int start,int end)
 {
	if(start<end)
	{
	     int P_index=partition(a,start,end);
             Quicksort(a,start,P_index-1);
             Quicksort(a,P_index+1,end);
	}
}
int main()
{
	int n;
        cout<<"Enter number of elements: ";
        cin>>n;
        int a[n];
        cout<<"Enter the array elements:\n";
        for(int i=0;i<n;i++)
       {
    	 cin>>a[i];
       }
      Quicksort(a,0,n-1);
      cout<<"After Quick Sort the array is:\n";
      for(int i=0;i<n;i++)
      {
    	 cout<<a[i]<<" ";
      }
	return 0;
}

The output is below.

Quicksort algorithm program

 

Time Complexity for Quicksort

The worst case occurs when the partition process always picks the greatest or smallest item as a pivot and the complexity of Worst Case: O(N^2).

The best case occurs when a partition process always picks the middle element as pivot. And the complexity of Best Case: O(N).

The average case means when there is neither a balanced tree nor like the Worst Case. The complexity of the Average Case: (N log N).

Why Quicksort over Merge Sort?

Actually, Time Complexity for QuickSort is O(n2). Its average case running time is O(nlog(n)), but its worst-case is O(n2), which occurs when you run it on the list that contains few unique items. Randomization takes O(n). Of course, it doesn’t change its worst case, it just prevents the malicious user from making your sort take a long time.

QuickSort is more popular because it:

  1. Is in-place (Merge Sort requires extra memory linear to a number of elements to be sorted).
  1. Has a small hidden constant.

Conclusively, Quick Sort in C++ Tutorial With Example | C++ Quick Sort Program is over.

Leave A Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.