C++

Quicksort C++

Sorting algorithms are used to rearrange the list of elements in a given array. These algorithms and techniques are used to solve complex arrays. Through these algorithms, you can organize your data in a new order. Sorting algorithms help you in searching and sorting items in bulky sets of data. Doing all this manually is time-consuming; that’s why they are created to make the searching and sorting of data easier. There are multiple sorting algorithms with different functionalities, namely:

  • Quicksort,
  • Bubble sort,
  • Merge sort,
  • Insertion sort,
  • Heapsort,
  • Bucket sort.

These are some of the sorting algorithms. In this article, we will enlighten the detailed working of the quicksort algorithm and its complexity analysis with the help of a few examples. These examples might help you in making a better understanding of the working of the quicksort algorithm.

Working of the Quicksort algorithm:

Quicksort is a sorting technique based on the divide and conquer notion, likewise the mergesort. Technically it is a recursive algorithm. Quicksort divides the elements of an array into sub-array. Below are the steps of how the quicksort algorithm works:

  1. Firstly, it takes any number as a pivot and divides the array into a sub-array.
  2. The chosen element is called a pivot, which will shift at the middle of the array.
  3. After that, it rearranges the elements so that numbers less than or equal to the pivot are shifted at its left side, and numbers greater than or equal to the pivot are shifted at its right side.
  4. After the partitioning, it doesn’t matter which relation and positioning the elements are holding at the left side of the pivot; the same goes for the right side of the pivot.
  5. The algorithm recursively sorts the subarray by repeating the same procedure on both sides.

Let’s discuss it more clearly with a basic example of quicksort. Let’s suppose you have an array in this order:

#Array = { 3,5,11,9,4,17,13,15,6}

Step#1: We have selected 6 as a pivot because it is considered the best practice to choose the rightmost element as a pivot.

Step#2: Now, the elements less than the pivot move towards the left side, and elements greater than or equal move towards the right side.

#{3,5,4,6,11,9,17,13,15}

Step#3: Now, arrays will be divided into two subarrays for further sorting the elements.

#{3,5,4} 6 {11,9,17,13,15}

Step#4: The algorithm will sort these arrays sub-divided them again until the whole elements of the array get sorted. Afterward, we will take 4 as a pivot and sort this array.

#{3,4,5}  6 {11,9,13,15,17}

We selected 15 as a pivot in the second array and sorted it.

Step#5: The algorithm will sub-divided the second array again because the left side array is sorted now.

#{3,4,5} 6 {9,11,13,15,17}

At this step, all elements 13, 15, and 17 were already sorted; hence the algorithm chose 13 as the pivot and sorted the remaining elements.

#{3,4,5,6,9,11,13,15,17}.

After this manual example, we are going to implement quicksort on a compiler with some different techniques.

Example_01:

In our first example, we have implemented quicksort using an iterative approach in C++. In this code, we have two functions; one is ‘main,’ and the other is ‘partition.’ Firstly, we have initialized the first and last element along with the pivot. Pivot can be any element, either the rightmost, leftmost, or the middle one. After selecting the pivot, the code will compare the elements with all the elements. After selecting pivot, we have initialized ‘int i’, which will be int i = (start-i). Now the loop will traverse the whole array from the initial index to the end index. If the pivot is greater than the value of arr[j] then the value of ‘i’ will be incremented, and arr[i] will swap with arr[j] in this way, the loop will iterate until and unless the value of arr[j] is greater than the pivot. Furthermore, the pivot will swap with the value of ‘i’ after breaking the loop. You will get the partitioning index and the sorted elements of an array in the end.


The output for the above-described code is appended below.

Example_02:

In this second example, we have implemented quicksort in a decreasing manner using the recursion approach in C++. Below is the code.

In this piece of code, the whole concept of initializing the first and start elements of the array remain the same, likewise in the first example, which is ‘int start’ and ‘int end’ in the partition method.  After this, we have initialized the arr[end] as the pivot of the element list and initialized the index of the smaller element from which the pivot is to be replaced by int i = (start -1). Now using a for loop, we will iterate through all the elements in an array to find the correct position for the pivot. Now to form the array into decreasing order, we used a condition in the loop (arr [j] > pivot). Afterward, the value of ‘int i’ will increase by i++, and we will swap arr[i] and arr[j]. The loop will stop once the swapping is done, and only the pivot will swap. Now the code will stop here ‘arr[end]=temp’ at this point, elements at the right side of the pivot are smaller than the pivot, and at the left side, all the greater elements shifted as we have shown in the output below.

The output for the above-described code is appended below.

Example_03:

This example is based on implementing quicksort using a recursive approach in C++. Let’s dive into this piece of code.

In the above piece of code, you can see that in the quicksort function, we have initialized ‘int start’ as the initial element of the array and ‘int end’ as the last element of the array. After this, we have set a condition that will run until all the starting elements remain less than the ending elements. Whenever these conditions are met, it will further call the ‘partition’ function. In the below piece of code, we have initialized the first and last element along with the pivot. Pivot can be any element, either the rightmost, leftmost, or the middle one. After selecting the pivot, the code will compare the elements with all the elements.

After selecting the pivot, we have initialized ‘int i’, which will be int i = (start-i). Now the loop will traverse the whole array from the initial index to the end index. If the value of arr[j] is less than the pivot, then the value of ‘i’ will be incremented, and arr[i]  will swap with arr[j]. In this way, the loop will iterate until and unless the value of arr[j] is greater than the pivot. Furthermore, the pivot will swap with the value of ‘i’ after breaking the loop. You will get the partitioning index and the sorted elements of an array in the end.

The output for the above-described code is appended below.

Conclusion:

In this article, we have discussed the cores of the quicksort algorithm in depth. We have tried our best to deliver most of the information about the quicksort algorithm by mentioning its complete working procedure. Also, to better understand, we have used multiple examples of quicksort that will help you implement quicksort by using the recursive and iterative approach.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.