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 method that uses a step called partitioning to organize elements around a pivot.In this project, you will implement two common partition methods: Lomuto and Hoare. These methods rearrange the list so that smaller numbers come before the pivot and larger numbers come after.

🎯 Goal: Build two partition functions in C: one using Lomuto's method and one using Hoare's method. Then, apply them to the same array and print the array after partitioning to see how the elements are arranged.

📋 What You'll Learn

Create an integer array with exact values

Define variables for array size and pivot index

Implement Lomuto partition function

Implement Hoare partition function

Print the array after each partition to show the result

💡 Why This Matters

🌍 Real World

Quick sort is widely used in software for fast sorting of data like search results, databases, and more.

💼 Career

Understanding partition schemes is important for software engineers working on performance-critical applications and algorithms.

1

Create the array and variables

Create an integer array called arr with these exact values: 9, 3, 7, 6, 2, 8, 5. Also create an integer variable n and set it to the length of arr (7).

DSA C

# Create the array 'arr' and variable 'n'
// Your code here

Hint

Use int arr[] = {9, 3, 7, 6, 2, 8, 5}; to create the array and int n = 7; for the size.

2

Add pivot index and helper function to print array

Create an integer variable pivot_index and set it to n - 1. Then, write a function called print_array that takes an integer array and its size, and prints the elements separated by spaces.

DSA C

int arr[] = {9, 3, 7, 6, 2, 8, 5};
int n = 7;
// Create pivot_index and print_array function
// Your code here

Hint

Set pivot_index = n - 1;. For print_array, use a for loop and printf to print each element followed by a space.

3

Implement Lomuto partition function

Write a function called lomuto_partition that takes an integer array, start index low, and end index high. Use Lomuto's partition scheme with the pivot as the last element. Return the final pivot position. Use variables i and j as in the Lomuto method.

DSA C

int arr[] = {9, 3, 7, 6, 2, 8, 5};
int n = 7;
int pivot_index = n - 1;

void print_array(int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

// Write lomuto_partition function here
// Your code here

Hint

Use pivot = array[high]. Initialize i = low - 1. Loop j from low to high - 1. Swap elements when array[j] <= pivot. Finally, swap pivot to position i + 1 and return i + 1.

4

Implement Hoare partition and print results

Write a function called hoare_partition that takes an integer array, start index low, and end index high. Use Hoare's partition scheme with the pivot as the first element. Return the partition index. Then, in main, call lomuto_partition and print the array, reset the array to original, call hoare_partition, and print the array again.

DSA C

int arr[] = {9, 3, 7, 6, 2, 8, 5};
int n = 7;
int pivot_index = n - 1;

void print_array(int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int lomuto_partition(int array[], int low, int high) {
    int pivot = array[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return i + 1;
}

// Write hoare_partition function and main function below
// Your code here

Hint

Use pivot = array[low] for Hoare. Use two indexes i and j moving inward. Swap elements when needed. In main, create two copies of the array, call each partition, and print results.

Practice

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

easy

A. Lomuto uses recursion, Hoare uses iteration

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

C. Lomuto uses one pointer, Hoare uses two pointers moving inward

D. Lomuto swaps only equal elements, Hoare swaps all elements

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses a single 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 that are on the wrong side.

3. Final Answer:

   Lomuto uses one pointer, Hoare uses two pointers moving inward -> Option C

4. Quick Check:

   Pointer count difference = A [OK]

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

Common Mistakes:

• Confusing sorting order difference
• Thinking both use same pointer method
• Assuming Hoare uses recursion only

2. Which of the following is the correct syntax for Lomuto partition function header in C?

easy

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

B. void lomutoPartition(int arr[], int low, int high);

C. int lomutoPartition(int arr, int low, int high);

D. int lomutoPartition(int arr[], int high, int low);

Solution

1. Step 1: Check parameter types

   Array must be passed as int arr[], and low and high as int indices.

2. Step 2: Check return type

   Lomuto partition returns an int index, so return type must be int.

3. Final Answer:

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

4. Quick Check:

   Correct signature = A [OK]

Hint: Partition returns index, so return type is int [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int arr instead of int arr[]
• Swapping low and high parameters

3. What is the output array after applying Lomuto partition on arr = [8, 3, 7, 6, 2] with low=0 and high=4?

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

   Pivot is arr[high] = 2. Initialize i = low - 1 = -1.

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

   Traverse j from 0 to 3:
   - j=0: arr[0]=8 > 2, no swap
   - j=1: arr[1]=3 > 2, no swap
   - j=2: arr[2]=7 > 2, no swap
   - j=3: arr[3]=6 > 2, no swap
   After loop, swap arr[i+1]=arr[0] and pivot arr[4]=2.

3. Final Answer:

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

4. Quick Check:

   Pivot 2 placed at start = A [OK]

Hint: Pivot is last element in Lomuto [OK]

Common Mistakes:

• Swapping elements incorrectly with pivot
• Using wrong pivot index
• Confusing i and j pointers

4. Identify the bug in this Hoare partition code snippet:

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

medium

A. Return statement should be i, not j

B. Swap function is missing

C. Pivot should be arr[high], not arr[low]

D. Pointers i and j are initialized incorrectly

Solution

1. Step 1: Examine the swap call

   The code calls swap(&arr[i], &arr[j]); but the swap function is not defined in the snippet, causing a compilation error.

2. Step 2: Verify other components

   Pointer initialization i=low-1, j=high+1 is correct for do-while structure; pivot at low ok; return j standard.

3. Final Answer:

   Swap function is missing -> Option B

4. Quick Check:

   Undefined swap function = C [OK]

Hint: Swap must be defined before calling [OK]

Common Mistakes:

• Missing swap function definition
• Confusing Hoare pointer initialization
• Returning wrong index after partition

5. Given the array [10, 80, 30, 90, 40, 50, 70], what is the final array after applying Hoare partition with low=0 and high=6?

hard

A. [10, 80, 30, 90, 40, 50, 70]

B. [10, 30, 40, 50, 70, 90, 80]

C. [10, 30, 40, 50, 80, 70, 90]

D. [10, 30, 40, 50, 70, 80, 90]

Solution

1. Step 1: Initialize pointers and pivot

   Pivot = arr[low] = 10, i = low - 1 = -1, j = high + 1 = 7.

2. Step 2: Move pointers

   do { i++; } while (arr[i] < 10); i++ to 0, arr[0]=10 not < 10, i=0.
   do { j--; } while (arr[j] > 10); j-- from 7: 6(70>10),5(50>10),4(40>10),3(90>10),2(30>10),1(80>10),0(10 not >10), j=0.
   i=0 >= j=0, return 0. No swap.

3. Final Answer:

   [10, 80, 30, 90, 40, 50, 70] -> Option A

4. Quick Check:

   Array unchanged (all ≥ pivot) = D [OK]

Hint: Hoare partition swaps inward until pointers cross [OK]

Common Mistakes:

• Assuming full sort after one partition
• Confusing pivot position after partition
• Mis-tracing pointer movements