Quick Sort is a highly efficient and widely used sorting algorithm developed by Tony Hoare in 1959. It employs a divide-and-conquer strategy to sort elements. This article will guide you through the implementation of Quick Sort in C++, providing detailed explanations and multiple examples to illustrate its application.
Prerequisites
Before diving into the implementation, ensure you have a basic understanding of the following concepts:
- Arrays: A collection of elements stored at contiguous memory locations.
- C++ Syntax: Basic knowledge of C++ programming, including loops, conditional statements, and functions.
- Recursion: Understanding how recursive functions work, as Quick Sort is often implemented using recursion.
1. Introduction to Quick Sort
1.1 Definition
Quick Sort is an efficient, comparison-based, in-place sorting algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
1.2 Algorithm Steps
- Choose a Pivot: Select an element from the array as the pivot.
- Partitioning: Rearrange the array so that all elements less than the pivot are on the left, and all elements greater than the pivot are on the right.
- Recursively Apply: Apply the above steps recursively to the sub-arrays of elements with smaller and greater values.
2. Implementation of Quick Sort in C++
2.1 Example 1: Basic Quick Sort
Let’s start with a basic implementation of Quick Sort in C++.
#include <iostream>
using namespace std;
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Sorted array: 1 5 7 8 9 10
2.2 Example 2: Quick Sort with Different Pivot Selection
Choosing a pivot is crucial for the efficiency of Quick Sort. Here, we implement Quick Sort with the pivot being the middle element.
#include <iostream>
using namespace std;
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
int pivot = arr[mid]; // pivot as middle element
swap(&arr[mid], &arr[high]); // move pivot to end
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {24, 97, 40, 67, 88, 85, 15};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Sorted array: 15 24 40 67 85 88 97
2.3 Example 3: Quick Sort with Strings
Quick Sort can also be applied to an array of strings. This example demonstrates sorting an array of strings in lexicographical order.
#include <iostream>
#include <string>
using namespace std;
void swap(string* a, string* b) {
string t = *a;
*a = *b;
*b = t;
}
int partition(string arr[], int low, int high) {
string pivot = arr[high]; // pivot
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(string arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(string arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
string arr[] = {"apple", "orange", "banana", "grape", "cherry"};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Sorted array: apple banana cherry grape orange
Conclusion
Quick Sort is a powerful sorting algorithm that excels in performance with an average-case time complexity of O(n log n). This article provided a comprehensive guide to implementing Quick Sort in C++, demonstrating the algorithm’s versatility through examples with integers and strings, and showcasing different pivot selection strategies