Arranging things in sequence is a task that we perform in daily life, whether it is arranged in ascending order or descending order. The process of arranging things in a proper sequence is called sorting. Ascending is increasing order and descending is decreasing order. In programming, we also perform the sorting using different algorithms. But one algorithm provides the quickest sorting which is “Quick Sort”. This sorting algorithm sorts the array faster than the other algorithms. It works on the divide and conquers rule, first sets a pivot point, and divides the array into two sub-arrays. Then, set a pivot for sub-arrays and the process goes on until we reach the end and the required array is sorted. This article explains an in-depth working of a quick sort in C++ with a practical coding example in ascending order.

How to Select a Pivot

Before moving into further detail, it is important to learn how we can select a pivot for the quick sort algorithm.

• • First element
  • Last element
  • Median element
  • Random element

There is no restriction for selecting a pivot. Mostly, we set the array’s last value as a pivot point.

Algorithms:

The quick sorting is done using two algorithms – one is to partition the array according to the pivot point and the other one is for sorting the array.

For Partitioning:

• • Take two variables as lowest and highest.
  • Store the starting index of the array in the lowest one and then store the last index in the highest one.
  • Define another variable and initialize it with the lowest variable like “iter”.
  • Select the array’s last member to act as the pivot.
  • Pass through the array. After that, match each element with the pivot value.
  • If the array element is less than the pivot, increment the “iter” and swap their positions.
  • Increment the “i” by 1 and repeat the process until the array’s end is reached. Terminate the loop there and return the iter-1.

The returned value gives us the position of the pivot index. Before the pivot, there are the elements that are smaller than the pivot value. After the pivot, there are the elements that are greater than the pivot value.

For Sorting:

Now, move on to the sorting. Use the following instructions to sort an array:

• • Choose the array’s last item to act as the pivot.
  • The returned index partition algorithm is the correct index of a pivot.
  • The Quicksort method is called on the left and right subarrays repeatedly.

With the help of these two algorithms, we can perform the quick sort on any array. An example of the quick sort method is elucidated in the following:

Quick Sort in Ascending Order

Let’s explain the “Quick Sort” method to sort an integer array in increasing order.

Code:

 
Start the code by importing the <iostream> library and include the standard namespace. After that, define a method named “swap” of the void return type. In this function, pass three parameters having integer type. The two arguments, “position_1” and “position_2”, are used for positions. The third one, “temp_0”, is an array. The method swaps the positions of array elements. The variable named “temp_0” is declared to temporarily save the value. Furthermore, initialize this “temp_0” with the array’s first position. Then, assign the array’s second position to an array’s first position “position_1”. And assign the temp to the array’s second position which is “position_2”. This works as a=b; b=c; c=a. This method only performs the swap.

In addition to this, define another function for partition. This method divides the array into two parts and further divides the sub-arrays into sub-arrays. This function is a return-type method and it returns an integer value that contains the correct index of the pivot. This partition()method has four integer type arguments. First is an array of “array_0”, the second is “low” which stores the starting index of the array, the third is “high” which contains the last index of the array, and the fourth is “pivot”. Within this method, initialize two variables – “i_0” and “j_0” – with “low”. These two variables have an “int” data type. As we know, “low” contains the initial index of the array. In the next line, use the “while” loop to iterate on the array. First, set the condition of”‘while” as i_0 <= high. Iterate until we reach the last index of the array. Inside the “while” loop, employ the “if” decision-making statement to check whether the array elements are greater than the pivot or not. If this condition is fulfilled, the body of “if” executes which increments the iterator. Otherwise, the body of “else” is run. In the body of “else”, we callthe swap() method that swaps the array values until they are in ascending order. Outside the “while”, return the “j_0-1” to the function. Because that is incremented in the “else” part.

Define another QuickSort()method of void return type to perform the quick sorting. Three arguments – “array_0”, “low”, and “high” – having an integer type data are provided to this function. Moreover, set the “if” condition. If “low” is less than the “high”, initialize the “pivot” with the array’s last index “high”. For the “position” variable, call the partition() method. Then, recursively invoke the QuickSort() function on the right and left sub-arrays.

In the last portion of the code, employ the main() method. Next, initialize an “int” type array and call the QuickSort_0() method. This function contains three arguments. It performs a quick sort on the specified array and sorts this array. Enter the “cout<<” command to print the “The sorted array is:” line. To display the sorted array, use a “for” loop and iterate until the end of the array is reached.

Output:

Conclusion

Quick Sort in C++ is discussed in this guide. In programming, it is necessary to arrange the arrays in ascending or descending order. There are multiple sorting algorithms like bubble sort, merge sort, etc. Quick sort is one of them but as the name says, it sorts the array more quickly than others. This article explains what a pivot is, which array element can be the pivot, which algorithms are used for quick sorting, and how they perform. This article concludes with the code of C++ where we implement the quick sort.