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.