Quick Sort Algorithm in DSA Java - Build from Scratch

Quick Sort Algorithm

📖 Scenario: You are helping a librarian organize a list of book IDs in ascending order. The librarian wants to use the Quick Sort algorithm to sort the list efficiently.

🎯 Goal: Build a Java program that uses the Quick Sort algorithm to sort an array of integers representing book IDs.

📋 What You'll Learn

Create an integer array called bookIDs with the exact values: 34, 7, 23, 32, 5, 62

Create an integer variable called high that stores the last index of the bookIDs array

Write a quickSort method that takes the array, a low index, and a high index, and sorts the array using the Quick Sort algorithm

Write a partition method that helps quickSort by selecting a pivot and arranging elements

Print the sorted bookIDs array after sorting

💡 Why This Matters

🌍 Real World

Quick Sort is used in many software systems to efficiently sort data like lists of IDs, names, or other records.

💼 Career

Understanding Quick Sort helps in technical interviews and improves problem-solving skills for software development roles.

1

Create the array of book IDs

Create an integer array called bookIDs with these exact values: 34, 7, 23, 32, 5, 62

DSA Java

# Create the integer array bookIDs with the given values
# Your code here

Hint

Use int[] bookIDs = {34, 7, 23, 32, 5, 62}; to create the array.

2

Create the high index variable

Create an integer variable called high that stores the last index of the bookIDs array

DSA Java

public class QuickSortExample {
    public static void main(String[] args) {
        int[] bookIDs = {34, 7, 23, 32, 5, 62};
        // Create the variable high to store last index
        // Your code here
    }
}

Hint

Use int high = bookIDs.length - 1; to get the last index.

3

Write the Quick Sort and Partition methods

Write a quickSort method that takes an integer array arr, an integer low, and an integer high, and sorts the array using the Quick Sort algorithm. Also write a partition method that selects the last element as pivot and partitions the array accordingly.

DSA Java

public class QuickSortExample {
    public static void main(String[] args) {
        int[] bookIDs = {34, 7, 23, 32, 5, 62};
        int high = bookIDs.length - 1;
        // Your code here: write quickSort and partition methods
    }
}

Hint

The quickSort method calls itself recursively and uses partition to split the array around a pivot.

4

Print the sorted array

Print the sorted bookIDs array after calling quickSort. Use a for loop to print each element separated by spaces.

DSA Java

public class QuickSortExample {
    public static void main(String[] args) {
        int[] bookIDs = {34, 7, 23, 32, 5, 62};
        int high = bookIDs.length - 1;
        quickSort(bookIDs, 0, high);
        // Print the sorted bookIDs array
        // Your code here
    }

    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 int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

Hint

Use a for loop to print each element followed by a space.

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