Quick Sort
Quick Sort is one of the fastest and most widely used sorting algorithms. It follows the Divide and Conquer technique, where an element called the Pivot is selected to divide the array into two parts. Elements smaller than the pivot are placed on the left side, while elements larger than the pivot are placed on the right side. The same process is then applied recursively to the left and right sub-arrays until the complete array becomes sorted.
Quick Sort is preferred in many programming libraries because of its excellent average-case performance and efficient use of memory. Although its worst-case time complexity is higher than Merge Sort, it is usually faster in practice for large datasets.
Prerequisite
| Concept | Description |
|---|---|
| Arrays | Quick Sort is generally implemented on arrays. |
| Recursion | The algorithm recursively sorts the left and right partitions. |
| Divide and Conquer | Quick Sort follows the Divide and Conquer strategy. |
Working Principle
Quick Sort works by selecting one element as the Pivot. The remaining elements are arranged so that all smaller elements appear before the pivot and all larger elements appear after it. After partitioning, the same procedure is repeated for both sub-arrays until every element reaches its correct position.
Steps of Quick Sort
- Select a pivot element.
- Partition the array around the pivot.
- Recursively sort the left sub-array.
- Recursively sort the right sub-array.
- Combine the results to obtain the sorted array.
Illustration
Example
Consider the following unsorted array.
50 20 80 30 10 60
Step 1 : Select the first element (50) as the pivot.
Step 2 : Rearrange the array so that elements smaller than the pivot are placed before it and larger elements after it.
20 30 10 50 80 60
Step 3 : Apply Quick Sort recursively to both sub-arrays.
10 20 30 50 60 80
Quick Sort Algorithm
QuickSort(Array, Low, High)
Step 1 : If Low < High
Step 2 : Select a Pivot element.
Step 3 : Partition the array around the Pivot.
Step 4 : Apply QuickSort() on the Left Sub-array.
Step 5 : Apply QuickSort() on the Right Sub-array.
Step 6 : Repeat until the complete array becomes sorted.
Complexity Analysis
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(n log n) | The pivot divides the array into two nearly equal halves during every partition. |
| Average Case | O(n log n) | On average, partitioning remains balanced, resulting in efficient sorting. |
| Worst Case | O(n²) | Occurs when the pivot is always the smallest or largest element, producing highly unbalanced partitions. |
| Space Complexity | O(log n) | Additional memory is required only for the recursive function calls. |
Why is Quick Sort Fast?
Quick Sort is generally faster than many other sorting algorithms because it performs sorting within the original array and requires very little additional memory. When the pivot divides the array into nearly equal parts, the number of comparisons is significantly reduced, resulting in an average time complexity of O(n log n).
Advantages of Quick Sort
- Very fast in practice for large datasets.
- Average time complexity is O(n log n).
- Requires very little additional memory.
- Suitable for in-memory sorting.
- Used in many standard programming libraries.
Limitations of Quick Sort
- Worst-case time complexity is O(n²).
- Performance depends on the choice of the pivot element.
- Recursive implementation may increase function call overhead.
- Quick Sort is not a stable sorting algorithm.
Applications of Quick Sort
| Application | Description |
|---|---|
| Programming Libraries | Used as one of the standard sorting algorithms. |
| Database Systems | Sorting records stored in memory. |
| Operating Systems | Efficient sorting of internal data structures. |
| Scientific Computing | Sorting numerical datasets. |
| Competitive Programming | Frequently used due to its excellent average-case performance. |
Merge Sort vs Quick Sort
| Merge Sort | Quick Sort |
|---|---|
| Uses Merge operation. | Uses Pivot Partitioning. |
| Stable Sorting Algorithm. | Not Stable. |
| Requires extra memory. | Works mostly in-place. |
| Worst Case: O(n log n) | Worst Case: O(n²) |
| Suitable for Linked Lists. | Suitable for Arrays. |