Quick Sort Algorithm in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Quick Sort algorithm?

Quick Sort works by picking a 'pivot' element and then rearranging the array so that all elements smaller than the pivot come before it, and all larger elements come after it. This process is repeated recursively on the smaller parts.

beginner

What role does the 'pivot' play in Quick Sort?

The pivot is the element used to split the array into two parts: elements less than the pivot and elements greater than the pivot. It helps organize the array around it for sorting.

intermediate

Explain the partition step in Quick Sort.

Partitioning rearranges the array so that elements less than the pivot are on the left, and elements greater than the pivot are on the right. The pivot ends up in its correct sorted position.

beginner

What is the average time complexity of Quick Sort?

The average time complexity of Quick Sort is O(n log n), where n is the number of elements to sort.

beginner

Why can Quick Sort be faster than other sorting algorithms like Bubble Sort?

Quick Sort uses a divide and conquer approach, breaking the problem into smaller parts and sorting them efficiently. This reduces the number of comparisons compared to simple methods like Bubble Sort.

What is the first step in the Quick Sort algorithm?

A Merge two sorted arrays

B Choose a pivot element

C Swap the first and last elements

D Count the number of elements

Quick Sort starts by choosing a pivot element to divide the array.

After partitioning, where is the pivot element located?

A In its correct sorted position

B At the end of the array

C Randomly in the array

D At the beginning of the array

The pivot ends up in its correct sorted position after partitioning.

What is the worst-case time complexity of Quick Sort?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

In the worst case, Quick Sort can take O(n^2) time, for example when the smallest or largest element is always chosen as pivot.

Which technique does Quick Sort use to sort the array?

A Dynamic programming

B Greedy algorithm

C Brute force

D Divide and conquer

Quick Sort uses divide and conquer by breaking the array into smaller parts.

What happens after partitioning in Quick Sort?

A Quick Sort is called recursively on subarrays

B The array is merged

C The algorithm stops

D The pivot is removed

After partitioning, Quick Sort is called recursively on the left and right subarrays.

Describe how Quick Sort sorts an array step-by-step.

Think about dividing the array around a pivot and sorting smaller parts.

Explain why Quick Sort is efficient on average but can be slow in the worst case.

Consider how the pivot choice impacts the size of subarrays.

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