Quick Sort in C++

In this tutorial, we are going to learn Quick Sort in C++ and its implementation.

‘Sorting’ in programming refers to the proper arrangement of the elements of an array (in ascending or descending order).

Note: ‘array’ is a collection of variables of the same data type which are accessed by a single name.

‘Quick Sort’ uses the following algorithm to sort the elements of an array:
let the array be -> {1,9,4,7}

  1. Fix one particular element of the array (this element is termed pivot)
    let the last element 7 be the pivot
  2. Partition all the elements of the array, lesser than the pivot, to the left (or right) and all the elements of the array, greater than the pivot, to the right (or left); to sort in ascending (or descending) order
    all elements lesser than 7 go to the left-> {1,4}
    all elements greater than 7 go to the right -> {9}
    so array -> {{1,4},7,{9}}
  3. Treat all the elements to the left as a new array and start from step 1, unless only one element remains
    let the last element in {1,4} be the pivot
    then, all elements lesser than 4 go to the left -> {1}
    there are no elements greater than 4 to go to the right
    so array -> {{{1},4},7,{9}}
  4. Treat all the elements to the right as a new array and start from step 1, unless only one element remains
    9 is the only element present in {9}, so no further action
    so array -> {{{1},4},7,{9}}
    Hence, the sorted array is -> {1,4,7,9}

Implementation of Quick Sort in C++

#include <stdio.h>
#define size 4//pre-defining the length of the array
void inputArray(int array[],int length)
 {
     printf("Input %d (integer) elements: ",length);
     //note, in the for loop, the intitializing statement is decreasing the value of length by 1 because in arrays, counting starts from 0
     for(length--;length>=0;length--){
        scanf("%d",&array[length]);
     }
 }
void printArray(int array[],int length)
 {
     printf("The elements of the given array are: ");
     for(int i=0;i<length;i++)printf("%d ",array[i]);
 }
void swap(int* p, int* q)//this function swaps the values to which pointers p and q point
{
    int temporary = *q;
    *q = *p;
    *p = temporary;
}
//here onwards, 'lower' indicates the first index of the passed array and 'upper' indicates last index of the passed array
int partition (int array[], int lower, int upper)//this function partitions the array, treating the last element as the pivot
{
    int i = (lower - 1);  //index of smaller element
    for (int j = lower; j < upper; j++)
    {
        if (array[j] <= array[upper])//THIS CONDITION SORTS IN ASCENDING ORDER
        {
            i++; // incrementing index of smaller element
            swap(&array[i],&array[j]);//passing the addresses of the array elements for swapping
        }
    }
    swap(&array[i + 1], &array[upper]);//finally, swapping the pivot and the element in the position at which pivot is supposed to be
    return (i + 1);//returning the position that the pivot would take in the sorted array
}
void quickSort(int array[], int lower, int upper)
{
    if (lower < upper)//this condition checks whether the array contains more than one element
    {
        int pivotIndex = partition(array, lower, upper);//getting the index of the pivot after partition of the array
        quickSort(array, lower, pivotIndex - 1);//sorting elements before the pivot
        quickSort(array, pivotIndex + 1, upper);//sorting elements after the pivot
    }
}
int main()
{
    int array[size];
    inputArray(array,size);
    quickSort(array,0,size-1);//passing size-1 because array-index-counting starts from 0
    printArray(array,size);
    return 0;
}

Output:

Input 4 (integer) elements: 1 9 4 7
The elements of the given array are: 1 4 7 9

Summary:

The execution of the program is explained below:

  • inputArray(int[],int) is called to take input integer elements from the user and store them in the array
  • quickSort(int[],int,int) is called to sort the elements of the array with the algorithm explained above
  • printArray(int[],int) is called to print the elements of the array (after sorting)

Note:

  • the value ‘4’ after size can be changed to any other value in order to get the desired array-length
  • since (in C++) arrays are passed by reference, therefore the changes made in quickSort(int[],int,int) and partition(int[],int,int) stay permanently
  • to sort in descending order, just change the sign from ‘<=’ to ‘>‘ in the logical condition inside the for loop of partition(int[],int,int)

You may also read:



Leave a Reply

Your email address will not be published. Required fields are marked *