Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 225 ยท Arrays and Lists

Partitioning, Dutch Flag and In-place Tricks

Learn Lomuto and Hoare partitioning, the Dutch national flag, move zeroes, quickselect and cyclic-sort index tricks to rearrange arrays in place in Python.

Many array problems ask you to rearrange the data without using extra memory: push the zeroes to the end, put the small numbers on the left, group equal colors together. The tool for all of them is partitioning: walk through the array with one or two pointers and swap elements so that the array splits into regions that obey a rule.

Partitioning is also the heart of quicksort and its cousin quickselect, which finds the k-th smallest element without sorting everything. By the end of this lesson you will know the two classic partition schemes (Lomuto and Hoare), the three-way Dutch national flag partition, a stable way to move zeroes, and a neat trick that uses the array's own indexes as a hash table to find missing and duplicate numbers.

Everything here is in place: extra space is O(1), apart from the output. If the phrase is new, see Space Complexity. The code relies on swapping with tuple assignment, a[i], a[j] = a[j], a[i], which is covered in Python You Need for DSA.

The idea: regions and invariants

Think of the array as several regions separated by pointers. At every moment you know what each region contains (the invariant), and each step either grows a region or swaps an element across a boundary.

TEXT
Lomuto partition around pivot p (last element), scanning with j:

  [ <= p ... | > p ... | unseen ... | p ]
              ^         ^
              i         j
  "<= p" is everything before i; "> p" is from i up to j-1.

Keeping this picture in your head and checking it after each step is how you avoid off-by-one bugs. Almost every partition bug comes from forgetting what a region boundary means.

Move zeroes: the simplest partition

Problem: move all zeroes to the end, keeping the order of the other numbers. Brute force: build a new list of the non-zero values, then append zeroes. That is O(n) time but O(n) extra space. In place, keep a write pointer write for the next position where a non-zero belongs, and swap each non-zero element into it.

Python Move zeroes (stable, in place)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Regions: everything before write is non-zero (in original order), from write to read - 1 is zero, and the rest is unseen. Each element is touched once: O(n) time, O(1) space. The order of non-zeroes is preserved, which makes this a stable partition.

When write == read, the swap does nothing. You can skip it with an if write != read: check, but the unconditional swap is shorter and just as correct.

Lomuto partition

Lomuto's scheme partitions around a pivot p, here the last element. Scan j from left to right. Whenever a[j] <= p, swap it into the "small" region (at i) and grow that region. At the end, swap the pivot into position i: everything to its left is <= p, everything to its right is > p, and the pivot is in its final sorted position.

Python Lomuto partition with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Lomuto is short and easy to remember. Its weakness: with many equal elements, or an already sorted array and a last-element pivot, the split is badly unbalanced, which makes quicksort O(nยฒ). It also does more swaps than Hoare's scheme.

Hoare partition

Hoare's original scheme uses two pointers moving toward each other. The left pointer skips values that are already small enough, the right pointer skips values that are already large enough, and when both are stuck, swap them. It typically does fewer swaps than Lomuto and copes better with equal values, but the boundary conditions are subtler: the returned index is not the pivot's final position, it is just a split point.

Python Hoare partition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After Hoare partition, every value in a[lo..split] is <= every value in a[split+1..hi], so you recurse on lo..split and split+1..hi. Unlike Lomuto, do not exclude the split index itself, or you can lose elements.

Scheme Pointers Swaps Pivot ends at final spot?
Lomuto one scanner, one boundary more yes
Hoare two, moving inward fewer no

Sort colors: the Dutch national flag

A classic: an array contains only 0, 1 and 2 (red, white, blue). Sort it in one pass with O(1) space. A counting pass followed by a rewrite takes two passes; Dijkstra's Dutch national flag algorithm takes one, using three regions and three pointers:

TEXT
  [ 0 0 0 | 1 1 1 | ? ? ? ? | 2 2 2 ]
            ^        ^        ^
           low      mid      high
  a[0:low] = 0s, a[low:mid] = 1s, a[mid:high+1] = unknown, a[high+1:] = 2s

Look at a[mid]:

  • 0: swap it with a[low], then move both low and mid forward (the value swapped into mid was a 1, already classified).
  • 1: it is already in the right region, so only advance mid.
  • 2: swap it with a[high] and shrink high. Do not advance mid: the value that arrived from high has not been inspected yet.
