Quick Sort Partition Lomuto and Hoare in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Lomuto partition scheme in Quick Sort?

Lomuto partition picks the last element as pivot, then rearranges the array so that elements less than pivot come before it, and elements greater or equal come after. It returns the pivot's final position.

intermediate

How does Hoare's partition scheme differ from Lomuto's in Quick Sort?

Hoare's partition uses two indices starting from both ends moving towards each other, swapping elements out of place. It returns an index that may not be the pivot's final position but splits the array for recursive calls.

beginner

Code snippet: What does this Lomuto partition function return? 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++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return i + 1; }

This function returns the index of the pivot after placing it in its correct sorted position, with all smaller elements to the left and all greater or equal elements to the right.

intermediate

Why can Hoare's partition be more efficient than Lomuto's?

Hoare's partition typically does fewer swaps and comparisons because it stops when pointers cross, making it faster especially on large or partially sorted arrays.

intermediate

What is a key limitation of Lomuto partition compared to Hoare's?

Lomuto partition can perform poorly on arrays with many duplicate elements and may cause unbalanced partitions, leading to worse performance.

In Lomuto partition, which element is chosen as the pivot?

A A random element

B The last element

C The middle element

D The first element

Lomuto partition always picks the last element as the pivot.

What does Hoare's partition return?

A The largest element index

B The final pivot position

C The smallest element index

D An index where left and right pointers crossed

Hoare's partition returns the index where the two pointers cross, which is used to split the array.

Which partition scheme generally uses fewer swaps?

A Hoare

B Lomuto

C Both use the same

D Depends on pivot

Hoare's partition usually uses fewer swaps because it swaps only when necessary.

In Lomuto partition, what happens to elements equal to the pivot during partitioning?

A They go to the right side

B They stay in place

C They go to the left side

D They are removed

Elements equal to the pivot are placed on the right side in Lomuto partition.

Which partition scheme can cause unbalanced partitions with many duplicates?

A Both

B Hoare

C Lomuto

D Neither

Lomuto partition can cause unbalanced partitions when many duplicates exist.

Explain step-by-step how Lomuto partition rearranges an array around the pivot.

Think about how elements less than pivot are grouped on the left.

Describe how Hoare's partition uses two pointers to split the array.

Focus on how pointers move inward and swap elements.

Practice

1. What is the main difference between Lomuto and Hoare partition schemes in Quick Sort?

easy

A. Lomuto uses recursion, Hoare uses iteration

B. Lomuto sorts in descending order, Hoare sorts in ascending order

C. Lomuto uses one pointer, Hoare uses two pointers moving inward

D. Lomuto swaps only equal elements, Hoare swaps all elements

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses a single pointer to track the boundary of smaller elements and swaps elements accordingly.

2. Step 2: Understand Hoare partition

   Hoare partition uses two pointers starting from both ends moving inward to swap elements that are on the wrong side.

3. Final Answer:

   Lomuto uses one pointer, Hoare uses two pointers moving inward -> Option C

4. Quick Check:

   Pointer count difference = A [OK]

Hint: Remember: Lomuto one pointer, Hoare two pointers [OK]

Common Mistakes:

• Confusing sorting order difference
• Thinking both use same pointer method
• Assuming Hoare uses recursion only

2. Which of the following is the correct syntax for Lomuto partition function header in C?

easy

A. int lomutoPartition(int arr[], int low, int high);

B. void lomutoPartition(int arr[], int low, int high);

C. int lomutoPartition(int arr, int low, int high);

D. int lomutoPartition(int arr[], int high, int low);

Solution

1. Step 1: Check parameter types

   Array must be passed as int arr[], and low and high as int indices.

2. Step 2: Check return type

   Lomuto partition returns an int index, so return type must be int.

3. Final Answer:

   int lomutoPartition(int arr[], int low, int high); -> Option A

4. Quick Check:

   Correct signature = A [OK]

Hint: Partition returns index, so return type is int [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int arr instead of int arr[]
• Swapping low and high parameters

3. What is the output array after applying Lomuto partition on arr = [8, 3, 7, 6, 2] with low=0 and high=4?

medium

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

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

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

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

Solution

1. Step 1: Choose pivot and initialize pointers

   Pivot is arr[high] = 2. Initialize i = low - 1 = -1.

2. Step 2: Iterate and swap elements smaller than pivot

   Traverse j from 0 to 3:
   - j=0: arr[0]=8 > 2, no swap
   - j=1: arr[1]=3 > 2, no swap
   - j=2: arr[2]=7 > 2, no swap
   - j=3: arr[3]=6 > 2, no swap
   After loop, swap arr[i+1]=arr[0] and pivot arr[4]=2.

3. Final Answer:

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

4. Quick Check:

   Pivot 2 placed at start = A [OK]

Hint: Pivot is last element in Lomuto [OK]

Common Mistakes:

• Swapping elements incorrectly with pivot
• Using wrong pivot index
• Confusing i and j pointers

4. Identify the bug in this Hoare partition code snippet:

int hoarePartition(int arr[], int low, int high) {
  int pivot = arr[low];
  int i = low - 1, j = high + 1;
  while (1) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);
    if (i >= j) return j;
    swap(&arr[i], &arr[j]);
  }
}

medium

A. Return statement should be i, not j

B. Swap function is missing

C. Pivot should be arr[high], not arr[low]

D. Pointers i and j are initialized incorrectly

Solution

1. Step 1: Examine the swap call

   The code calls swap(&arr[i], &arr[j]); but the swap function is not defined in the snippet, causing a compilation error.

2. Step 2: Verify other components

   Pointer initialization i=low-1, j=high+1 is correct for do-while structure; pivot at low ok; return j standard.

3. Final Answer:

   Swap function is missing -> Option B

4. Quick Check:

   Undefined swap function = C [OK]

Hint: Swap must be defined before calling [OK]

Common Mistakes:

• Missing swap function definition
• Confusing Hoare pointer initialization
• Returning wrong index after partition

5. Given the array [10, 80, 30, 90, 40, 50, 70], what is the final array after applying Hoare partition with low=0 and high=6?

hard

A. [10, 80, 30, 90, 40, 50, 70]

B. [10, 30, 40, 50, 70, 90, 80]

C. [10, 30, 40, 50, 80, 70, 90]

D. [10, 30, 40, 50, 70, 80, 90]

Solution

1. Step 1: Initialize pointers and pivot

   Pivot = arr[low] = 10, i = low - 1 = -1, j = high + 1 = 7.

2. Step 2: Move pointers

   do { i++; } while (arr[i] < 10); i++ to 0, arr[0]=10 not < 10, i=0.
   do { j--; } while (arr[j] > 10); j-- from 7: 6(70>10),5(50>10),4(40>10),3(90>10),2(30>10),1(80>10),0(10 not >10), j=0.
   i=0 >= j=0, return 0. No swap.

3. Final Answer:

   [10, 80, 30, 90, 40, 50, 70] -> Option A

4. Quick Check:

   Array unchanged (all ≥ pivot) = D [OK]

Hint: Hoare partition swaps inward until pointers cross [OK]

Common Mistakes:

• Assuming full sort after one partition
• Confusing pivot position after partition
• Mis-tracing pointer movements