Updated April 10, 2023
Introduction to C++ QuickSort
The following article provides an outline for C++ QuickSort. In programming language we always need algorithm to make it efficient and quicksort is one of them. As the name suggest it is used to sort the elements. It follows some steps to do this. This algorithm select one element from the list which is known as ‘pivot’ and it turns divide the list two parts for effective sorting.
Syntax of C++ QuickSort
As it is an algorithm so it does not have syntax with it but it defines some step which need to be followed while implementing quick sort in any language.
- Step A: Pick one element from list as pivot.
- Step B: Pick two element as left and right.
- Step C: Left element represent low index.
- Step D: Right element represent high index.
- Step E: If value at left is less move right.
- Step F: If value at right is more move left.
We will perform this steps until the smaller and greater elements passes each other.
So by following the above steps we can implement this is our code using C++ language. But the basic idea behind this would be same for all language.
How QuickSort work in C++ with Algorithm
As now we know that QuickSort is used to sort the element in an efficient way. It is an algorithm which define some steps to follow in order to implement this in code. This algorithm basically work with pivot element, it takes one element from list as pivot and divide the whole list into two sub list and sort them.
We can choose the pivot element in different ways which are defined below:
- We can take last element as the pivot element.
- We can take middle element as the pivot element.
- We can take first element as the pivot element.
- We can take any random element as the pivot element.
We can follow any of the approaches which will turn divide our list of element into two different sub list further. We will move the other elements into the array or list to left and right in order to sort.
Below we can see one simple algorithm which is used to define the QuickSort in C++ language.
Algorithm:
quickSorAlgo(Array, less, more)
//starting algo logic
begin
Here we are defining an array which needs to be sorted
less = first element;
more = last element;
pivot
if(less < more)
//starting sorting logic
begin
pivot = partitionList (Array,less,more);
quickSorAlgo(Array,less,pivot-1)
quickSorAlgo(Array,pivot+1,more)
//here it ends
End
//algo ends
end
Let’s understand the algorithm in detail:
50, 25, 15, 20, 60, 30.
Consider the above array which contains various element inside it. We are selecting here pivot element as the last element, and accordingly we have marked first element of array as low and last element of array as high. Now we will iterate our pointers to the respective positions, but for this we will follow one rule to compare the elements.
If marked element high is smaller than our selected pivot element and low marked element is greater than our pivot element in this case we will exchange the potions of the element with each other and we are going to increment the positions of our respective elements as well where they should point to. We are going to continue this iteration until our low and high element cross each other and the pivot element is in the proper position where it should be, this will portioned the array or list into two sub list, this two list can be sorted with QuickSort algorithm independently.
15, 20, 25, 30, 50, 60
So the final output from the above sorting algorithm would be this. We can easily and effectively sort our arrays by using QuickSort algorithm in C++.
Points to remember while working with QuickSort:
- First we need to select the pivot elements from the array, it can be anything like, first, last, random or middle elements from the array of elements.
- It has different complexity which are mentioned below:
Worst case: O (n 2 )
Average case: O (n log n)
Best case: O (n log n)
- By the use of it we can sort our array elements faster which improves the performance as well.
Example of C++ QuickSort
In this example we are sorting array elements using quick sort an considering the pivot element as the last element from the array.
Code:
#include <iostream>
using namespace std;
void elementSwap(int* ele1, int* ele2)
{
int temp = *ele1;
*ele1 = *ele2;
*ele2 = temp;
}
int elementPartition (int array[], int less, int more)
{
int pivotelement = array[more];
int indexSmaller = (less - 1);
for (int qs = less; qs <= more - 1; qs++)
{
if (array[qs] < pivotelement)
{
indexSmaller++;
elementSwap(&array[indexSmaller], &array[qs]);
}
}
elementSwap(&array[indexSmaller + 1], &array[more]);
return (indexSmaller + 1);
}
void demoquickSort(int array[], int less, int greater)
{
if (less < greater)
{
int parInd = elementPartition(array, less, greater);
demoquickSort(array, less, parInd - 1);
demoquickSort(array, parInd + 1, greater);
}
}
int main()
{
cout << "Sorting array elemnts using quick sort in C++ ::** \n";
int array[] = {35, 15, 90, 26, 87, 12, 5, 44, 23, 1};
int arrsize = sizeof(array) / sizeof(array[0]);
cout << "Before sort array is : \n";
int z;
for (z = 0; z < arrsize; z++)
cout << array[z] << " ";
cout << endl;
demoquickSort(array, 0, arrsize - 1);
cout << "After sorted array is : \n";
int i;
for (i = 0; i < arrsize; i++)
cout << array[i] << " ";
cout << endl;
return 0;
}Output:
Conclusion
By using QuickSort algorithm we can efficiently sort our array list elements. We just need to select the pivot element in order to proceed with it. This will divide the array or list into two parts then we can perform QuickSort algorithm recursively in order to get the sorted elements list.
Recommended Articles
This is a guide to C++ QuickSort. Here we discuss the introduction, how QuickSort work in C++ with algorithm and example respectively. You may also have a look at the following articles to learn more –
