data structures and algorithms

    The Quick Sort algorithm sorts an array by picking a pivot, partitioning the other items around it, and repeating on the smaller parts. Use the visualization below to run it, pause it, step through it, and even step backward. ▶ Play⏮ BackStep ⏭↺ ResetRun to completionShuffle SpeedVery SlowSlowNormalFastVery Fast PivotLast elementFirst elementMiddle elementRandom element Size (5–60) Min Max Generate new array Apply arrayUnsortedP = pivot? = compared⇄ = swapped✓ = final positioni = partition boundaryactive subarray Operation log Recursive calls Complexity (theory): best O(n log n), average O(n log n), worst O(n²). Extra space: O(log n) stack when balanced, O(n) worst case. In-place partitioning, usually not stable. Real behavior depends on pivot choice, input and implementation. The counters above are measured for your array only. Introduction to Quick Sort Quick Sort is a comparison-based sorting algorithm and one of the best-known divide and conquer algorithms. Developers use it because it is simple, sorts in place, and is fast on many real inputs. Its key idea is partitioning: rearrange items so the pivot lands in its final position, with items that belong before it on one side and items that belong after it on the other. Learning Quick Sort is a great way to understand sorting algorithms and recursion. What Is the Quick Sort Algorithm? The Quick Sort algorithm sorts an array by choosing one element, the pivot, and partitioning the rest around it. After partitioning, the pivot never moves again. Quick Sort then sorts the left part and the right part the same way. Take [3, 1, 2]. With pivot 2, the value 1 goes left and 3 stays right, giving [1, 2, 3]. Each step shrinks the problem until pieces are too small to need sorting. How Quick Sort Works Step by Step Choose a pivot. Partition the array around the pivot. Recursively sort the left subarray. Recursively sort the right subarray. Finish when each subarray has zero or one element. The exact moves in step 2 depend on the partition scheme. This page uses the Lomuto scheme for every pivot strategy: the chosen pivot is first swapped to the end of the subarray, then partitioned. Its invariant: while scanning, items from the start up to boundary i hold values less than or equal to the pivot, and items from i up to the scan position hold values greater than the pivot. Because of the “less than or equal” rule, equal values may sit on the left, so do not assume everything on the left is strictly smaller. Understanding the Pivot in Quick Sort The pivot is the reference value for a partition. Pivot choice matters because it decides how even the two parts are. Common strategies: First element: easy, but slow on already sorted input. Last element: also easy and equally weak on sorted input. Middle element: handles sorted and reverse-sorted arrays well. Note that the middle index is not the median value. Random element: makes consistently bad splits unlikely. Median of three (optional): use the median of the first, middle and last values for better balance. Try each strategy in the visualization on a sorted array and compare the comparison counts. Quick Sort Example With a Step-by-Step Walkthrough Array [8, 3, 1, 7, 0, 10, 2], Lomuto partition, last element as pivot. Pivot is 2, boundary i = 0. Scan: 8 and 3 are greater than 2, so nothing moves. 1 is at most 2, so swap it with index 0: [1, 3, 8, 7, 0, 10, 2], i = 1. 7 is greater. 0 is at most 2, so swap with index 1: [1, 0, 8, 7, 3, 10, 2], i = 2. 10 is greater. Place the pivot: swap index 2 with the end: [1, 0, 2, 7, 3, 10, 8]. The 2 is final. Left part [1, 0], pivot 0: nothing is smaller, so swap 1 and 0 to get [0, 1]. Right part [7, 3, 10, 8], pivot 8: 7 and 3 stay in the left group, 10 is greater, then swap 10 and 8: [7, 3, 8, 10]. Sort [7, 3] with pivot 3: swap to [3, 7]. The final array is [0, 1, 2, 3, 7, 8, 10]. Quick Sort Pseudocode quickSort(A, lo, hi): if lo >= hi: return // base case p = partition(A, lo, hi) quickSort(A, lo, p – 1) quickSort(A, p + 1, hi) partition(A, lo, hi): // pivot = A[hi] i = lo for j = lo to hi – 1: if A[j] <= A[hi]: swap A[i], A[j]; i = i + 1 swap A[i], A[hi] return i // pivot’s final index The base case stops recursion on zero or one element. The partition function returns the pivot’s final index, which the recursive calls use to exclude it. Quick Sort Implementation in JavaScript function quickSort(input) { const a = […input]; // copy: input is not modified const sort = (lo, hi) => { if (lo >= hi) return; // handles [] and [x] const p = partition(lo, hi); sort(lo, p – 1); sort(p + 1, hi); }; const partition = (lo, hi) => { const pivot = a[hi]; let i = lo; for (let j = lo; j < hi; j++) { if (a[j] <= pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; } } [a[i], a[hi]] = [a[hi], a[i]]; return i; }; sort(0, a.length – 1); return a; } The function copies the input, so the original stays unchanged. The partition loop moves small values to the left of boundary i, and the final swap puts the pivot in place. For other pivot strategies, swap the chosen element to index hi first. Time Complexity of Quick Sort Quick Sort time complexity depends on partition balance. When partitions are roughly even, there are about log n levels and each level does O(n) work, so time is O(n log n). If every partition is extremely lopsided, such as a sorted array with a first or last pivot, there are n levels and the time grows