On this page & study actions
Assessed progress
Sign in and complete the verified MCQs to track mastery.
Unit 2: Divide & Conquer6 min read
Quick Sort is a highly efficient, comparison-based sorting algorithm that leverages the divide and conquer paradigm. Renowned for its speed and in-place sorting capabilities, it is widely used in various applications and is a staple in computer science education.
The Divide and Conquer paradigm is a powerful algorithmic design strategy that breaks down a problem into three steps:
Quick Sort embodies this strategy by partitioning an array around a chosen element (the pivot), then recursively sorting the resulting sub-arrays.
The core idea behind Quick Sort is partitioning. Given an unsorted array of n elements, Quick Sort aims to sort them in non-decreasing order.
Here's how it generally works:
The informal recurrence relation for Quick Sort can be expressed as: Where is the time to sort an array of size , is the number of elements in the left sub-array after partitioning, is the number of elements in the right sub-array, and represents the time taken for the partitioning process itself (scanning through the array).
Let's break down the Quick Sort process with a focus on the partitioning step using two pointers.
i, to the element just after the pivot.j, to the last element of the sub-array.i while arr[i] <= pivot and i is within bounds.j while arr[j] > pivot and j is within bounds.i < j, swap arr[i] and arr[j]. This moves a "large" element to the right and a "small" element to the left.i >= j. This indicates that the pointers have crossed or met.The base case for the recursion is when a sub-array has zero or one element, as it is already sorted.
Let's walk through an example of the partitioning step using the array provided in the source material:
40 20 10 80 60 50 7 30 100
Initial array: [40, 20, 10, 80, 60, 50, 7, 30, 100]
Range: low = 0, high = 8
Pivot: arr[0] = 40
i = 1, j = 8
Step 1: Pointers i=1, j=8. Pivot 40.
Array: [40, 20, 10, 80, 60, 50, 7, 30, 100]
Indices: 0 1 2 3 4 5 6 7 8
^ ^ ^
pivot i ji moves right: arr[1]=20 <= 40, arr[2]=10 <= 40. arr[3]=80 > 40. i stops at index 3.j moves left: arr[8]=100 > 40, arr[7]=30 <= 40. j stops at index 7.i=3 < j=7, swap arr[i] and arr[j] (i.e., arr[3]=80 and ).Array after swap: [40, 20, 10, 30, 60, 50, 7, 80, 100]
Array: [40, 20, 10, 30, 60, 50, 7, 80, 100]
Indices: 0 1 2 3 4 5 6 7 8
^ ^ ^ ^
pivot old i new i old jStep 2: Pointers i=3, j=7. Pivot 40.
i moves right: arr[3]=30 <= 40. (After previous swap, i is still at 3). i increments, arr[4]=60 > 40. i stops at index 4.j moves left: arr[7]=80 > 40. j decrements, arr[6]=7 <= 40. j stops at index 6.i=4 < j=6, swap Array after swap: [40, 20, 10, 30, 7, 50, 60, 80, 100]
Array: [40, 20, 10, 30, 7, 50, 60, 80, 100]
Indices: 0 1 2 3 4 5 6 7 8
^ ^ ^ ^
pivot old i new i old jStep 3: Pointers i=4, j=6. Pivot 40.
i moves right: arr[4]=7 <= 40. i increments, arr[5]=50 > 40. i stops at index 5.j moves left: arr[6]=60 > 40. j decrements, arr[5]=50 > 40. j decrements, arr[4]=7 <= 40. j stops at index 4.i=5 and . Since , the loop terminates.Final step: Swap arr[low] (the pivot 40) with arr[j] (which is arr[4]=7).
Array after final swap: [7, 20, 10, 30, 40, 50, 60, 80, 100]
Array: [7, 20, 10, 30, 40, 50, 60, 80, 100]
Indices: 0 1 2 3 4 5 6 7 8
^ ^
j pivotThe pivot 40 is now at index 4, its final sorted position.
Elements to its left ([7, 20, 10, 30]) are less than 40.
Elements to its right ([50, 60, 80, 100]) are greater than 40.
Quick Sort would now recursively sort [7, 20, 10, 30] and [50, 60, 80, 100].
Here's a C++ implementation of the Quick Sort algorithm:
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap
// Function to partition the array
// Takes the array, lower bound, and upper bound
// Returns the index of the pivot after partitioning
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[low]; // Choosing the first element as the pivot
int i = low + 1; // Left pointer, starts just after pivot
int j = high; // Right pointer, starts at the end
while (true) {
// Find element on left that should be on right
while (i <= j && arr[i] <=
The time complexity of Quick Sort depends heavily on the choice of the pivot and the resulting partitions.
Best Case:
Quick Sort is an in-place sorting algorithm, meaning it sorts the elements within the original array without using significant additional memory.
Average Case:
Worst Case:
A problem-solving paradigm where a problem is broken into smaller subproblems, each solved independently, and their solutions combined to solve the original problem.
The crucial step in Quick Sort where an element from the array is chosen to serve as a reference point for partitioning.
The process of rearranging array elements such that all elements less than or equal to the pivot are placed before it, and all elements greater than or equal to the pivot are placed after it.
A sorting algorithm that transforms the input array directly without requiring significant additional memory space beyond a small constant amount for variables or recursion stack.
Occurs in Quick Sort when pivot selection consistently leads to highly unbalanced partitions, such as always picking the smallest or largest element, resulting in $O(n^2)$ time complexity.
Test your understanding with 5 questions
Which algorithmic paradigm does Quick Sort primarily follow?
What is the main purpose of the 'pivot' element in Quick Sort?
In the context of Quick Sort, what is the average-case time complexity?
Which of the following scenarios is most likely to lead to Quick Sort's worst-case time complexity?
Why is Quick Sort often considered an 'in-place' sorting algorithm?
i >= j), swap the pivot element (which was originally at the start of the sub-array) with arr[j]. This places the pivot in its correct sorted position. The index j is now the final position of the pivot.low to j-1) and the sub-array to the right of the pivot (j+1 to high).arr[7]=30arr[j]arr[4]=60arr[6]=7j=4i >= jAverage Case:
Worst Case:
6 Modules
6 Modules