Quick Sort (Divide and Conquer)
- [8, 3, 1, 7, 0, 10, 2]
- [1, 0, 2, 7, 3, 10, 8]
- [0, 1, 2, 7, 3, 8, 10]
- [0, 1, 2, 3, 7, 8, 10]: SORTED ARRAY
Now, Choose 8 as pivot:
Now Choose 3 as pivot
We can choose any element as the pivot, but for simplicity, we select the last element since it makes the algorithm easier to implement.
Algorithm Steps
- Choose a pivot element
Select one element from the array (commonly first, last, middle, or random). - Partition the array
Rearrange elements so that:
Elements smaller than the pivot go to the left.Elements greater than the pivot go to the right. - Place the pivot in its correct position
After partitioning, the pivot is in its final sorted place. - Recursively apply Quick Sort
Apply Quick Sort to the left sub-array.
Apply Quick Sort to the right sub-array. - Stop condition (Base Case)
If the sub-array has 0 or 1 element, it is already sorted.
Time Complexity:
- Best Case:
O(n log n) - Average Case:
O(n log n) - Worst Case:
O(n2)Already sorted + Bad Pivot (choose)
Space Complexity:
- O(log n)
- Only
Recursionstack takes a space. - Very efficient with space Complexity.
Importance of Quick Sort
- No extra
memory allocation. - Cache friendly.
Partitioningis efficient. (log n)- Randomize pivots avoid worst case.
- Most standard
librariesstill rely on Quick Sort and variant.
Dry Run
Input:
Array: [8, 3, 1, 7, 0, 10, 2]
State Transitions:
Initial Array: [8, 3, 1, 7, 0, 10, 2] quickSort(0, 6) Pivot = 2 After partition: [1, 0, 2, 7, 3, 10, 8] Pivot index = 2 quickSort(0, 1) Pivot = 0 After partition: [0, 1, 2, 7, 3, 10, 8] Pivot index = 0 quickSort(3, 6) Pivot = 8 After partition: [0, 1, 2, 7, 3, 8, 10] Pivot index = 5 quickSort(3, 4) Pivot = 3 After partition: [0, 1, 2, 3, 7, 8, 10] Pivot index = 3
Final State:
Sorted Array:
[0, 1, 2, 3, 7, 8, 10]
function findPivotIndex(arr, startIndex, endIndex) {
let pivot = arr[endIndex];
let pos = startIndex - 1;
// moving all smaller elements to the left
for (let i = startIndex; i < endIndex; i++) {
if (arr[i] < pivot) {
pos++;
[arr[i], arr[pos]] = [arr[pos], arr[i]];
}
}
// moving pivot to correct position
[arr[pos + 1], arr[endIndex]] = [arr[endIndex], arr[pos + 1]];
return pos + 1;
}
function quickSort(arr, startIndex, endIndex) {
if (startIndex < endIndex) {
let pivotIndex = findPivotIndex(arr, startIndex, endIndex);
// calling quickSort for left part
quickSort(arr, startIndex, pivotIndex - 1);
// calling quickSort for right part
quickSort(arr, pivotIndex + 1, endIndex);
return arr;
}
}
let nums = [8, 3, 1, 7, 0, 10, 2];
let startIndex = 0;
let endIndex = nums.length - 1;
console.log(quickSort(nums, startIndex, endIndex));
def findPivotIndex(arr, startIndex, endIndex):
pivot = arr[endIndex]
pos = startIndex - 1
for i in range(startIndex, endIndex):
if arr[i] < pivot:
pos += 1
arr[i], arr[pos] = arr[pos], arr[i]
arr[pos + 1], arr[endIndex] = arr[endIndex], arr[pos + 1]
return pos + 1
def quickSort(arr, startIndex, endIndex):
if startIndex < endIndex:
pivotIndex = findPivotIndex(arr, startIndex, endIndex)
quickSort(arr, startIndex, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, endIndex)
return arr
nums = [8, 3, 1, 7, 0, 10, 2]
print(quickSort(nums, 0, len(nums) - 1))
public class QuickSortExample {
static int findPivotIndex(int[] arr, int startIndex, int endIndex) {
int pivot = arr[endIndex];
int pos = startIndex - 1;
for (int i = startIndex; i < endIndex; i++) {
if (arr[i] < pivot) {
pos++;
int temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
}
}
int temp = arr[pos + 1];
arr[pos + 1] = arr[endIndex];
arr[endIndex] = temp;
return pos + 1;
}
static void quickSort(int[] arr, int startIndex, int endIndex) {
if (startIndex < endIndex) {
int pivotIndex = findPivotIndex(arr, startIndex, endIndex);
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
}
public static void main(String[] args) {
int[] nums = {8, 3, 1, 7, 0, 10, 2};
quickSort(nums, 0, nums.length - 1);
for (int num : nums) {
System.out.print(num + " ");
}
}
}
#include <iostream>
using namespace std;
int findPivotIndex(int arr[], int startIndex, int endIndex) {
int pivot = arr[endIndex];
int pos = startIndex - 1;
for (int i = startIndex; i < endIndex; i++) {
if (arr[i] < pivot) {
pos++;
swap(arr[i], arr[pos]);
}
}
swap(arr[pos + 1], arr[endIndex]);
return pos + 1;
}
void quickSort(int arr[], int startIndex, int endIndex) {
if (startIndex < endIndex) {
int pivotIndex = findPivotIndex(arr, startIndex, endIndex);
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
}
int main() {
int nums[] = {8, 3, 1, 7, 0, 10, 2};
int n = sizeof(nums) / sizeof(nums[0]);
quickSort(nums, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << nums[i] << " ";
}
return 0;
}
#include <stdio.h>
int findPivotIndex(int arr[], int startIndex, int endIndex) {
int pivot = arr[endIndex];
int pos = startIndex - 1;
for (int i = startIndex; i < endIndex; i++) {
if (arr[i] < pivot) {
pos++;
int temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
}
}
int temp = arr[pos + 1];
arr[pos + 1] = arr[endIndex];
arr[endIndex] = temp;
return pos + 1;
}
void quickSort(int arr[], int startIndex, int endIndex) {
if (startIndex < endIndex) {
int pivotIndex = findPivotIndex(arr, startIndex, endIndex);
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
}
int main() {
int nums[] = {8, 3, 1, 7, 0, 10, 2};
int n = sizeof(nums) / sizeof(nums[0]);
quickSort(nums, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", nums[i]);
}
return 0;
}
using System;
class Program {
static int FindPivotIndex(int[] arr, int startIndex, int endIndex) {
int pivot = arr[endIndex];
int pos = startIndex - 1;
for (int i = startIndex; i < endIndex; i++) {
if (arr[i] < pivot) {
pos++;
int temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
}
}
int temp2 = arr[pos + 1];
arr[pos + 1] = arr[endIndex];
arr[endIndex] = temp2;
return pos + 1;
}
static void QuickSort(int[] arr, int startIndex, int endIndex) {
if (startIndex < endIndex) {
int pivotIndex = FindPivotIndex(arr, startIndex, endIndex);
QuickSort(arr, startIndex, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, endIndex);
}
}
static void Main() {
int[] nums = { 8, 3, 1, 7, 0, 10, 2 };
QuickSort(nums, 0, nums.Length - 1);
Console.WriteLine(string.Join(" ", nums));
}
}
