# 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}*

- Fix one particular element of the array (this element is termed
**pivot**)

*let the last element***7**be the pivot - 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}}** - 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***4**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}}** - 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