Quick Sort – Complete 10 Page Study Guide
1. Introduction to Quick Sort
Quick Sort is one of the most popular sorting algorithms in computer science. It follows the divide and conquer
technique. The algorithm works by selecting a pivot element and partitioning the array around the pivot. Elements
smaller than the pivot move to the left side, while greater elements move to the right. The same process is repeated
recursively until the array becomes sorted. Quick Sort is widely used because of its fast average performance and
efficient memory usage. It is commonly used in libraries, databases, and real-world systems.
2. Working Principle
The Quick Sort algorithm follows these steps:
1. Choose a pivot element.
2. Rearrange elements around the pivot.
3. Place smaller elements on the left side.
4. Place larger elements on the right side.
5. Recursively apply the same process to subarrays.
Example array: [9, 1, 8, 3, 7, 2, 15, 11, 6, 4]
3. Step-by-Step Example
Pivot = 4
Left Side = [1, 3, 2]
Right Side = [9, 8, 7, 15, 11, 6]
After partition: [1, 3, 2, 4, 9, 8, 7, 15, 11, 6]
Sorting left side: Pivot = 2
Result = [1, 2, 3]
Sorting right side: Pivot = 6
Result = [6, 7, 8, 9, 11, 15]
Final sorted array: [1, 2, 3, 4, 6, 7, 8, 9, 11, 15]
4. Pseudocode
QUICKSORT(array, low, high)
IF low < high
pivot = PARTITION(array, low, high)
QUICKSORT(array, low, pivot-1)
QUICKSORT(array, pivot+1, high)
PARTITION(array, low, high)
pivot = array[high]
i = low - 1
FOR j = low TO high-1
IF array[j] < pivot
swap array[i] and array[j]
swap pivot into correct position
5. Time Complexity
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n²)
The worst case occurs when the pivot divides the array unevenly. This often happens when the smallest or largest
element is repeatedly chosen. The average case performance is very efficient, making Quick Sort one of the fastest
practical sorting algorithms.
6. Space Complexity
Quick Sort uses recursive calls, so extra memory is required for recursion.
Space Complexity:
Average Case = O(log n)
Worst Case = O(n)
Compared to Merge Sort, Quick Sort uses less additional memory.
7. Advantages of Quick Sort
• Very fast in practice.
• Efficient for large datasets.
• Requires less memory than Merge Sort.
• Widely used in real-world applications.
• Good cache performance.
• Easy to implement recursively.
8. Disadvantages of Quick Sort
• Worst-case time complexity is O(n²).
• Recursive implementation may cause stack overflow for very large arrays.
• Performance depends heavily on pivot selection.
• Not stable by default.
9. Applications of Quick Sort
Quick Sort is used in:
• Database systems
• Search engines
• Operating systems
• Data analysis software
• Library sorting functions
• Artificial Intelligence systems
Due to its speed, Quick Sort is preferred in many software systems.
10. Comparison with Other Sorting Algorithms
Bubble Sort:
Very simple but slow for large datasets.
Merge Sort:
Stable and efficient but requires extra memory.
Insertion Sort:
Good for small arrays but inefficient for large arrays.
Quick Sort:
Faster average performance and commonly used in practical applications.
Sorting Algorithms Comparison Table
Algorithm Best Case Average Case Worst Case
Quick Sort O(n log n) O(n log n) O(n²)
Merge Sort O(n log n) O(n log n) O(n log n)
Bubble Sort O(n) O(n²) O(n²)