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

Quick Sort Partition: Lomuto and Hoare

📖 Scenario: You are working on sorting a list of numbers to organize your data efficiently. Quick Sort is a fast sorting method that uses a step called partitioning to arrange elements around a pivot.There are two popular ways to partition: Lomuto and Hoare. Understanding both helps you see how Quick Sort works under the hood.

🎯 Goal: You will create two functions in JavaScript: one for Lomuto partition and one for Hoare partition. Then, you will apply these to a sample array and print the partitioned array and pivot index after each method.

📋 What You'll Learn

Create an array called arr with the exact numbers [8, 3, 1, 7, 0, 10, 2]

Create a variable high set to the last index of the array

Write a function lomutoPartition that partitions the array using Lomuto's method

Write a function hoarePartition that partitions the array using Hoare's method

Print the array and pivot index after applying each partition method

💡 Why This Matters

🌍 Real World

Sorting is used everywhere: organizing data, searching faster, and improving software speed.

💼 Career

Understanding Quick Sort and its partition methods is essential for software engineers and data scientists to optimize algorithms.

1

Create the initial array

Create an array called arr with these exact numbers: [8, 3, 1, 7, 0, 10, 2]

DSA Javascript

# Your code here

Hint

Use const arr = [8, 3, 1, 7, 0, 10, 2]; to create the array.

2

Set the high index variable

Create a variable called high and set it to the last index of arr using arr.length - 1

DSA Javascript

const arr = [8, 3, 1, 7, 0, 10, 2];
# Your code here

Hint

Use const high = arr.length - 1; to get the last index.

3

Write the Lomuto partition function

Write a function called lomutoPartition that takes array, low, and high as parameters and partitions the array using Lomuto's method. Use the last element as pivot. Return the pivot index after partitioning.

DSA Javascript

const arr = [8, 3, 1, 7, 0, 10, 2];
const high = arr.length - 1;

# Your code here

Hint

Use the last element as pivot. Move smaller elements left, then place pivot after them.

4

Write the Hoare partition function and print results

Write a function called hoarePartition that takes array, low, and high as parameters and partitions the array using Hoare's method. Use the first element as pivot. Return the partition index. Then, call both lomutoPartition and hoarePartition on copies of arr with low = 0 and high as defined. Print the array and pivot index after each partition in this exact format:
console.log('Lomuto partition index:', lomutoIndex);
console.log('Array after Lomuto partition:', lomutoArr);
console.log('Hoare partition index:', hoareIndex);
console.log('Array after Hoare partition:', hoareArr);

DSA Javascript

const arr = [8, 3, 1, 7, 0, 10, 2];
const high = arr.length - 1;

function lomutoPartition(array, low, high) {
    const pivot = array[high];
    let i = low - 1;
    for (let j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            [array[i], array[j]] = [array[j], array[i]];
        }
    }
    [array[i + 1], array[high]] = [array[high], array[i + 1]];
    return i + 1;
}

# Your code here

Hint

Use the first element as pivot for Hoare. Move pointers inward and swap elements until pointers cross.

Print results exactly as shown.

Practice

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

easy

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

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

C. Lomuto is used only for arrays of even length, Hoare for odd length

D. Lomuto swaps elements only once, Hoare swaps multiple times

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses a single pointer to track the boundary of smaller elements and swaps with the pivot at the end.

2. Step 2: Understand Hoare partition

   Hoare partition uses two pointers starting from both ends moving inward to swap elements out of place.

3. Final Answer:

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

4. Quick Check:

   Pointer count difference = Lomuto(1), Hoare(2) [OK]

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

Common Mistakes:

• Confusing the number of pointers used
• Thinking Lomuto sorts differently by order
• Assuming partition depends on array length

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[j] in JavaScript during partition?

easy

A. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

B. arr[i], arr[j] = arr[j], arr[i];

C. swap(arr[i], arr[j]);

D. arr[i] = arr[j]; arr[j] = arr[i];

Solution

1. Step 1: Identify correct swap syntax in JavaScript

   JavaScript does not support tuple unpacking; swapping requires a temporary variable.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temp variable correctly; B is Python syntax; C is undefined function; D overwrites values incorrectly.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

4. Quick Check:

   Use temp variable for swap in JS [OK]

Hint: Use temp variable to swap in JS, no tuple unpacking [OK]

Common Mistakes:

• Using Python-style tuple swap in JavaScript
• Calling undefined swap function
• Overwriting values without temp variable

3. What is the output array after applying Lomuto partition on arr = [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 = 2 (last element). i starts at -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. Finally swap pivot with arr[i+1] = arr[0].

3. Step 3: Final array after swap

   Swap arr[0] and arr[4]: [2, 3, 7, 6, 8]

4. Final Answer:

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

5. Quick Check:

   Lomuto partition places pivot correctly [OK]

Hint: Pivot is last element; swap smaller elements left [OK]

Common Mistakes:

• Not swapping pivot at the end
• Swapping elements incorrectly
• Confusing pivot position

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

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

medium

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

B. The loop condition should be while(i < j), not while(true)

C. Swap syntax is invalid in JavaScript

D. Initialization of i and j is incorrect; should be i=low, j=high

Solution

1. Step 1: Check initialization of pointers

   Hoare partition requires i = low and j = high to start inside the array.

2. Step 2: Analyze effect of incorrect initialization

   Standard Hoare partition initializes i = low, j = high, starting the pointers at the array bounds and moving inward.

3. Final Answer:

   Initialization of i and j is incorrect; should be i=low, j=high -> Option D

4. Quick Check:

   Correct pointer start = i=low, j=high [OK]

Hint: Start pointers inside array for Hoare partition [OK]

Common Mistakes:

• Setting i and j outside array bounds
• Confusing pivot position
• Misusing swap syntax

5. You want to sort an array using Quick Sort with Hoare partition. Which of these is the correct recursive call pattern after partitioning at index p?

hard

A. quickSort(arr, low, p - 1); quickSort(arr, p, high);

B. quickSort(arr, low, p); quickSort(arr, p + 1, high);

C. quickSort(arr, low, p + 1); quickSort(arr, p, high);

D. quickSort(arr, low, p - 1); quickSort(arr, p + 1, high);

Solution

1. Step 1: Understand Hoare partition return value

   Hoare partition returns an index p such that elements arr[low..p] ≤ pivot and arr[p+1..high] ≥ pivot. The pivot is not guaranteed to be at position p.

2. Step 2: Determine correct recursive calls

   Recurse on the left subarray from low to p (inclusive) and right subarray from p+1 to high: quickSort(arr, low, p); quickSort(arr, p + 1, high).

3. Final Answer:

   quickSort(arr, low, p); quickSort(arr, p + 1, high); -> Option B

4. Quick Check:

   Hoare recursion: low to p, p+1 to high [OK]

Hint: Hoare: quickSort(low, p); quickSort(p+1, high) [OK]

Common Mistakes:

• Using p+1 in left recursive call
• Ignoring infinite recursion risk
• Confusing Lomuto and Hoare recursion