Quick Sort Algorithm

Generated on 2025-07-10 02:05:34 Algorithm Cheatsheet for Technical Interviews

---

Quick Sort Cheat Sheet

1. Quick Overview

• What it is: A divide-and-conquer sorting algorithm. It picks an element as a pivot and partitions the given array around the pivot.
• When to Use: Generally, when you need a fast, in-place sorting algorithm. It performs well on average, but be mindful of worst-case scenarios. Often used as a system sort function.
• Key Idea: Partition the array into smaller sub-arrays around a chosen pivot element, such that all elements less than the pivot are on its left and all elements greater than the pivot are on its right. Recursively apply this process to the sub-arrays.

2. Time & Space Complexity

Case	Time Complexity	Space Complexity
Best	O(n log n)	O(log n)
Average	O(n log n)	O(log n)
Worst	O(n^2)	O(n)

• Explanation:
  • Time: Best and average cases occur when the pivot consistently divides the array into nearly equal halves. The worst case happens when the pivot is always the smallest or largest element, leading to highly unbalanced partitions.
  • Space: The space complexity is primarily due to the recursive calls. In the best and average cases, the recursion depth is logarithmic. In the worst case, the recursion depth can be linear. In-place implementations can reduce space complexity.

3. Implementation

Python

def quicksort(arr):
    """
    Sorts an array using the Quick Sort algorithm.

    Args:
        arr: The array to be sorted.

    Returns:
        The sorted array.
    """
    if len(arr) < 2:
        return arr  # Base case: already sorted

    pivot = arr[0]  # Choose the first element as the pivot
    less = [i for i in arr[1:] if i <= pivot]  # Elements less than or equal to pivot
    greater = [i for i in arr[1:] if i > pivot]  # Elements greater than pivot

    return quicksort(less) + [pivot] + quicksort(greater)

# Example usage
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quicksort(arr)
print("Sorted array:", sorted_arr) # Output: Sorted array: [1, 5, 7, 8, 9, 10]

# In-place Quick Sort (more efficient for larger arrays)
def quicksort_in_place(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)

        quicksort_in_place(arr, low, pi-1)  # Before pi
        quicksort_in_place(arr, pi+1, high) # After pi

def partition(arr, low, high):
    pivot = arr[high]  # Choose rightmost element as pivot
    i = low - 1       # Index of smaller element
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Swap

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Example usage (in-place)
arr = [10, 7, 8, 9, 1, 5]
quicksort_in_place(arr, 0, len(arr)-1)
print("Sorted array (in-place):", arr) # Output: Sorted array (in-place): [1, 5, 7, 8, 9, 10]

• Complexity Analysis:
  • quicksort(arr): O(n log n) average/best case, O(n^2) worst case time complexity. O(n) space complexity because new lists are created.
  • quicksort_in_place(arr, low, high): O(n log n) average/best case, O(n^2) worst case time complexity. O(log n) average/best case, O(n) worst case space complexity.

Java

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);  // Before pi
            quickSort(arr, pi + 1, high); // After pi
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1); // index of smaller element
        for (int j = low; j < high; j++) {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot) {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.print("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

• Complexity Analysis: O(n log n) average/best case, O(n^2) worst case time complexity. O(log n) average/best case, O(n) worst case space complexity.

C++

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

• Complexity Analysis: O(n log n) average/best case, O(n^2) worst case time complexity. O(log n) average/best case, O(n) worst case space complexity.

4. Common Patterns

• Choosing the Pivot:
  • First Element: Simple but can lead to worst-case scenarios if the array is already sorted or nearly sorted.
  • Last Element: Similar to the first element, prone to worst-case performance.
  • Random Element: Helps avoid worst-case scenarios by introducing randomness.
  • Median-of-Three: Selects the median of the first, middle, and last elements as the pivot. This is a good compromise between simplicity and avoiding worst-case performance.
• Partitioning:
  • Lomuto Partition Scheme: (Used in the examples above) Simple to implement.
  • Hoare Partition Scheme: More efficient in practice, especially for already sorted arrays. Requires careful handling of indices.
• Tail Recursion Optimization: Some compilers can optimize tail-recursive calls into iterative loops, reducing stack usage.

5. Pro Tips

• Pivot Selection is Key: A good pivot leads to balanced partitions and faster sorting. Consider randomized pivot selection or median-of-three.
• Handling Duplicates: When there are many duplicate elements, the standard partitioning can lead to poor performance. Consider a 3-way partition (less than, equal to, greater than pivot).
• Switching to Insertion Sort for Small Subarrays: Quick Sort has overhead due to recursion. For small subarrays (e.g., less than 10 elements), Insertion Sort can be faster. This is called “Introsort”.
• Worst-Case Avoidance: If you suspect the input might be nearly sorted, use a randomized pivot selection or consider using a more robust sorting algorithm like Merge Sort (which guarantees O(n log n) time complexity).
• Space Optimization: The in-place version uses O(log n) space on average, while the non-in-place version uses O(n) space. Choose the in-place version when memory is a constraint.

6. Practice Problems

• LeetCode 912. Sort an Array: Implement Quick Sort to sort an array of integers. (Good for basic practice)
• LeetCode 215. Kth Largest Element in an Array: Use Quick Sort’s partitioning step to find the Kth largest element without fully sorting the array. (Excellent for understanding the partitioning process)
• LeetCode 75. Sort Colors: Sort an array containing only 0s, 1s, and 2s. This can be solved with a modified partitioning scheme (Dutch National Flag problem).

7. Templates

These templates are designed to be easy to copy and paste into your coding environment. They provide a basic structure for implementing Quick Sort in each language. Remember to adapt the code to your specific needs.

C++ Template

#include <iostream>
#include <vector>

using namespace std;

// Function to partition the array (Lomuto scheme)
int partition(vector<int>& arr, int low, int high) {
    // Implement partition logic here
    return 0; // Placeholder
}

// Quick Sort function
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // Partition the array
        int pi = partition(arr, low, high);

        // Recursively sort sub-arrays
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = { /* Your array here */ };
    int n = arr.size();

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Python Template

def partition(arr, low, high):
    # Implement partition logic here
    return 0 # Placeholder

def quicksort_in_place(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)

        quicksort_in_place(arr, low, pi-1)
        quicksort_in_place(arr, pi+1, high)


if __name__ == "__main__":
    arr = [ /* Your array here */ ]
    quicksort_in_place(arr, 0, len(arr)-1)
    print("Sorted array:", arr)

Java Template

public class QuickSortTemplate {

    public static int partition(int[] arr, int low, int high) {
        // Implement partition logic here
        return 0; // Placeholder
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = { /* Your array here */ };
        quickSort(arr, 0, arr.length - 1);

        System.out.print("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}