Today we will learn the Quick Sort Program in C++. So before starting you should have a little bit knowledge about quicksort. So,

What is Quick Sort?

Quicksort is a very efficient sorting method. It is also called “partition Exchange Sort”. The strategy used here is “Divide and Conquer” i.e, we successively partition the list into smaller lists and apply the same procedure to the sub-list.

Procedure:

We consider one element at a time (pivot) and place it in its correct position. The pivot is placed such that all elements to the left of the pivot are less than the pivot and all elements to the right are greater.

quick sort program in c

This partitions the array into two parts-left partition and right partition. The same method is applied for each of the partition. The process continues till no more partition can be made.

Note: any element can be chosen as the pivot.

We shall be considering the first element as the pivot element. The recursive function is similar to Mergesort seen earlier. However, in quick sort, we do not divide into two equal parts but partition on the basis of the pivot element.

The function sorts elements a[lb] to a[ub] where lb stands for lower bound and ub stands for the upper bound.

void Quicksort( int a[], int lb,int ub)
{
	int j;
	if(lb<ub)
	{
		j=Partition(a,lb,ub); //partition the array
		Quicksort(a,lb,j-1); //sort first partition
		Quicksort(a,j+1,ub); //sort second partition
	}
}

Now we must write the function to partition the array. We shall choose the first element of the sub-array as the pivot and find its correct position in the sub-array.

We will be using two variables i.e down and up for moving down and up the array.

quick sort program in c
Credits:Runestone.academy

Algorithm for Partitioning:

1st Step: START.

2nd Step: down=lb.

3rd Step: up=ub.

4th Step: pivot=A[lb].

5th Step: While (A[down]<=pivot && down<ub) and down++.

6th Step: While (A[up]>pivot && up>lb) and up–.

7th Step: If(down<up) interchange A[down] and A[up]. and go to step 5.

8th Step: Interchange A[up] and A[lb].

9th Step: Return up.

10th Step: STOP.

In this Algorithm, we want to find the position of pivot i.e A[lb].

We use two pointers up and down initialized to the first and last elements respectively.

We repeatedly increase down as long as the element is < pivot i.e A[down]<pivot.

Also repeatedly decrease up as long as the element is >pivot i.e A[up]>pivot.

If up and down cross each other i.e up <=down, the correct position of the pivot is up and A[up] and pivot are interchanged.

If up and down do not cross, A[up] and A[down] are interchanged and the process is repeated till they do not cross or coincide.

For Example: Sort 55,7,80,32,18,23,82,62

quick sort in c

First Partition: 18 7 23 32.

Second Partition: 80 82 62.

Applying the algorithm to the first partition:

quick sort in c

Efficiency of Quicksort:

Best Case Behavior:

The best-case behaviour occurs if there are n elements such that every time a pivot is positioned, the partitions are of equal sizes.

Thus, we have to sort two sub-arrays each of size about n/2. Each of these will be partitioned into two arrays of sizes n/4. each as shown below.

quick sort efficiency

The total number of iterations taken in log2n (here 2 is the base). In each Iteration, the total number of elements to be compared is n.

Therefore, the Best case Time complexity= O(n log2n). The best-case time complexity is achieved if the median is chosen as the pivot. This will ensure that the array splits into equal parts each time.

Worst Case Behavior:

This occurs when the pivot does not partition the array. All elements are either in the left or the right partition. This will happen when the pivot either the smallest or the largest element.

Thus, there are n iterations. The total number of comparisons will be n+(n-1)+(n-2)+…+1=n(n+1)/2.

Therefore, the Worst-case Time complexity=O(n^2). This occurs when the array is already sorted or if the elements are in the reverse order. However, in all cases, it performs efficiently.

Advantages:

It is a very efficient sorting method.

No additional data structure is required.

It is in-place sorting method.

Disadvantages:

It is not a stable sorting method.

Applications:

Defence.

Medical Monitoring.

Control for Aircraft etc.

1. Quick Sort Program in C++

//Learnprogramo - programming made simple
#include<iostream>
#include<cstdlib>
using namespace std;
// Swapping two values.
void swap(int *a, int *b)
{
	int temp; 
	temp = *a;
	*a = *b;
	*b = temp;
}
// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high)
{
	int pivot, index, i;
	index = low;
	pivot = high;
	// Getting index of pivot.
	for(i=low; i < high; i++)
	{
		if(a[i] < a[pivot])
		{
			swap(&a[i], &a[index]);
			index++;
		}
	}
	// Swapping value at high and at the index obtained.
	swap(&a[pivot], &a[index]);
	return index;
}
// Random selection of pivot.
int RandomPivotPartition(int a[], int low, int high)
{
	int pvt, n, temp;
	n = rand();
	// Randomizing the pivot value in the given subpart of array.
	pvt = low + n%(high-low+1);
	// Swapping pvt value from high, so pvt value will be taken as pivot while partitioning.
	swap(&a[high], &a[pvt]);
	return Partition(a, low, high);
}
// Implementing QuickSort algorithm.
int QuickSort(int a[], int low, int high)
{
	int pindex;
	if(low < high)
	{
		// Partitioning array using randomized pivot.
		pindex = RandomPivotPartition(a, low, high);
		// Recursively implementing QuickSort.
		QuickSort(a, low, pindex-1);
		QuickSort(a, pindex+1, high);
	}
	return 0;
}
int main()
{
	int n, i;
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
	int arr[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>arr[i];
	}
	QuickSort(arr, 0, n-1);
	// Printing the sorted data.
	cout<<"\nSorted Data ";
	for (i = 0; i < n; i++)
        	cout<<"->"<<arr[i];
	return 0;
}

Output:

using function

2. Quick Sort Program in C++ Using Recursion

The program is said to be in recursion if and only if the function which calls itself directly or indirectly.

//Learnprogramo - programming made simple
#include<iostream>
using namespace std;
void qsort(int data[],int low,int high);
int main()
{
system("cls");
int data[50],n,c=1;
while(c==1)
{
cout<<"\nEnter the size of the array:\n"; cin>>n;
cout<<"\nEnter the elements of the array\n"; for(int i=0;i<n;i++)
{
cin>>data[i];
cout<<"\n"; } qsort(data,0,n-1); cout<<"\nThe sorted array is: \n"; for(int i=0;i<n;i++)
{
cout<<" "<<data[i];
}
cout<<"\nPress 1 to continue: "; cin>>c;
}
}
void qsort(int data[],int low,int high)
{
int pivot,temp,i,j;
i=low;
j=high;
pivot=data[(low+high)/2];
while(i<=j) { while(data[i]<pivot)
i++;
while(pivot<data[j])
j--;
if(i<=j) { temp=data[i]; data[i]=data[j]; data[j]=temp; i++; j--; } } if(low<j)
(data,low,j);
if(i<high)
qsort(data,i,high);
}

Output:

using recursion

In the above program, the execution of the program continues until we press exit to stop. The function qsort() is calling itself again and again, This is called Recursion.

Also Read: