AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Hardsortingquicksortpartition

~180s

One partition step

The array [7, 2, 1, 6, 8, 5, 3, 4] is partitioned by the Lomuto scheme with the last element as pivot: a boundary index i starts at −1, every element less than or equal to the pivot advances the boundary and is swapped into it, and the pivot is finally swapped into position i + 1. What is the array after this single partition?

Show the answer and the worked solution

Correct answer: D.

2, 1, 3, 4, 8, 5, 7, 6

Worked solution

  1. The pivot is 4 and the boundary starts at i = −1.
  2. 7 is larger and is skipped. 2 is smaller, so i becomes 0 and 2 swaps into index 0: [2, 7, 1, 6, 8, 5, 3, 4].
  3. 1 is smaller, so i becomes 1 and 1 swaps into index 1: [2, 1, 7, 6, 8, 5, 3, 4].
  4. 6, 8 and 5 are all larger and are skipped.
  5. 3 is smaller, so i becomes 2 and 3 swaps with index 2: [2, 1, 3, 6, 8, 5, 7, 4].
  6. Finally the pivot swaps with index i + 1 = 3: [2, 1, 3, 4, 8, 5, 7, 6].

Answer: 2, 1, 3, 4, 8, 5, 7, 6.

The idea

After one partition the pivot alone is in its final position, everything to its left is no larger and everything to its right is no smaller. Neither side is sorted, which is what rules out the tidy-looking options.

Shortcut. Lomuto keeps the small keys in the order it meets them, 2, 1, 3, which rules out two options; the final pivot swap sends the large key at index 3, 6, to the last slot, which rules out the option ending in 7.

Common trap. "1, 2, 3, 4, 8, 5, 7, 6" sorts the left part, as though partitioning ordered it; 2 is met before 1 and stays in front.

Data Structures & Algorithms

24 of 40

Level

Hard

Target time

~180s

PreviousNext
AI InterviewGet started

One partition step — Aptitude Question

One partition step: The array [7, 2, 1, 6, 8, 5, 3, 4] is partitioned by the Lomuto scheme with the last element as… Answer and worked solution on CodeKairo.

Question

The array [7, 2, 1, 6, 8, 5, 3, 4] is partitioned by the Lomuto scheme with the last element as pivot: a boundary index i starts at −1, every element less than or equal to the pivot advances the boundary and is swapped into it, and the pivot is finally swapped into position i + 1. What is the array after this single partition?

Options

  1. 1, 2, 3, 4, 8, 5, 7, 6
  2. 2, 1, 3, 4, 5, 6, 8, 7
  3. 2, 3, 1, 4, 8, 5, 7, 6
  4. 2, 1, 3, 4, 8, 5, 7, 6
Show the answer and the worked solution

Correct answer: D. 2, 1, 3, 4, 8, 5, 7, 6

Worked solution

  1. The pivot is 4 and the boundary starts at i = −1.
  2. 7 is larger and is skipped. 2 is smaller, so i becomes 0 and 2 swaps into index 0: [2, 7, 1, 6, 8, 5, 3, 4].
  3. 1 is smaller, so i becomes 1 and 1 swaps into index 1: [2, 1, 7, 6, 8, 5, 3, 4].
  4. 6, 8 and 5 are all larger and are skipped.
  5. 3 is smaller, so i becomes 2 and 3 swaps with index 2: [2, 1, 3, 6, 8, 5, 7, 4].
  6. Finally the pivot swaps with index i + 1 = 3: [2, 1, 3, 4, 8, 5, 7, 6].

Answer: 2, 1, 3, 4, 8, 5, 7, 6.

The idea

After one partition the pivot alone is in its final position, everything to its left is no larger and everything to its right is no smaller. Neither side is sorted, which is what rules out the tidy-looking options.

Shortcut. Lomuto keeps the small keys in the order it meets them, 2, 1, 3, which rules out two options; the final pivot swap sends the large key at index 3, 6, to the last slot, which rules out the option ending in 7.

Common trap. "1, 2, 3, 4, 8, 5, 7, 6" sorts the left part, as though partitioning ordered it; 2 is met before 1 and stays in front.

All Data Structures & Algorithms questions · placement mock tests