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.

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

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

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]
            }
        }
    }
}