Quick Sort is a popular and efficient sorting algorithm that uses a divide-and-conquer approach to sort an array or list of elements. The algorithm works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, one containing elements less than the pivot and one containing elements greater than the pivot. This process is then repeated recursively on the sub-arrays until the entire array is sorted.
The pivot element is typically chosen as the last element in the array, but it can also be chosen randomly or as the median of the array to improve performance. The pivot element is then placed in its correct position in the sorted array, and the process is repeated on the left and right sub-arrays until the entire array is sorted.
The key advantage of Quick Sort is its average O(n log n) time complexity, making it a faster option than other sorting algorithms such as Bubble sort and insertion sort. However, its worst-case time complexity is O(n^2) if the pivot is chosen poorly, making it less efficient in certain situations.
Here is an example of the Quick Sort algorithm implemented in C++:
#include <iostream>
using namespace std;
// Function to partition the array and return the pivot index
int partition(int arr[], int low, int high) {
int pivot = arr[high];
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;
}
// Function to perform Quick Sort
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int main() {
int arr[] = {4, 2, 9, 6, 23, 12, 34, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
In this example, the partition function is used to divide the array into two sub-arrays and return the pivot index. The quickSort function then recursively calls itself on the left and right sub-arrays until the entire array is sorted. The main function initializes an array and calls the quickSort function to sort it, and finally, the sorted array is printed to the console.
It is important to note that Quick Sort is not a stable sorting algorithm, meaning that equal elements may not maintain their relative order in the sorted array. Additionally, the efficiency of Quick Sort can be improved by using a different pivot selection strategy, such as choosing the median of the array or using a random pivot.
In conclusion, Quick Sort is a popular and efficient sorting algorithm that uses a divide-and-conquer approach to sort an array of elements. Its average time complexity of O(n log n) makes it faster than other sorting algorithms
