Quick Sort Partition Lomuto and Hoare in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Lomuto Partition on given array

What is the output index returned by the Lomuto partition function for the array below?

Array: [8, 3, 7, 6, 2, 5, 4, 1]
Pivot is the last element.

DSA C

int lomuto_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;
}

int main() {
    int arr[] = {8, 3, 7, 6, 2, 5, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int p = lomuto_partition(arr, 0, n - 1);
    printf("%d", p);
    return 0;
}

A 5

B 3

C 4

D 6

💡 Hint

Remember Lomuto places pivot at its correct position after partitioning.

Lomuto partition moves elements <= pivot to the left and finally places pivot after them. The pivot 1 ends up at index 0 after swaps.

❓ Predict Output

intermediate

Output of Hoare Partition on given array

What is the index returned by the Hoare partition function for the array below?

Array: [9, 4, 8, 3, 7, 6, 2, 5]
Pivot is the first element.

DSA C

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

int main() {
    int arr[] = {9, 4, 8, 3, 7, 6, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int p = hoare_partition(arr, 0, n - 1);
    printf("%d", p);
    return 0;
}

A 3

B 4

C 5

D 6

💡 Hint

Hoare partition returns the index where left and right pointers cross.

Hoare partition uses two pointers moving inward. The returned index is where pointers cross, here index 3.

🧠 Conceptual

advanced

Difference in pivot placement between Lomuto and Hoare partitions

Which statement correctly describes the difference in pivot placement after Lomuto and Hoare partition schemes?

A Lomuto places pivot at its final sorted position; Hoare does not guarantee pivot's final position.

B Hoare places pivot at its final sorted position; Lomuto does not guarantee pivot's final position.

C Both Lomuto and Hoare always place pivot at its final sorted position.

D Neither Lomuto nor Hoare place pivot at its final sorted position.

💡 Hint

Think about where the pivot ends after partitioning in each scheme.

Lomuto partition always places pivot at its correct sorted index. Hoare partition only ensures elements are partitioned but pivot may not be at final position.

🔧 Debug

advanced

Identify the bug in this Lomuto partition code snippet

What error will this Lomuto partition code produce when run on array [5, 3, 8, 4, 2]?

DSA C

int lomuto_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) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }
    }
    int temp = arr[i];
    arr[i] = arr[high];
    arr[high] = temp;
    return i;
}

A Infinite loop due to missing increment of j.

B No error; code works correctly.

C Segmentation fault due to invalid array access.

D Off-by-one error: i should start at low - 1.

💡 Hint

Check initial value of i and how it affects swapping.

In Lomuto partition, i must start at low - 1 to correctly track elements <= pivot. Starting at low causes incorrect partitioning.

🚀 Application

expert

Number of recursive calls in Quick Sort using Hoare partition

Given an array of 7 distinct elements sorted in descending order, how many recursive calls will Quick Sort make using Hoare partition scheme (excluding the initial call)?

A 13

B 14

C 12

D 6

💡 Hint

Consider worst-case recursion depth and number of calls in Quick Sort with Hoare partition on reverse sorted array.

In worst case (reverse sorted), Quick Sort with Hoare partition makes 2n - 1 calls total. For n=7, total calls = 13, so excluding initial call, recursive calls = 13 - 1 = 12.

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