Quick Sort Partition Lomuto and Hoare in DSA Go - Build from Scratch

Quick Sort Partition: Lomuto and Hoare

📖 Scenario: You are working on sorting a list of numbers efficiently. Quick Sort is a popular method that uses a step called partitioning to organize numbers around a pivot.There are two common ways to partition: Lomuto and Hoare. Each arranges the numbers differently but helps Quick Sort work faster.

🎯 Goal: Build two partition functions in Go: one using Lomuto's method and one using Hoare's method. Then, apply them to a sample list to see how the list changes after partitioning.

📋 What You'll Learn

Create a slice of integers named arr with the exact values: 8, 3, 7, 6, 2, 5, 4, 1

Create an integer variable pivotIndex set to 0 to use as the pivot position

Write a function lomutoPartition that partitions arr using Lomuto's method and returns the pivot's final index

Write a function hoarePartition that partitions arr using Hoare's method and returns the partition index

Print the state of arr after each partition function is called

💡 Why This Matters

🌍 Real World

Quick Sort is widely used in software to sort data quickly, such as organizing user lists, searching data, or preparing data for reports.

💼 Career

Understanding partition methods helps in optimizing sorting algorithms, which is valuable for software engineers, data scientists, and anyone working with large data sets.

1

Create the initial slice arr

Create a slice of integers called arr with these exact values in order: 8, 3, 7, 6, 2, 5, 4, 1

DSA Go

# Create the slice arr with the given values
# Your code here

Hint

Use arr := []int{...} to create the slice with the exact numbers.

2

Set the pivot index variable pivotIndex

Create an integer variable called pivotIndex and set it to 0 to represent the pivot position

DSA Go

package main

import "fmt"

func main() {
    arr := []int{8, 3, 7, 6, 2, 5, 4, 1}
    // Create pivotIndex variable
    // Your code here
}

Hint

Use pivotIndex := 0 to create the pivot index variable.

3

Write the lomutoPartition function

Write a function called lomutoPartition that takes a slice of integers arr, and two integers low and high. It should partition the slice using Lomuto's method with the pivot as arr[high] and return the final pivot index as an integer. Use a variable i starting at low - 1 and swap elements accordingly.

DSA Go

package main

import "fmt"

func lomutoPartition(arr []int, low int, high int) int {
    // Your code here
}

func main() {
    arr := []int{8, 3, 7, 6, 2, 5, 4, 1}
    pivotIndex := 0
}

Hint

Remember Lomuto uses the last element as pivot and moves smaller elements to the left.

4

Write the hoarePartition function and print results

Write a function called hoarePartition that takes a slice of integers arr, and two integers low and high. It should partition the slice using Hoare's method with the pivot as arr[low] and return the partition index as an integer. Then, in main, call lomutoPartition(arr, 0, len(arr)-1) and print arr after it. Reset arr to the original values, call hoarePartition(arr, 0, len(arr)-1), and print arr again.

DSA Go

package main

import "fmt"

func lomutoPartition(arr []int, low int, 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 hoarePartition(arr []int, low int, high int) int {
    // Your code here
}

func main() {
    arr := []int{8, 3, 7, 6, 2, 5, 4, 1}
    pivotIndex := 0
    // Call lomutoPartition and print arr
    // Reset arr
    // Call hoarePartition and print arr
    // Your code here
}

Hint

Hoare uses the first element as pivot and moves pointers inward swapping elements until they cross.

Print the slice after each partition call to see the changes.

Practice

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

easy

A. Lomuto uses a single pointer to partition, Hoare uses two pointers moving inward

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

C. Lomuto requires extra memory, Hoare works in-place

D. Lomuto always picks the last element as pivot, Hoare always picks the first

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses one 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 around the pivot.

3. Final Answer:

   Lomuto uses a single pointer to partition, Hoare uses two pointers moving inward -> Option A

4. Quick Check:

   Partition pointers = single vs two [OK]

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

Common Mistakes:

• Confusing pivot selection with partition method
• Thinking Lomuto uses two pointers
• Assuming Hoare needs extra memory

2. Which of the following is the correct Lomuto partition function header in Go?

easy

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

B. func lomutoPartition(arr []int) int

C. func lomutoPartition(arr []int, pivot int) int

D. func lomutoPartition(arr []int, start int, end int) bool

Solution

1. Step 1: Check parameters needed for Lomuto

   Lomuto partition requires the array and indices low and high to define the subarray.

2. Step 2: Check return type

   It returns an integer index of the pivot after partitioning.

3. Final Answer:

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

4. Quick Check:

   Function signature = arr, low, high, returns int [OK]

Hint: Lomuto needs array and low, high indices, returns pivot index [OK]

Common Mistakes:

• Omitting low and high parameters
• Returning bool instead of int
• Passing pivot as parameter explicitly

3. What is the output array after applying Lomuto partition on [8, 3, 7, 6, 2] with pivot as last element?

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: Identify pivot and initialize pointers

   Pivot is last element 2. Initialize i = low - 1 = -1.

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

   Check elements: 8 > 2 no swap, 3 > 2 no swap, 7 > 2 no swap, 6 > 2 no swap. i stays -1. Finally swap pivot with arr[i+1] = arr[0].

3. Final Answer:

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

4. Quick Check:

   Pivot 2 placed at start, smaller elements left [OK]

Hint: Pivot last element, swap smaller left, pivot next [OK]

Common Mistakes:

• Swapping elements incorrectly
• Not updating i pointer properly
• Confusing pivot position after partition

4. Given this Hoare partition code snippet in Go, what is the bug?

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

medium

A. The inner loops should use <= and >= instead of < and >

B. Pivot should be arr[high] instead of arr[low]

C. i and j initialization should be i = low, j = high

D. The swap should happen after checking i > j

Solution

1. Step 1: Check pointer initialization

   In Hoare partition, i starts at low and j at high, not outside the array bounds.

2. Step 2: Understand loop conditions

   Starting i at low - 1 and j at high + 1 causes index out of range errors during arr[i] and arr[j] access.

3. Final Answer:

   i and j initialization should be i = low, j = high -> Option C

4. Quick Check:

   Pointer start = low, high [OK]

Hint: Hoare pointers start at low and high, not outside [OK]

Common Mistakes:

• Initializing pointers outside array bounds
• Using wrong pivot element
• Swapping before pointer check

5. You want to sort an array with many duplicate elements efficiently. Which partition scheme is better and why?

hard

A. Lomuto, because it handles duplicates by placing them all on one side

B. Hoare, because it partitions elements more evenly and reduces swaps with duplicates

C. Lomuto, because it uses two pointers to handle duplicates quickly

D. Hoare, because it always picks the last element as pivot

Solution

1. Step 1: Consider duplicate handling in Lomuto

   Lomuto tends to put duplicates on one side, causing unbalanced partitions and more recursive calls.

2. Step 2: Consider duplicate handling in Hoare

   Hoare's two-pointer approach partitions more evenly, reducing swaps and improving performance with duplicates.

3. Final Answer:

   Hoare, because it partitions elements more evenly and reduces swaps with duplicates -> Option B

4. Quick Check:

   Duplicates handled better by Hoare [OK]

Hint: Hoare partitions evenly, better for duplicates [OK]

Common Mistakes:

• Assuming Lomuto is better for duplicates
• Confusing pivot choice with partition efficiency
• Ignoring swap count impact