# Exchange Sort

# Exchange Sort

Exchange sort is a basic comparison-based sorting algorithm. It compares every pair of elements and swaps them when they are in the wrong order.

It is one of the simplest sorting methods and serves as a conceptual baseline for understanding comparison sorting.

## Problem

Given a sequence $A$ of length $n$, reorder it such that

$$
A[0] \le A[1] \le \cdots \le A[n-1]
$$

## Algorithm

Compare each pair $(i, j)$ with $i < j$. If $A[i] > A[j]$, swap them.

```id="k2x9p1"
exchange_sort(A):
    n = length(A)
    for i from 0 to n - 1:
        for j from i + 1 to n - 1:
            if A[i] > A[j]:
                swap(A[i], A[j])
```

## Example

Let

$$
A = [4, 3, 2, 1]
$$

Step by step:

| comparison | action | result    |
| ---------- | ------ | --------- |
| (4,3)      | swap   | [3,4,2,1] |
| (3,2)      | swap   | [2,4,3,1] |
| (2,1)      | swap   | [1,4,3,2] |
| (4,3)      | swap   | [1,3,4,2] |
| (3,2)      | swap   | [1,2,4,3] |
| (4,3)      | swap   | [1,2,3,4] |

Final result:

$$
[1,2,3,4]
$$

## Correctness

For each index $i$, the algorithm ensures that after all comparisons with indices $j > i$, the element at position $i$ is the smallest among the remaining elements. Therefore the prefix grows in sorted order, and the entire sequence becomes sorted after all iterations.

## Complexity

| case    | comparisons        | time     |
| ------- | ------------------ | -------- |
| best    | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| worst   | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| average | $\frac{n(n-1)}{2}$ | $O(n^2)$ |

Space complexity:

$$
O(1)
$$

## Properties

* in-place
* not stable
* simple structure
* many redundant swaps

## When to Use

Exchange sort is mainly used for teaching purposes. It is easy to understand but inefficient compared to other quadratic algorithms such as insertion sort or selection sort.

## Implementation

```id="m3x8q2"
def exchange_sort(a):
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] > a[j]:
                a[i], a[j] = a[j], a[i]
    return a
```

```id="z7k2v1"
func ExchangeSort[T constraints.Ordered](a []T) {
    n := len(a)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if a[i] > a[j] {
                a[i], a[j] = a[j], a[i]
            }
        }
    }
}
```