Quick Sort Partition Lomuto and Hoare in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in an array.

DSA C

void swap(int *a, int *b) {
    int temp = *a;
    *a = [1];
    *b = temp;
}

Drag options to blanks, or click blank then click option'

Atemp

B*b

Ca

D*a

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning temp to *a instead of *b.

Using variable names without dereferencing pointers.

The swap function exchanges the values pointed by a and b. We assign *a = *b to copy the value from b to a.

2fill in blank

medium

Complete the Lomuto partition function to return the correct pivot index.

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] [1] pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

Drag options to blanks, or click blank then click option'

A<

B<=

C>=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' or '>' which moves larger elements incorrectly.

Using '<=' which includes equal elements on the left side.

In Lomuto partition, elements less than the pivot are moved to the left. So the condition is arr[j] < pivot.

3fill in blank

hard

Fix the errors in the Hoare partition loop conditions to avoid infinite loops.

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] [1] pivot);
        do {
            j--;
        } while (arr[j] [2] pivot);
        if (i >= j)
            return j;
        swap(&arr[i], &arr[j]);
    }
}

Drag options to blanks, or click blank then click option'

A<=

B<

C>=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= or >= causes pointers to move incorrectly and may cause infinite loops.

Using the same condition for both i and j loops.

In Hoare partition, the left pointer moves right while arr[i] < pivot, and the right pointer moves left while arr[j] > pivot.

4fill in blank

hard

Fill both blanks to complete the Lomuto partition swap and return statement correctly.

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++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[[1]], &arr[[2]]);
    return i + 1;
}

Drag options to blanks, or click blank then click option'

Ai + 1

Bhigh

Clow

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with wrong indices like low or i instead of i+1 and high.

Returning wrong pivot index.

After the loop, swap arr[i+1] with arr[high] to place the pivot correctly.

5fill in blank

hard

Fill all three blanks to complete the Hoare partition inner loops and swap correctly.

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] [1] pivot);
        do {
            j--;
        } while (arr[j] [2] pivot);
        if (i >= j)
            return j;
        swap(&arr[[3]], &arr[j]);
    }
}

Drag options to blanks, or click blank then click option'

A<

B>

Ci

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators causing infinite loops.

Swapping wrong indices.

The left pointer moves while arr[i] < pivot, the right pointer moves while arr[j] > pivot, and swap uses arr[i] and arr[j].

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