Quick Sort Algorithm in C++
Quick sort algorithm was developed using the divide and conquer approach and it comes under comparison algorithm category.
This is also known as partition-exchange sort. This algorithm splits the array into two sub-arrays based on the pivot position and performs the sort operation recursively
till there is no more sub arrays exist. Quick sort is an easiest way of sorting technique, but it's not an efficient on large data sets.
Time Complexity
- Best complexity: n*log(n)
- Average complexity: n*log(n)
- Worst complexity: n^2
Quick Sort Implementation in C++
C++ Input Screen
#include <iostream>
using namespace std;
class QuickSortExample
{
// Access specifier
private:
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while(i < j) {
while(arr[i] <= pivot && i < high) {
i++;
}
while(arr[j] > pivot && j > low) {
j--;
}
if(i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[low] = arr[j];
arr[j] = pivot;
return j;
}
// Access specifier
public:
void quickSort(int arr[], int low, int high) {
if(low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot);
quickSort(arr, pivot + 1, high);
}
}
void printArray(const int arr[], size_t size) {
for(size_t i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main(int argc, const char * argv[])
{
// Declare an object of class QuickSortExample
QuickSortExample obj;
int arr[] = { 15, 3, 12, 6, -9, 9, 0 };
const size_t SIZE = sizeof(arr) / sizeof(*arr);
cout << "Before Sorting: ";
obj.printArray(arr, SIZE);
obj.quickSort(arr, 0, (SIZE - 1));
cout << "After Sorting: ";
obj.printArray(arr, SIZE);
return 0;
}
C++ Output Screen
Before Sorting: 15 3 12 6 -9 9 0
After Sorting: -9 0 3 6 9 12 15
Quick sort implementation steps:
Let's take the input array as { 15, 3, 12, 6, -9, 9, 0 } and we can see how the Quick sort is sorting the array.
- Choose the lowest or highest index value as a pivot element, in our above example we chose the lowest index as a pivot element 15.
- Declare two variables (i.e. pointer) to store the lowest and highest index position except the pivot element, so the lowest index position is 1 points the value 3 and the highest index position is 6 which is pointing the value 0
- Move the left side pointer towards right until the value of the pointer is less than or equal to the pivot element.
- Move the right side pointer towards left until the value of the pointer is greater than the pivot element.
- Interchange the values of left side pointer and right side pointer.
- Interchange the values of leftmost index (i.e. position 0 has the pivot element 15) and right side pointer.
- The right side pointer is a new pivot position for the value 15
- Split the array into two sub-arrays with the help of pivot point
- Index from 0 to pivot
- Index from (pivot + 1) to (n - 1), where n is the length of an array
- Apply the step 1 to 8 until there is no more elements to split as an array.
Quick Sort Implementation in C++ with explanation
C++ Input Screen
#include <iostream>
using namespace std;
class QuickSortExample
{
// Access specifier
private:
int partition(int arr[], int low, int high) {
// Pick a lowest bound element as an pivot value
int pivot = arr[low];
int i = low;
int j = high;
while(i < j) {
// Increment the index value of "i"
// till the left most values should be less than or equal to the pivot value
while(arr[i] <= pivot && i < high) {
i++;
}
// Decrement the index value of "j"
// till the right most values should be greater than to the pivot value
while(arr[j] > pivot && j > low) {
j--;
}
// Interchange the values of present
// in the index i and j of an array only if i is less than j
if(i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Interchange the element in j's poisition to the lower bound of an array
// and place the Pivot element to the j's position
arr[low] = arr[j];
arr[j] = pivot;
// Finally return the appropriate index position of the pivot element
return j;
}
// Access specifier
public:
void quickSort(int arr[], int low, int high) {
if(low < high) {
// Find the pivot index of an lower bound of an array
int pivot = partition(arr, low, high);
// Apply Divide and conquer stratagy
// to sort the left side and right side of an array
// respective to the pivot position
// Left hand side array
quickSort(arr, low, pivot);
// Right hand side array
quickSort(arr, pivot + 1, high);
}
}
void printArray(const int arr[], size_t size) {
// Loop the item and print each item in the console with white space seperated
for(size_t i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main(int argc, const char * argv[])
{
// Declare an object of class geeks
QuickSortExample obj;
int arr[] = { 15, 3, 12, 6, -9, 9, 0 };
const size_t SIZE = sizeof(arr) / sizeof(*arr);
cout << "Before Sorting: ";
obj.printArray(arr, SIZE);
obj.quickSort(arr, 0, (SIZE - 1));
cout << "After Sorting: ";
obj.printArray(arr, SIZE);
return 0;
}
C++ Output Screen
Before Sorting: 15 3 12 6 -9 9 0
After Sorting: -9 0 3 6 9 12 15
BBMINFO
