Suggest an edit

Improve this article

Refine the answer for “What are exchange sorts (exchange sorts)?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

**Exchange sorts** are a class of algorithms that order an array through repeated exchanges (swaps) of pairs of elements that are out of order. They are comparison-based, usually work in-place, and include algorithms such as bubble sort, cocktail shaker sort, odd-even sort, comb sort, gnome sort, and the partition-exchange approach used in quicksort.

## Extended answer

### Definition and idea

- The basic operation is swapping two elements when they are found to violate the order.
- The typical process is repeated passes over the array with pairwise comparisons and swaps until it is fully ordered.
- These are comparison-based sorts, often in-place (requiring O(1) extra memory, not counting the recursion stack in quicksort).

### Typical representatives

- Bubble sort: swaps adjacent elements, stable, O(n²), adaptive to nearly sorted data with an early exit (best case O(n)).
- Cocktail shaker sort: a bidirectional version of bubble sort, reduces "turtles" (large elements getting stuck near the start of the array).
- Odd-even sort: alternately compares the pairs (0,1), (2,3), ... and (1,2), (3,4), ...; parallelizes well, but is O(n²) sequentially.
- Comb sort: swaps with a shrinking "gap" between pairs, speeds up the removal of "turtle" inversions compared to bubble sort; average complexity is around O(n²), but it is faster than bubble sort in practice.
- Gnome sort: "walks" through the array and steps back on every order violation, making sequences of adjacent swaps; behaves similarly to insertion sort but is implemented through swaps.
- Simple exchange sort O(n²) (often literally called exchange sort): for each i, compares it with every j > i and swaps immediately if needed. Not stable because of non-adjacent swaps.
- Quicksort: divide-and-conquer with partition-exchange - regroups elements around a pivot through swaps. Average O(n log n), worst case O(n²), usually unstable.

### Complexity and properties

- Time: most simple exchange sorts are O(n²); improvements: bubble sort with a flag has a best case of O(n); quicksort has an average of O(n log n), worst case O(n²).
- Memory: generally in-place (O(1)), except for the recursion stack in quicksort (average O(log n)).
- Stability: bubble sort is stable; simple O(n²) exchange sort, comb sort, and quicksort are usually not (unless specifically modified).
- Adaptivity: bubble/cocktail shaker sort are adaptive to nearly sorted data; odd-even sort is convenient for parallelism; quicksort has good cache locality and excellent practical performance.

### Code examples

#### Bubble sort (JS, stable, with an early exit)

```js
function bubbleSort(arr, compare = (a, b) => a - b) {
  const a = arr; // sort in place
  let n = a.length;
  let swapped = true;
  while (swapped) {
    swapped = false;
    for (let i = 1; i < n; i++) {
      if (compare(a[i - 1], a[i]) > 0) {
        // adjacent swap - stability is preserved
        [a[i - 1], a[i]] = [a[i], a[i - 1]];
        swapped = true;
      }
    }
    // the last element is already in place
    n--;
  }
  return a;
}

// Example
const data1 = [5, 1, 4, 2, 8];
console.log(bubbleSort(data1)); // [1, 2, 4, 5, 8]
```

#### Simple exchange sort O(n²) (JS) - swap on every order violation

```js
function exchangeSort(arr, compare = (a, b) => a - b) {
  const a = arr; // sort in place
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
      if (compare(a[i], a[j]) > 0) {
        // non-adjacent swap - the algorithm is not stable
        [a[i], a[j]] = [a[j], a[i]];
      }
    }
  }
  return a;
}

// Example
const data2 = [3, 2, 1, 2];
console.log(exchangeSort(data2)); // [1, 2, 2, 3]
```

#### Quicksort (partition-exchange, JS)

```js
function quickSort(arr, compare = (a, b) => a - b, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;

const pivot = arr[right]; // Lomuto partition for clarity
  let i = left;
  for (let j = left; j < right; j++) {
    if (compare(arr[j], pivot) <= 0) {
      [arr[i], arr[j]] = [arr[j], arr[i]]; // swaps around the pivot
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];

quickSort(arr, compare, left, i - 1);
  quickSort(arr, compare, i + 1, right);
  return arr;
}

// Example
const data3 = [10, 7, 8, 9, 1, 5];
console.log(quickSort(data3)); // [1, 5, 7, 8, 9, 10]
```

### When to choose exchange sorts

- Teaching and interviews: simple to explain, useful for understanding inversions and stability.
- Very small arrays or nearly sorted data - bubble sort with an early exit can be acceptable.
- In-place and a simple implementation are required - most exchange sorts need no extra memory.
- For performance-critical code, quicksort (or a hybrid/library implementation) is usually chosen instead of the O(n²) exchange sorts.

### Comparison with other classes of sorts

- Insertion sort: moves an element to its position with shifts rather than swaps; usually better on nearly sorted data.
- Selection sort: searches for the minimum/maximum and performs rare swaps; a fixed number of swaps O(n), but still O(n²) comparisons.
- Merge sort: divides and merges using extra memory, guarantees O(n log n) and stability.
- Heap sort: uses the heap data structure, O(n log n), in-place, but usually unstable; fewer swaps than simple exchange sorts.

### Typical interview questions

1. Why is bubble sort stable, while the simple O(n²) exchange sort is not?
2. How do you modify bubble sort for an early exit, and what is the resulting best-case asymptotics?
3. Why is quicksort called a partition-exchange sort, and how does it fundamentally differ from O(n²) exchange sorts?
4. In which cases are exchange sorts appropriate in practice, and in which are they not?

Markdown · drag & drop images · ⌘B / ⌘I shortcuts950 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.