Sorting

Quick Sort

What is Quick Sort?

Quick Sort picks one element as a 'pivot' and uses it to split the rest of the array into two groups — everything smaller goes left of the pivot, everything larger goes right. Each of those groups then gets the same treatment recursively, until the whole array falls into place.

How Does It Work?

Consider this unsorted array: [10, 80, 30, 90, 40, 50, 70]

Partitioning Phase:
1. Choose last element as pivot (70)
2. Rearrange: elements < pivot on left, > pivot on right → [10, 30, 40, 50] [70] [80, 90]
Recursive Phase:
1. Apply same process to left sub-array [10, 30, 40, 50]
2. Apply same process to right sub-array [80, 90]
3. Combine results: [10, 30, 40, 50, 70, 80, 90]
Partition [10, 30, 40, 50]:
Partition [80, 90]:
Combine sorted left + pivot + sorted right:
→

PivotLess than pivotGreater than pivotFully sorted

Algorithm Steps

Choose Pivot:
- Select an element as pivot (commonly last/first/random element)
Partition:
- Reorder array so elements < pivot come before it
- Elements > pivot come after it
- Pivot is now in its final sorted position
Recurse:
- Apply quick sort to left sub-array (elements < pivot)
- Apply quick sort to right sub-array (elements > pivot)

Time Complexity

Best Case: O(n log n) (balanced partitions)
Average Case: O(n log n)
Worst Case: O(n²) (unbalanced partitions)

The log n factor comes from the division steps when partitions are balanced. The n² occurs when the pivot selection consistently creates unbalanced partitions.

Time Complexity Analysis

Space Complexity

Quick Sort is O(log n) space complexity for the call stack in the average case, but can degrade to O(n) in the worst case with unbalanced partitions. It is generally considered an in-place algorithm as it doesn't require significant additional space.

Advantages

Fastest general-purpose in-memory sorting algorithm in practice
In-place algorithm (requires minimal additional memory)
Cache-efficient due to sequential memory access
Can be easily parallelized for better performance

Disadvantages

Not stable (relative order of equal elements may change)
Worst-case O(n²) performance (though rare with proper pivot selection)
Performance depends heavily on pivot selection strategy
Not ideal for linked lists (works best with arrays)

Pivot Selection Strategies

Last element: Simple but can lead to worst-case on sorted arrays
First element: Similar issues as last element
Random element: Reduces chance of worst-case scenarios
Median-of-three: Takes median of first, middle, last elements
Middle element: Often provides good balance

Quick Sort is the algorithm of choice for most standard library sorting implementations (like C's qsort, Java's Arrays.sort for primitives) due to its excellent average-case performance. It's particularly effective for large datasets that fit in memory.

Daily DSA Challenge by Scale Engineer

Test Your Knowledge before moving forward!

Quick Sort Quiz Challenge

How it works:

+1 point for each correct answer
0 points for wrong answers
Earn stars based on your final score (max 5 stars)

Quick Sort Implementation

// Quick Sort in JavaScript
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;
  
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

// Usage
const arr = [10, 7, 8, 9, 1, 5];
console.log("Original:", arr);
console.log("Sorted:", quickSort([...arr]));

Done With the Learning

Mark Quick Sort as done and view it on your dashboard

Explore Sorting Algorithms

Selection Sort

Bubble Sort

Insertion Sort

Merge Sort

Heap Sort