Summary
| Algorithm Name | Quick Sort | |
| Category |  Sorting Algorithms | |
| Core Technique | Pick a pivot, partition elements into smaller and larger sets, then recursively sort the partitions. | |
| Best Case Time Complexity | Ω(n log n) | Linearithmic (log-linear) |
| Average Case Time Complexity | Θ(n log n) | Linearithmic (log-linear) |
| Worst Case Time Complexity | O(n ^ 2) | Quadratic |
| Space / Memory Complexity | O(log n) | Logerithimic |
Intro
Quick sort uses the divide-and-conquer technique. This helps to achieve the O(n log n) time complexity in most of the cases.
With that, it uses a pivoting technique to break down the list of elements into subsets. Then the subsets use the pivoting technique again to sort themselves.
NOTE
The algorithm goes like this-
Pick a pivot element from the list of elements
⇓
Bring all numbers less than the pivot, to the left of the pivot
⇓
Bring all the numbers greater than the pivot, to the right of the pivot
⇓
Repeat the same process for the left and right subsets of the pivot
Space complexity of Quick sort is O(log n), which is better than merge sort. This makes Quick sort a very efficient sorting algorithm.
Use Cases
Quick sort is better than other sorting algorithms, on the average case. Also, the space complexity(which is O(log n)) is very favorable for the in-memory process of a large data set.
Just remember to choose the pivot element properly.
Algorithm Visualizer
Here is how we can visualize Quicksort-
Implementation Steps
Here are the steps we should follow to implement the Merge sort algorithm-
- Choose a Pivot: select an element from the array (first, last, random, or median).
- Partitioning: rearrange the array so that all elements smaller than the pivot are on its left, and all greater are on its right.
- Place Pivot Correctly: after partitioning, the pivot is in its final sorted position.
- Recursively Apply: repeat steps 1–3 on the left and right subarrays (excluding the pivot).
- Base Case: stop when the subarray has zero or one element (already sorted).
NOTE
The execution time of Quick sort depends on choosing a good(more favourable/suitable/balanced) pivot element.
With wrong pivot selection, the time complexity can be O(n^2). This happens when the pivot element is the smallest or the largest element of the list, or very close to those numbers.
Pseudocode
Here is the pseudocode for Quick sort. It will make the implementation steps clear-
# Quick Sort Pseudocode
procedure QuickSort(A, Low, High)
IF Low < High
PivotIndex ← Partition(A, Low, High)
QuickSort(A, Low, PivotIndex - 1)
QuickSort(A, PivotIndex + 1, High)
end procedure
procedure Partition(A, Low, High)
Pivot ← A[High] // choose last element as pivot
I ← Low - 1 // index of smaller element
FOR J ← Low TO High - 1
IF A[J] ≤ Pivot
I ← I + 1
SWAP A[I] ↔ A[J]
SWAP A[I + 1] ↔ A[High]
RETURN I + 1 // final pivot position
end procedure
Implementation
// QuickSort implementation in JavaScript
/**
* Sorts an array in place using the QuickSort algorithm.
* @param {Array<number>} arr - The array to sort.
* @param {number} low - The starting index.
* @param {number} high - The ending index.
* @returns {Array<number>} The sorted array.
*/
function quickSort(arr, low = 0, high = arr.length - 1) {
// Only sort if the subarray has more than one element
if (low < high) {
// Partition the array and get the pivot index
const pivotIndex = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
return arr;
}
/**
* Partitions the array around a pivot element.
* Elements less than or equal to the pivot are moved to the left of the pivot.
* Elements greater than the pivot are moved to the right.
* @param {Array<number>} arr - The array to partition.
* @param {number} low - The starting index.
* @param {number} high - The ending index (pivot).
* @returns {number} The index of the pivot after partitioning.
*/
function partition(arr, low, high) {
const pivot = arr[high]; // Choose the last element as pivot
let i = low - 1; // Index of smaller element
for (let j = low; j < high; j++) {
// If current element is less than or equal to pivot
if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
// Place the pivot in the correct position
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
// Or you can use the following lines to swap without destructuring:
// const temp = arr[i + 1];
// arr[i + 1] = arr[high];
// arr[high] = temp;
return i + 1;
}
export default quickSort;Demo
// Demo for QuickSort
import quickSort from "./quick-sort.js";
const testCases = [
{ name: "Normal array", arr: [10, 7, 8, 9, 1, 5] },
{ name: "Empty array", arr: [] },
{ name: "Single element", arr: [42] },
{ name: "Duplicates", arr: [3, 3, 3, 3] },
{ name: "Negative numbers", arr: [3, -1, 0, -7, 8] },
{ name: "Already sorted", arr: [1, 2, 3, 4, 5] },
{ name: "Reverse sorted", arr: [5, 4, 3, 2, 1] },
{ name: "Large array", arr: Array.from({length: 20}, () => Math.floor(Math.random() * 100)) }
];
for (const { name, arr } of testCases) {
console.log(`\n${name}:`);
console.log('Original array:', arr);
const sorted = quickSort([...arr]);
console.log('Sorted array:', sorted);
}Output:
Normal array:
Original array: [ 10, 7, 8, 9, 1, 5 ]
Sorted array: [ 1, 5, 7, 8, 9, 10 ]
Empty array:
Original array: []
Sorted array: []
Single element:
Original array: [ 42 ]
Sorted array: [ 42 ]
Duplicates:
Original array: [ 3, 3, 3, 3 ]
Sorted array: [ 3, 3, 3, 3 ]
Negative numbers:
Original array: [ 3, -1, 0, -7, 8 ]
Sorted array: [ -7, -1, 0, 3, 8 ]
Already sorted:
Original array: [ 1, 2, 3, 4, 5 ]
Sorted array: [ 1, 2, 3, 4, 5 ]
Reverse sorted:
Original array: [ 5, 4, 3, 2, 1 ]
Sorted array: [ 1, 2, 3, 4, 5 ]
Large array:
Original array: [
65, 86, 73, 80, 12, 22, 14,
34, 29, 72, 47, 12, 99, 56,
41, 69, 22, 98, 5, 48
]
Sorted array: [
5, 12, 12, 14, 22, 22, 29,
34, 41, 47, 48, 56, 65, 69,
72, 73, 80, 86, 98, 99
]Tests
// Test for QuickSort
import quickSort from './quick-sort.js';
import { describe, it, expect } from 'vitest';
describe('QuickSort', () => {
it('sorts an array of numbers', () => {
const arr = [5, 2, 9, 1, 5, 6];
expect(quickSort([...arr])).toEqual([1, 2, 5, 5, 6, 9]);
});
it('sorts an empty array', () => {
expect(quickSort([])).toEqual([]);
});
it('sorts an array with one element', () => {
expect(quickSort([42])).toEqual([42]);
});
it('sorts an array with negative numbers', () => {
const arr = [3, -1, 0, -7, 8];
expect(quickSort([...arr])).toEqual([-7, -1, 0, 3, 8]);
});
it('sorts an already sorted array', () => {
const arr = [1, 2, 3, 4, 5];
expect(quickSort([...arr])).toEqual([1, 2, 3, 4, 5]);
});
it('sorts a reverse sorted array', () => {
const arr = [5, 4, 3, 2, 1];
expect(quickSort([...arr])).toEqual([1, 2, 3, 4, 5]);
});
it('sorts an array with all duplicates', () => {
const arr = [7, 7, 7, 7];
expect(quickSort([...arr])).toEqual([7, 7, 7, 7]);
});
it('sorts an array with floats', () => {
const arr = [3.1, 2.2, 5.5, 1.0];
expect(quickSort([...arr])).toEqual([1.0, 2.2, 3.1, 5.5]);
});
it('sorts an array of strings', () => {
const arr = ['banana', 'apple', 'cherry'];
expect(quickSort([...arr])).toEqual(['apple', 'banana', 'cherry']);
});
it('sorts a large array', () => {
const arr = Array.from({length: 1000}, () => Math.floor(Math.random() * 10000));
const sorted = quickSort([...arr]);
expect(sorted).toEqual([...arr].sort((a, b) => a - b));
});
});
Source Code
| Source Code of | Implementation Code | Demo Code | Test Case Code | Benchmark Code |
|---|---|---|---|---|
| Quick Sort Visualizer | Quick Sort Visualizer – GitHub | |||
| Quick Sort Pseudocode | Quick Sort Pseudocode – GitHub | |||
| Quick Sort Implementation in JS | Quick Sort Implementation in JS – GitHub | Quick Sort Demo in JS – GitHub | Quick Sort Tests in JS – GitHub | Quick Sort Benchmark in JS – GitHub |