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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Lomuto Partition on Array

What is the output array after applying Lomuto partition on the given array with pivot as last element?

DSA Go

func lomutoPartition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

func main() {
    arr := []int{8, 3, 7, 6, 2, 5, 4, 1}
    lomutoPartition(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

A [1 3 7 6 2 5 4 8]

B [1 2 3 4 5 6 7 8]

C [1 3 2 4 5 6 7 8]

D [8 3 7 6 2 5 4 1]

💡 Hint

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

Lomuto partition uses last element as pivot. It moves elements smaller or equal to pivot to left and finally places pivot after them. The resulting array after partition is [1 3 7 6 2 5 4 8].

❓ Predict Output

intermediate

Output of Hoare Partition on Array

What is the output array after applying Hoare partition on the given array with pivot as first element?

DSA Go

func hoarePartition(arr []int, low, high int) int {
    pivot := arr[low]
    i := low - 1
    j := high + 1
    for {
        for {
            i++
            if arr[i] >= pivot {
                break
            }
        }
        for {
            j--
            if arr[j] <= pivot {
                break
            }
        }
        if i >= j {
            return j
        }
        arr[i], arr[j] = arr[j], arr[i]
    }
}

func main() {
    arr := []int{8, 3, 7, 6, 2, 5, 4, 1}
    hoarePartition(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

A [4 3 1 6 2 5 7 8]

B [3 2 1 4 5 6 7 8]

C [4 3 7 6 2 5 8 1]

D [1 3 7 6 2 5 4 8]

💡 Hint

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

Hoare partition picks first element as pivot (8). It swaps elements to ensure left side <= pivot and right side >= pivot. The resulting array after partition is [1 3 7 6 2 5 4 8].

🧠 Conceptual

advanced

Difference Between Lomuto and Hoare Partition

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 Lomuto partition places the pivot at its correct sorted position, Hoare partition may not.

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

💡 Hint

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

Lomuto partition places the pivot at its correct sorted position after partitioning. Hoare partition does not guarantee the pivot is at its final position.

🔧 Debug

advanced

Identify the Bug in Lomuto Partition Code

Given the Lomuto partition code below, which option correctly identifies the bug causing incorrect partitioning?

DSA Go

func lomutoPartition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }
    arr[i], arr[high] = arr[high], arr[i]
    return i
}

A The comparison should be 'arr[j] <= pivot' instead of 'arr[j] < pivot' to include equal elements.

B The initial value of 'i' should be 'low - 1' instead of 'low' to correctly track smaller elements.

C The swap of pivot with arr[i] should happen before the loop, not after.

D The loop should run until 'j <= high' instead of 'j < high' to include the pivot element.

💡 Hint

Check how 'i' is initialized and how it tracks the boundary of smaller elements.

In Lomuto partition, 'i' must start at 'low - 1' so that when the first smaller element is found, 'i' increments to 'low' and swaps correctly. Starting at 'low' skips the first element.

🚀 Application

expert

Choosing Partition Scheme for Nearly Sorted Array

You have a nearly sorted large array. Which partition scheme is generally better to reduce worst-case performance in Quick Sort?

A Use Hoare partition with median-of-three pivot selection to reduce worst-case splits.

B Use Lomuto partition with last element as pivot to maintain simplicity.

C Use Lomuto partition with random pivot selection to avoid worst-case.

D Use Hoare partition with first element as pivot for faster swaps.

💡 Hint

Consider pivot selection and partition scheme impact on nearly sorted data.

Hoare partition combined with median-of-three pivot selection helps avoid worst-case O(n^2) on nearly sorted arrays by choosing better pivots and balanced partitions.