Quick Sort Algorithm in DSA Java

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorting each part separately until the whole list is sorted.

Analogy: Imagine sorting a deck of cards by picking one card as a divider, then putting all smaller cards to the left and bigger cards to the right, and repeating this for each side until sorted.

Array: [7, 2, 9, 4, 3]
Pivot chosen: 3
Partitioned: [2] -> 3 -> [9, 4, 7]

Dry Run Walkthrough

Input: array: [7, 2, 9, 4, 3]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot as last element 3, partition array around pivot

[2, 3, 9, 4, 7]

Why: We place elements smaller than 3 to the left and bigger to the right

Step 2: Recursively quick sort left part [2]

[2]

Why: Single element is already sorted

Step 3: Recursively quick sort right part [9, 4, 7]

[4, 7, 9]

Why: Sort elements greater than pivot by repeating partition

Step 4: Choose pivot 7 in right part, partition around 7

[4, 7, 9]

Why: Place elements smaller than 7 to left, bigger to right

Step 5: Recursively quick sort left part [4]

[4]

Why: Single element is sorted

Step 6: Recursively quick sort right part [9]

[9]

Why: Single element is sorted

Result:

[2, 3, 4, 7, 9]

Annotated Code

DSA Java

public class QuickSort {

    // Function to swap two elements in the array
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Partition function to place pivot correctly
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // choose last element as pivot
        int i = low - 1; // index of smaller element

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++; // move smaller element index forward
                swap(arr, i, j); // swap smaller element to correct position
            }
        }
        swap(arr, i + 1, high); // place pivot after smaller elements
        return i + 1; // return pivot index
    }

    // QuickSort recursive function
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high); // partition array
            quickSort(arr, low, pi - 1); // sort left part
            quickSort(arr, pi + 1, high); // sort right part
        }
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {7, 2, 9, 4, 3};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

int pivot = arr[high]; // choose last element as pivot

select pivot to divide array

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

move elements smaller than pivot to left side

swap(arr, i + 1, high); return i + 1;

place pivot in correct sorted position

if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }

recursively sort left and right parts

Output

2 3 4 7 9 

Complexity Analysis

Time: O(n log n) average case because the array is divided into halves recursively; O(n^2) worst case when pivot divides array unevenly

Space: O(log n) due to recursion stack in average case

vs Alternative: Better than simple sorting like bubble sort O(n^2) on average because it divides and conquers instead of comparing all pairs

Edge Cases

empty array

function returns immediately without changes

DSA Java

