Quick Sort in C++

How Quick Sort works in C++

In the process of sorting we arrange the given data in either ascending or descending order this means that we try to arrange the data in a logical form. Data structure and algorithm provides us various sorting algorithm like selection sort, merge sort, etc. You can learn about these sorting algorithm clicking the button below.Quick sort  is an algorithm of the divide and conquer type. That is,the problem of sorting a set is reduced of the problem of sorting two smaller sets. In this article we learn how this sorting algorithm works and  will code a program for quick sort in C++

quickly

How it works?

Quick sort works in the following way – 

  • Choose an item from array called as pivot
  • Move all the elements smaller than pivot to left partition
  • Move all the elements greater than pivot to right partition.

Choose new pivot item in each partition and keep doing the same process again until partition of one element each aren’t formed.

How to choose a pivot element for quick sort in C++?

Pivot can be selected in following ways:-

  • First element as pivot.
  • Last element as pivot
  • Random element as pivot.
  • Median element as pivot.
Quick Sort in C++

Algorithm for quick sort in C++

  • If p < r then
  • q= Partition (A, p, r)
  • Quick Sort (A, p, q)
  • Quick Sort (A, q + r, r)

Partition Algorithm

PARTITION (A, p, r)

  • x ← A[p]
  • i ← p-1
  • j ← r+1
  • while TRUE do
  • Repeat j ← j-1
  • until A[j] ≤ x
  • Repeat i ← i+1
  • until A[i] ≥ x
  • if i < j
  • then exchange A[i] ↔
  • A[j]
  • else return j
#include <iostream>
using namespace std;
  
//Function to swap two elements. 
void swap(int* x, int* y) 
{ 
    int temp = *x; 
    *x = *y; 
    *y = temp; 
} 
  
/* Partition function to do Partition
elements on the left side of pivot elements would be smaller than pivot
elements on the right side of pivot would be greater than the pivot
*/
int partition (int array[], int low, int high) 
{ 
    //Pivot element selected as right most element in array each time.
    int pivot = array[high];    
    int swapIndex  = (low - 1);   //swapping index.
  
    for (int j = low; j <= high- 1; j++) 
    { 
        //Check if current element is smaller than pivot element.
        if (array[j] < pivot) 
        { 
            swapIndex ++;    //increment swapping index.
            swap(&array[swapIndex], &array[j]); 
        } 
    } 
    swap(&array[swapIndex + 1], &array[high]); 
    return (swapIndex + 1); 
} 
  
//Recursive function to apply quickSort
void quickSort(int array[], int low, int high) 
{ 
    if (low < high) 
    { 
       /* indexPI is partitioning index, partition() function will 
        return index of partition */
        int indexPI  = partition(array, low, high); 
  
        quickSort(array, low, indexPI  - 1);  //left partition
        quickSort(array, indexPI  + 1, high); //right partition
    } 
} 
  
//Function to display the array
void display(int array[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        cout<< array[i]<<"\t"; 
} 
  
//Main function to run the program
int main() 
{ 
    int array[] = {7, 9, 1, 3, 5, 2, 6, 0, 4, 8}; 
    int size = sizeof(array)/sizeof(array[0]);
    cout<<"Before Sorting: \n";
    display(array, size);
    quickSort(array, 0, size-1); 
    cout<<"After Sorting: \n"; 
    display(array, size); 
    return 0; 
}
Output:
Before Sorting: 
7	9	1	3	5	2	6	0	4	8	
After Sorting: 
0	1	2	3	4	5	6	7	8	9	

Facts about Quick Sort

  • Quick sort is in-place algorithm.In-place sorting means,it does not use additional storage space to perform sorting.
  • The algorithm is efficient for large sized data sets.
  • The average or worst case complexity of quick sort is O(nlogn).
  • The quick sort is an in-place, divide-and-conquer, massively recursive sort algorithm.
  • The worst-case efficiency of the quick sort is o(n²) when the list is sorted and left most element is chosen as the pivot.
Quick sort in C meme