Quick Sort Partition Lomuto and Hoare in DSA C++ - 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 sorting method that uses a step called partitioning to organize elements around a pivot.There are two common ways to partition: Lomuto and Hoare. Understanding how these work helps you grasp Quick Sort better.

🎯 Goal: Build two partition functions for Quick Sort: one using the Lomuto method and one using the Hoare method. Then apply them to a sample array to see how the array changes after partitioning.

📋 What You'll Learn

Create an integer array called arr with the exact values: 8, 3, 7, 6, 2, 5, 4, 1

Create two integer variables low and high with values 0 and 7 respectively

Write a function lomutoPartition that partitions arr using the Lomuto scheme

Write a function hoarePartition that partitions arr using the Hoare scheme

Print the array after applying lomutoPartition and after applying hoarePartition

💡 Why This Matters

🌍 Real World

Quick Sort is widely used in software to sort data quickly, such as organizing names, numbers, or records in databases and applications.

💼 Career

Understanding partition methods is essential for software engineers and developers working on algorithms, data processing, and performance optimization.

1

Create the array arr

Create an integer array called arr with these exact values: 8, 3, 7, 6, 2, 5, 4, 1

DSA C++

// Create the array arr with the given values
// Your code here

Hint

Use C++ array syntax: int arr[] = {values};

2

Create low and high variables

Create two integer variables called low and high with values 0 and 7 respectively

DSA C++

int arr[] = {8, 3, 7, 6, 2, 5, 4, 1};
// Create low and high variables
// Your code here

Hint

Use simple integer variable declarations.

3

Write the Lomuto partition function

Write a function called lomutoPartition that takes arr, low, and high as parameters and partitions the array using the Lomuto scheme. Use the last element as pivot. Return the partition index.

DSA C++

int arr[] = {8, 3, 7, 6, 2, 5, 4, 1};
int low = 0;
int high = 7;

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

Hint

Use the last element as pivot. Move smaller elements to the left. Swap pivot to correct position.

4

Write the Hoare partition function and print results

Write a function called hoarePartition that takes arr, low, and high as parameters and partitions the array using the Hoare scheme. Use the first element as pivot. Return the partition index. Then print the array after applying lomutoPartition and after applying hoarePartition on the original array.

DSA C++

int arr[] = {8, 3, 7, 6, 2, 5, 4, 1};
int low = 0;
int high = 7;

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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

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

int main() {
    // Your code here
}

Hint

Use the first element as pivot for Hoare. Move indices inward and swap elements. Print arrays after partitioning.