Compare and Swap (Sorting)

Compare and swap is the simplest way to put things in order: look at two elements, and if they are in the wrong order, swap them. Repeat until nothing is out of place. Interviewers like it because it tests whether you can reason about loop invariants (what is already correct after each pass) and handle index boundaries without off-by-one slips.

When to use it

  • The question asks you to sort an array in place, or to put elements into a required order without extra memory.
  • You are told to rearrange values so that groups end up together (for example 0s, 1s and 2s, or negatives before positives).
  • The array has only a few distinct values, or each value tells you exactly where it belongs (such as 1..n in an array of size n).
  • You need to understand or implement a basic sort such as bubble, selection or insertion sort.
  • The problem says 'swap' or 'in place' and asks for O(1) extra space.

See it work

  1. Start with the array [5, 1, 4, 2]. We will use bubble sort: compare each pair of neighbours and swap them if the left one is bigger. Pointer i marks the left element of the pair being compared. [5, 1, 4, 2]
  2. 5 > 1, so they are out of order. Swap them. The array is now [1, 5, 4, 2]. Move i one step right. [1, 5, 4, 2]
  3. Compare 5 and 4 at positions 1 and 2. 5 > 4, so swap. Now compare 5 and 2 at positions 2 and 3. 5 > 2, so swap again. The biggest value, 5, has 'bubbled' to the end and is now in its final place. [1, 4, 2, 5]
  4. Pass 2 only needs to cover the first three cells. Compare 1 and 4: already in order, no swap. Compare 4 and 2: 4 > 2, so swap. The array becomes [1, 2, 4, 5] and 4 is locked in. [1, 2, 4, 5]
  5. Pass 3 compares 1 and 2 and finds no swap. A full pass with zero swaps means the array is sorted, so we can stop early. Final answer: [1, 2, 4, 5]. [1, 2, 4, 5]

Code template

Python

def compare_and_swap_sort(a):
    n = len(a)
    for end in range(n - 1, 0, -1):      # a[end+1:] is already final
        swapped = False
        for i in range(end):             # compare neighbours up to 'end'
            if a[i] > a[i + 1]:          # out of order?
                a[i], a[i + 1] = a[i + 1], a[i]   # swap them
                swapped = True
        if not swapped:                  # no swaps means sorted, stop early
            break
    return a

C

void compare_and_swap_sort(int a[], int n) {
    for (int end = n - 1; end > 0; end--) {   /* a[end+1..] is already final */
        int swapped = 0;
        for (int i = 0; i < end; i++) {       /* compare neighbours up to end */
            if (a[i] > a[i + 1]) {            /* out of order? */
                int tmp = a[i];               /* swap them */
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;                  /* no swaps means sorted, stop early */
    }
}

Java

static void compareAndSwapSort(int[] a) {
    int n = a.length;
    for (int end = n - 1; end > 0; end--) {   // a[end+1..] is already final
        boolean swapped = false;
        for (int i = 0; i < end; i++) {       // compare neighbours up to 'end'
            if (a[i] > a[i + 1]) {            // out of order?
                int tmp = a[i];               // swap them
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break;                  // no swaps means sorted, stop early
    }
}

Complexity: Bubble and selection sort take O(n^2) time and O(1) extra space; bubble sort is O(n) on already sorted input thanks to the early exit. Single-pass swap problems (like partitioning 0s, 1s and 2s) run in O(n) time and O(1) space.

Programs that use it

Interview problems that use it

  • Sort Colors (Dutch National Flag): Keep pointers for the boundaries of the 0s and 2s, and swap each new element into the correct zone as you scan.
  • Move Zeroes to the End: Swap each non-zero value with the first zero slot, so non-zeros pack to the front while keeping their order.
  • Cyclic Sort for Numbers 1 to n: Compare each value with its target index and swap it there until the current spot holds the right number.
  • Find the Missing Number: Swap every value into its matching index, then the first index holding the wrong value reveals the missing number.
  • Selection Sort Implementation: Find the smallest remaining element and swap it into the next front position, growing a sorted prefix.
  • Partition Array Around a Pivot: Scan once and swap elements smaller than the pivot into the left region, which is the core step of quicksort.

Common mistakes

  • Going past the end of the array when comparing a[i] with a[i + 1]; the inner loop must stop one position early.
  • Swapping without a temporary variable (or tuple swap), which overwrites one value and loses data.
  • Advancing the pointer after a swap in cyclic-sort style problems, when you should re-check the same index because the new value there may also be misplaced.

Frequently asked questions

Is compare and swap the same as bubble sort?

Bubble sort is one example of it. The wider pattern is any approach that compares two elements and swaps them when they are out of order, including selection sort, insertion sort, cyclic sort and partition steps.

When should I use compare and swap instead of a built-in sort?

Use it when the problem demands in-place, O(1) space rearrangement, or when the values have special structure (few distinct values, or values that match indexes) that lets you finish in O(n). Otherwise a built-in O(n log n) sort is usually fine.

Why is bubble sort O(n^2)?

Each pass fixes only one element at the end, and there are about n passes that each compare up to n pairs, so the work adds up to roughly n times n comparisons.

← All interview patterns

Try AI Flowchart free →