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 array after applying Lomuto partition on the array [8, 3, 7, 6, 2, 5, 4] with pivot as last element?

DSA C++

int lomutoPartition(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++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

int main() {
    int arr[] = {8, 3, 7, 6, 2, 5, 4};
    int n = 7;
    int p = lomutoPartition(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

A [3, 7, 6, 2, 5, 4, 8]

B [3, 2, 4, 5, 6, 7, 8]

C [3, 2, 4, 5, 6, 8, 7]

D [2, 3, 4, 5, 6, 7, 8]

💡 Hint

Remember Lomuto partition places pivot at correct position and all smaller elements to left.

Lomuto partition uses last element as pivot. It moves all elements <= pivot to left and finally swaps pivot to position i+1. Here pivot=4, after partition array becomes [3, 2, 4, 6, 7, 5, 8] but 6,7,5 are not <=4 so they stay right. Only 3 and 2 move left.

❓ Predict Output

intermediate

Output of Hoare Partition on given array

What is the output array after applying Hoare partition on the array [9, 4, 8, 3, 1, 2, 5] with pivot as first element?

DSA C++

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

int main() {
    int arr[] = {9, 4, 8, 3, 1, 2, 5};
    int n = 7;
    int p = hoarePartition(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

A [5, 4, 8, 3, 1, 2, 9]

B [2, 4, 3, 1, 5, 8, 9]

C [1, 2, 3, 4, 5, 8, 9]

D [4, 2, 3, 1, 5, 8, 9]

💡 Hint

Hoare partition uses first element as pivot and swaps elements crossing from left and right.

Pivot is 9. Hoare partition moves i right until element >= pivot and j left until element <= pivot, then swaps. Since pivot is largest, only last swap happens putting 9 at end. Result is [5,4,8,3,1,2,9].

🧠 Conceptual

advanced

Difference between Lomuto and Hoare partition schemes

Which statement correctly describes a key difference between Lomuto and Hoare partition schemes?

A Lomuto partition always uses the first element as pivot, Hoare uses the last element.

B Hoare partition returns the final pivot index, Lomuto returns an index that may not be the pivot position.

C Hoare partition requires extra space, Lomuto partition works in-place.

D Lomuto partition places the pivot in its final sorted position, Hoare partition may not.

💡 Hint

Think about where the pivot ends after partitioning.

Lomuto partition places pivot at its correct sorted position after partitioning. Hoare partition returns an index but pivot may not be at final position.

🔧 Debug

advanced

Identify error in Lomuto partition code snippet

What error will this Lomuto partition code produce when run on array [5, 3, 8, 4, 2]? int lomutoPartition(int arr[], int low, int high) { int pivot = arr[high]; int i = low; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { std::swap(arr[i], arr[j]); i++; } } std::swap(arr[i], arr[high]); return i; }

A Off-by-one error causing incorrect pivot placement

B Runtime error due to invalid array index

C No error, code runs correctly

D Infinite loop due to wrong loop condition

💡 Hint

Check initial value of i and how it moves.

Variable i should start at low-1, not low. Starting at low causes pivot to be placed incorrectly, leading to wrong partitioning.

🚀 Application

expert

Number of swaps in Hoare partition

Given array [10, 7, 8, 9, 1, 5] and pivot as first element, how many swaps does Hoare partition perform?

DSA C++

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

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = 6;
    int swaps = hoarePartition(arr, 0, n - 1);
    std::cout << swaps;
    return 0;
}

A 2

B 3

C 4

D 5

💡 Hint

Trace i and j pointers and count swaps carefully.

Hoare partition swaps pairs crossing pivot boundary. For this array, swaps happen between (10,5), (9,1), and (8,7) totaling 3 swaps.