if (low < high) {

array with one element

already sorted, recursion stops immediately

DSA Java

if (low < high) {

array with all equal elements

partition places pivot but no swaps needed, sorts correctly

DSA Java

if (arr[j] <= pivot) {

When to Use This Pattern

When you need to sort an array efficiently by dividing it into smaller parts, use Quick Sort because it sorts in place and is fast on average.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping pivot to correct position
Fix: Always swap pivot to its correct place after partitioning

Mistake: Not updating indices correctly during partition
Fix: Increment i only when a smaller element is found and swap properly

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting subarrays recursively.

Use Quick Sort when you want an efficient, in-place sorting algorithm with good average performance.

The key insight is partitioning the array so that elements smaller than pivot go left and bigger go right, then sorting those parts separately.

Practice

1. What is the main idea behind the Quick Sort algorithm?

easy

A. Insert elements one by one into their correct position

B. Compare every element with every other element and swap if needed

C. Merge two sorted arrays into one sorted array

D. Divide the array into smaller parts using a pivot and sort them recursively

Solution

1. Step 1: Understand Quick Sort's approach

   Quick Sort picks a pivot element and divides the array into parts smaller and larger than the pivot.

2. Step 2: Recursive sorting of parts

   It then sorts these parts recursively, combining them to get the sorted array.

3. Final Answer:

   Divide the array into smaller parts using a pivot and sort them recursively -> Option D

4. Quick Check:

   Quick Sort = Divide and conquer [OK]

Hint: Remember: Quick Sort uses a pivot to split and sort recursively [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort merges arrays like Merge Sort
• Assuming Quick Sort inserts elements one by one

2. Which of the following is the correct way to declare the partition method header in Java for Quick Sort?

easy

A. int partition(int arr[], low, high)

B. public int partition(int[] arr, int low, int high)

C. void partition(int[] arr, int low, int high)

D. public static partition(int[] arr, int low, int high)

Solution

1. Step 1: Check Java method declaration syntax

   Java methods must specify access modifier, return type, method name, and parameter types with names.

2. Step 2: Validate each option

   public int partition(int[] arr, int low, int high) correctly declares a public method returning int with parameters typed and named properly.

3. Final Answer:

   public int partition(int[] arr, int low, int high) -> Option B

4. Quick Check:

   Java method syntax = public int partition(int[] arr, int low, int high) [OK]

Hint: Remember Java method syntax: access + return type + name + parameters [OK]

Common Mistakes:

• Omitting return type
• Missing parameter types
• Incorrect order of parameters

3. What will be the output array after the first partition call on arr = [8, 3, 7, 6, 2] with pivot as last element?

medium

A. [2, 3, 6, 7, 8]

B. [3, 2, 6, 7, 8]

C. [2, 3, 7, 6, 8]

D. [8, 3, 7, 6, 2]

Solution

1. Step 1: Choose pivot and partition

   Pivot is last element 2. Move elements smaller than 2 to left.

2. Step 2: Rearrange array

   No elements smaller than 2, so swap 2 with first element 8. Result: [2, 3, 6, 7, 8]

3. Step 3: Check order after partition

   Elements less than pivot (none) are left, others right. No further swaps in first partition.

4. Final Answer:

   [2, 3, 6, 7, 8] -> Option A

5. Quick Check:

   Pivot 2 placed correctly, smaller left, larger right [OK]

Hint: Pivot is last element; smaller elements go left [OK]

Common Mistakes:

• Not swapping pivot correctly
• Assuming all smaller elements are sorted immediately
• Confusing pivot position after partition

4. Identify the error in this Quick Sort partition code snippet:

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

medium

A. Pivot should be arr[low] instead of arr[high]

B. Loop condition should be j <= high

C. Variable i should start at low - 1

D. Swap should happen only if arr[j] <= pivot

Solution

1. Step 1: Analyze initialization of i

   In Lomuto partition, i starts at low - 1 to track smaller elements index before loop.

2. Step 2: Check loop and swaps

   Starting i at low causes incorrect swaps and pivot placement.

3. Final Answer:

   Variable i should start at low - 1 -> Option C

4. Quick Check:

   i = low - 1 for correct partition [OK]

Hint: i starts one before low to track smaller elements [OK]

Common Mistakes:

• Starting i at low causes wrong partition
• Changing pivot position incorrectly
• Using wrong loop bounds

5. Given an array with many duplicate elements, which modification to Quick Sort improves performance most?

hard

A. Use a three-way partitioning to separate less, equal, and greater elements

B. Always pick the first element as pivot

C. Use Bubble Sort instead for duplicates

D. Skip sorting duplicates by checking each element

Solution

1. Step 1: Understand problem with duplicates

   Standard Quick Sort performs poorly with many duplicates due to repeated swaps.

2. Step 2: Apply three-way partitioning

   Three-way partitioning divides array into less than, equal to, and greater than pivot, reducing unnecessary work.

3. Step 3: Evaluate other options

   Picking first element or skipping sorting duplicates doesn't improve performance reliably; Bubble Sort is inefficient.

4. Final Answer:

   Use a three-way partitioning to separate less, equal, and greater elements -> Option A

5. Quick Check:

   Three-way partitioning = better with duplicates [OK]

Hint: Use three-way partitioning for arrays with many duplicates [OK]

Common Mistakes:

• Picking fixed pivot without randomization
• Ignoring duplicates in partitioning
• Switching to inefficient sorts unnecessarily