Your Progress

17/30 completed

57% complete. Continue learning to master DSA!

Quick Sort Algorithm

Quick Sort is an efficient, divide-and-conquer sorting algorithm that uses a pivot element to partition an array and sort it recursively, achieving better average-case performance than many other sorting algorithms.

Key Takeaways

Quick Sort uses the divide-and-conquer paradigm with a pivot element
Average time complexity is O(n log n), but worst case is O(n²)
It's an in-place sorting algorithm with O(log n) space complexity for recursion
Pivot selection strategies affect performance (first, last, random, median-of-three)
Quick Sort is often faster in practice than other O(n log n) algorithms due to better locality of reference

How Quick Sort Works

Quick Sort works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

The Quick Sort Algorithm

Choose a pivot element from the array.
Partition the array around the pivot (elements less than pivot go to the left, elements greater go to the right).
Recursively apply Quick Sort to the sub-arrays created from the partition step.
The base case is when the array has 0 or 1 element, which is already sorted.

Example of Quick Sort

Let's walk through a simple example of sorting [8, 4, 2, 9, 3, 5] using Quick Sort:

Step 1: Choose a pivot (let's use 5)

[8, 4, 2, 9, 3, 5]

Step 2: Partition the array around pivot 5

[4, 2, 3] < 5 < [8, 9]

Step 3: Recursively sort the left partition [4, 2, 3]

Choose pivot 3: [2] < 3 < [4]

Both [2] and [4] are single elements (base case)

Step 4: Recursively sort the right partition [8, 9]

Choose pivot 9: [8] < 9 < []

[8] is a single element (base case)

Step 5: Combine all parts

Final sorted array: [2, 3, 4, 5, 8, 9]

Quick Sort Implementation

JavaScript Implementation

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // Get the index of the pivot element after partition
    const pivotIndex = partition(arr, left, right);
    
    // Recursively sort the sub-arrays
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  
  return arr;
}

