Quick Sort
📘 Data Structure and Algorithm
👁 84 views
📅 Nov 05, 2025
⏱ Estimated reading time: 2 min
Quick Sort Algorithm
Quick Sort is a highly efficient sorting algorithm that follows the divide and conquer approach. It works by selecting a pivot element and partitioning the array into two halves — elements less than the pivot and those greater than it.
Algorithm Steps
- Choose a pivot element from the array.
- Partition the array so that elements smaller than the pivot are on the left and larger ones on the right.
- Recursively apply the same steps to the left and right subarrays.
Example (C++)
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; 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);
}
}
Time Complexity
- Best: O(n log n)
- Average: O(n log n)
- Worst: O(n²) (when pivot is poorly chosen)
Advantages
- Very fast for large datasets.
- In-place sorting, minimal memory usage.
Disadvantages
- Worst-case can be O(n²).
- Not stable by default.
Conclusion
Quick Sort is one of the fastest general-purpose sorting algorithms and is used in many standard libraries like C++ STL and Python.
🔒 Some advanced sections are available for Registered Members
Register Now
Register Now
Share this Post
← Back to Tutorials