Python Dutch national flag (sort colors)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same three-way partition fixes quicksort's weakness with duplicates: group < pivot, == pivot, > pivot and only recurse on the outer two. It also solves "partition around a value x" questions. Time O(n), space O(1), each element handled at most about twice.

Quickselect: the k-th smallest without sorting

To find the k-th smallest element (0-based), partition around a pivot. The pivot lands at index p. If p == k you are done. If k < p, the answer is in the left part; otherwise in the right part. Unlike quicksort you recurse into one side only, so the expected work is n + n/2 + n/4 + ..., which is O(n). The worst case (always unlucky pivots) is O(nยฒ), which is why implementations choose a random pivot.

Python Quickselect with Lomuto

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the options: sorting is O(n log n); a heap of size k is O(n log k) (see Heaps); quickselect is expected O(n). "Median of medians" gives a guaranteed O(n) but is rarely worth the code.

Cyclic-sort tricks: using indexes as the hash table

Suppose an array of length n holds numbers from 1 to n, some missing and some duplicated. The value v has a natural home: index v - 1. Cyclic sort puts each value in its home by swapping, using the array itself as the lookup table. Afterwards, every index i where a[i] != i + 1 reveals a problem: i + 1 is missing and a[i] is a duplicate.

TEXT
value 3 belongs at index 2, value 7 at index 6, and so on
Swap until each value sits at index value-1, or its home already holds that value
(that means it is a duplicate, so leave it).
Python Find the missing and duplicate numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why is this O(n) even though there is a while with swaps inside? Every swap puts one value into its final position permanently, so there are at most n swaps in total, plus at most n increments of i. This is the same "charge each step to a fixed budget" thinking you will meet in Amortized Analysis.

A close relative is the first missing positive problem: find the smallest positive integer not in an unsorted list. Values outside 1..n cannot be the answer, so ignore them during the cyclic sort and then look for the first index where a[i] != i + 1.

Python First missing positive in O(n) time, O(1) space

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When you swap a[i], a[a[i] - 1] = a[a[i] - 1], a[i] in one line, Python evaluates the right side first, but it assigns left to right. a[i] changes before the second target a[a[i] - 1] is computed, so the swap goes wrong. Compute home = a[i] - 1 first, as the code above does.

Common mistakes

  • Losing the invariant. Before you code a partition, write down in words what each region contains. Re-check it after every branch.
  • Advancing mid after swapping with high in the Dutch flag algorithm. The swapped-in value is still unclassified.
  • Excluding the split index in Hoare (or including the pivot index in Lomuto's recursion). The two schemes have different conventions.
  • Fixed pivots on sorted data. A first- or last-element pivot gives O(nยฒ) on sorted input. Use a random or middle pivot.
  • Mutating the caller's list unexpectedly. Say so in the docstring, or copy first.
  • Using in-place tricks when the input must stay unchanged. In-place saves memory but destroys the original order.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. After a Lomuto partition, which statement is true?

    Lomuto swaps the pivot between the two regions, so it ends at its final position. The two sides themselves are not sorted.
  2. 2. In the Dutch national flag algorithm, why is mid not advanced after swapping a[mid] with a[high]?

    Values at or before mid are classified, but a[high] came from the unknown region, so it must be looked at on the next step.
  3. 3. What is the expected time complexity of quickselect?

    Each round partitions the current range in O(size) and keeps only one side, so the sizes shrink like n + n/2 + n/4 + ... = O(n) in expectation.
  4. 4. Why is the cyclic-sort loop O(n) even though it has swaps inside a while loop?

    A value that has reached its home is never moved again, so swaps are limited by n and the pointer moves at most n times.
  5. 5. Which problem is solved by a stable in-place partition with one write pointer?

    The write pointer marks the next slot for a non-zero value, and non-zero values keep their relative order.

Summary

  • Partitioning rearranges an array in place into regions defined by an invariant; most bugs come from forgetting what a boundary means.
  • Move zeroes uses a read pointer and a write pointer: O(n) time, O(1) space, and it is stable.
  • Lomuto is simple and puts the pivot in its final place; Hoare does fewer swaps but returns only a split point.
  • The Dutch national flag handles three groups in one pass; use it for sort colors and three-way quicksort.
  • Quickselect finds the k-th smallest element in expected O(n) by recursing into one side only; a random pivot protects against bad inputs.
  • Cyclic sort treats the array as a hash table of value to index, solving missing, duplicate and first-missing-positive problems in O(n) time and O(1) space.

Next: Matrices and 2D Arrays, where the array gets a second dimension.