function partition(arr, left, right) {
  // Choose the rightmost element as pivot
  const pivot = arr[right];
  
  // Index of smaller element
  let i = left - 1;
  
  // Traverse through all elements
  // compare each element with pivot
  for (let j = left; j < right; j++) {
    // If current element is smaller than the pivot
    if (arr[j] < pivot) {
      // Increment index of smaller element
      i++;
      
      // Swap elements at i and j
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  // Swap pivot element with element at i+1
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  
  // Return the position where partition is done
  return i + 1;
}

// Example usage
const array = [8, 4, 2, 9, 3, 5];
console.log(quickSort(array)); // [2, 3, 4, 5, 8, 9]

Python Implementation

def quick_sort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
        
    if left < right:
        # Get the index of the pivot element after partition
        pivot_index = partition(arr, left, right)
        
        # Recursively sort the sub-arrays
        quick_sort(arr, left, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, right)
        
    return arr

def partition(arr, left, right):
    # Choose the rightmost element as pivot
    pivot = arr[right]
    
    # Index of smaller element
    i = left - 1
    
    # Traverse through all elements
    # compare each element with pivot
    for j in range(left, right):
        # If current element is smaller than the pivot
        if arr[j] < pivot:
            # Increment index of smaller element
            i += 1
            
            # Swap elements at i and j
            arr[i], arr[j] = arr[j], arr[i]
    
    # Swap pivot element with element at i+1
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    
    # Return the position where partition is done
    return i + 1

# Example usage
array = [8, 4, 2, 9, 3, 5]
print(quick_sort(array))  # [2, 3, 4, 5, 8, 9]

Pivot Selection Strategies

The choice of pivot can significantly affect Quick Sort's performance. Here are common pivot selection strategies:

First Element

Simple to implement but performs poorly on already sorted arrays (O(n²) time).

pivot = arr[left];

Last Element

Also simple but has the same issue with sorted arrays.

pivot = arr[right];

Random Element

Reduces the chance of worst-case performance but adds randomness.

pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
pivot = arr[pivotIndex];

Median-of-Three

Uses the median of first, middle, and last elements, which often gives better performance.

mid = left + Math.floor((right - left) / 2);
// Find median of left, middle, right
// and use it as pivot

Note: In production environments, many programming languages implement hybrid sorting algorithms that combine Quick Sort with other algorithms like Insertion Sort for small arrays to maximize efficiency.

Time and Space Complexity

Case	Time Complexity	When It Occurs
Best Case	O(n log n)	When the pivot divides the array into nearly equal halves each time
Average Case	O(n log n)	Expected performance with random data
Worst Case	O(n²)	When the pivot is always the smallest or largest element (e.g., sorted array with first/last element as pivot)
Space Complexity	O(log n)	Space needed for the recursion stack in balanced partitioning

The worst-case space complexity can be O(n) in unbalanced partitioning scenarios, but this is rare with good pivot selection strategies. Quick Sort generally outperforms other O(n log n) algorithms in practice due to better cache locality and fewer comparisons on average.

Advantages and Disadvantages

Advantages

Faster in practice than other O(n log n) algorithms like Merge Sort
In-place sorting with low memory overhead
Good cache performance due to locality of reference
Tail recursion can be optimized to reduce stack space
Adaptive with the right implementations (e.g., Introsort)

Disadvantages

Not stable (relative order of equal elements may change)
Worst-case O(n²) time complexity
Sensitive to pivot selection
Not adaptive in its basic form (doesn't benefit from partially sorted arrays)
Can have deep recursion in worst cases

Applications of Quick Sort

Standard Libraries

Many programming language standard libraries use Quick Sort or its variants as their default sorting algorithm.

Quick Select

A related algorithm that finds the kth smallest element in an unordered list by partitioning like Quick Sort.

Database Systems

Used in database systems for ordering results and internal sorting operations.

Large Datasets

Particularly effective for large datasets that don't fit entirely in memory.

Common Interview Questions

1. Implement Quick Sort with Median-of-Three Pivot

This version selects the median of the first, middle, and last elements as the pivot to improve performance.

function medianOfThree(arr, left, right) {
  const mid = Math.floor((left + right) / 2);
  
  // Sort left, mid, right
  if (arr[left] > arr[mid]) {
    [arr[left], arr[mid]] = [arr[mid], arr[left]];
  }
  if (arr[left] > arr[right]) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
  }
  if (arr[mid] > arr[right]) {
    [arr[mid], arr[right]] = [arr[right], arr[mid]];
  }
  
  // Return the index of the median value
  return mid;
}

function quickSortMedian(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // Use median-of-three pivot selection
    const pivotIndex = medianOfThree(arr, left, right);
    const pivotValue = arr[pivotIndex];
    
    // Move pivot to end temporarily
    [arr[pivotIndex], arr[right]] = [arr[right], arr[pivotIndex]];
    
    // Partition around pivot value
    let i = left;
    for (let j = left; j < right; j++) {
      if (arr[j] <= pivotValue) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }
    
    // Move pivot to its final sorted position
    [arr[i], arr[right]] = [arr[right], arr[i]];
    
    // Recursively sort partitions
    quickSortMedian(arr, left, i - 1);
    quickSortMedian(arr, i + 1, right);
  }
  
  return arr;
}

2. How would you optimize Quick Sort for nearly sorted arrays?

For nearly sorted arrays, you can improve Quick Sort by:

Using median-of-three pivot selection to avoid worst-case scenarios
Switching to Insertion Sort for small subarrays (typically < 10-20 elements)
Implementing a check for already sorted subarrays to skip unnecessary partitioning
Using a hybrid approach like Introsort (combination of Quick Sort, Heap Sort, and Insertion Sort)

Conclusion

Quick Sort is one of the most efficient and widely used sorting algorithms. Its divide-and-conquer approach, combined with good cache locality, makes it faster in practice than many other sorting algorithms despite its O(n²) worst-case time complexity. Understanding Quick Sort and its variants is essential for any programmer or computer scientist.

Remember

The key to Quick Sort's efficiency lies in the choice of pivot and the partitioning strategy. With good pivot selection, you can avoid the worst-case performance and leverage its superior average-case performance in most real-world applications.

Next Steps

To further your understanding of sorting algorithms and related concepts, explore these topics:

Merge Sort

Compare with another divide-and-conquer sorting algorithm

Divide and Conquer

Learn about the general algorithmic paradigm

Recursion

Master the technique at the heart of Quick Sort

Your Progress

Key Takeaways

How Quick Sort Works

The Quick Sort Algorithm

Example of Quick Sort

Quick Sort Implementation

JavaScript Implementation

Python Implementation

Pivot Selection Strategies

First Element

Last Element

Random Element

Median-of-Three

Time and Space Complexity

Advantages and Disadvantages

Advantages

Disadvantages

Applications of Quick Sort

Standard Libraries

Quick Select

Database Systems

Large Datasets

Common Interview Questions

1. Implement Quick Sort with Median-of-Three Pivot

2. How would you optimize Quick Sort for nearly sorted arrays?

Conclusion

Remember

Next Steps

Merge Sort

Divide and Conquer

Recursion

Related Tutorials

Related Tutorials

Merge Sort

Divide and Conquer

Recursion