交換ソートを使用する

交換ソート (exchange sort) は、未確定の左端 i を基準に、右側の各要素 A[j] と比較し、より小さい値が見つかるたびにその場で入れ替える比較ソートである。二重ループの比較パターンは選択ソートと同じだが、最小値の位置を記録してから一度だけ交換するのではなく、見つけ次第交換する点が異なる。

  1. 外側のインデックス: 確定済みでない左端を i とする（初期は i = 0）。
  2. 右側との比較: j を i+1 から末尾まで進め、A[j] < A[i] なら A[i] と A[j] を入れ替える。
  3. 位置の確定: 内側ループが終わると、位置 i には未整列部分の最小値が残る。
  4. 繰り返し: i を1つ進め、i = n-2 まで繰り返す。
procedure exchange_sort(A)
  n = length(A)
  for i from 0 to n - 2
    for j from i + 1 to n - 1
      if A[j] < A[i] then
        swap(A[i], A[j])

最悪・平均・最良いずれも比較回数は O(n²) で、入力の並びで大きくは変わらない。選択ソートと違い、小さい値を見つけるたびに交換するため交換回数は最悪 O(n²) になりうる。追加配列を使わなければ空間計算量は O(1) のインプレースソート。等しい値同士の順序を入れ替える実装になりやすく、不安定なソートである。

選択ソートと整列結果は同じだが交換回数が多くなりやすい。バブルソートのように隣接ペアだけを扱う単純交換法とも、比較するペアの取り方が異なる。

計算時間量および空間計算量を計測する

Size Average time Maximum time Average memory Maximum memory
256 0.000031 0.000587 1662 1668
512 0.000095 0.000539 1666 1672
1024 0.000327 0.000560 1674 1680
2048 0.001256 0.001950 1689 1696
4096 0.005151 0.017483 1722 1728
8192 0.021620 0.108146 1785 1792
16384 0.090977 0.299141 1918 1924
32768 0.604069 1.464319 2177 2184
計測に使用したコードを表示する 

set -euo pipefail

WORKDIR="$(mktemp -d)"
trap 'rm -rf "$WORKDIR"' EXIT

cat > "$WORKDIR/Dockerfile" <<'EOF'
FROM rust:1.95.0

WORKDIR /app

RUN mkdir -p src

RUN cat > Cargo.toml <<'CARGO'
[package]
name = "rust-benchmark"
version = "0.1.0"
edition = "2021"

[profile.release]
lto = true
codegen-units = 1
panic = "abort"
CARGO

RUN cat > src/main.rs <<'RUST'
use std::{
    env,
    process::Command,
    time::{Duration, Instant},
};
const MIN_POWER: u32 = 8;
const MAX_POWER: u32 = 15;
const RUNS: usize = 8192;


fn exchange_sort(a: &mut [usize]) {
    for i in 0..a.len() {
        for j in i + 1..a.len() {
            if a[j] < a[i] {
                a.swap(i, j);
            }
        }
    }
}


fn benchmark_sort(array: &mut [usize]) {

    exchange_sort(array);

}

fn shuffled(size: usize, seed: u64) -> Vec<usize> {
    let mut v: Vec<usize> = (1..=size).collect();

    let mut state = seed;

    for i in (1..size).rev() {
        state ^= state << 13;
        state ^= state >> 7;
        state ^= state << 17;

        let j = (state as usize) % (i + 1);

        v.swap(i, j);
    }

    v
}

fn memory_usage_kb() -> usize {
    let contents = std::fs::read_to_string("/proc/self/status")
        .unwrap_or_default();

    for line in contents.lines() {
        if let Some(rest) = line.strip_prefix("VmHWM:") {
            let kb = rest
                .split_whitespace()
                .next()
                .unwrap_or("0")
                .parse::<usize>()
                .unwrap_or(0);

            return kb;
        }
    }

    0
}

fn micros(d: Duration) -> u128 {
    d.as_micros()
}

fn run_once(size: usize, seed: usize) -> (u128, usize) {
    let expected: Vec<usize> = (1..=size).collect();
    let mut array = shuffled(size, seed as u64);

    let start = Instant::now();

    benchmark_sort(&mut array);

    let elapsed = start.elapsed();

    if array != expected {
        panic!(
            "sort failed with seed {} for size {}",
            seed,
            size
        );
    }

    (micros(elapsed), memory_usage_kb())
}

fn run_child(args: &[String]) {
    let size = args[2].parse::<usize>().expect("invalid size");
    let seed = args[3].parse::<usize>().expect("invalid seed");
    let (elapsed_us, mem) = run_once(size, seed);
    println!("{} {}", elapsed_us, mem);
}

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.get(1).is_some_and(|arg| arg == "--run-once") {
        run_child(&args);
        return;
    }

    println!(
        "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
        "Size",
        "Average time",
        "Maximum time",
        "Average memory",
        "Maximum memory"
    );

    println!(
        "|{:-<11}:|{:-<16}:|{:-<16}:|{:-<16}:|{:-<16}:|",
        "",
        "",
        "",
        "",
        ""
    );

    for power in MIN_POWER..=MAX_POWER {
        let size = 1usize << power;

        let mut total_time: u128 = 0;
        let mut max_time: u128 = 0;

        let mut total_mem: usize = 0;
        let mut max_mem: usize = 0;

        for seed in 1..=RUNS {
            let output = Command::new(env::current_exe().expect("failed to find current executable"))
                .arg("--run-once")
                .arg(size.to_string())
                .arg(seed.to_string())
                .output()
                .expect("failed to run benchmark child process");

            if !output.status.success() {
                panic!(
                    "benchmark child process failed: {}",
                    String::from_utf8_lossy(&output.stderr)
                );
            }

            let stdout = String::from_utf8(output.stdout)
                .expect("child process returned non-UTF-8 output");
            let mut fields = stdout.split_whitespace();
            let elapsed_us = fields
                .next()
                .expect("missing elapsed time")
                .parse::<u128>()
                .expect("invalid elapsed time");
            let mem = fields
                .next()
                .expect("missing memory usage")
                .parse::<usize>()
                .expect("invalid memory usage");

            total_time += elapsed_us;

            if elapsed_us > max_time {
                max_time = elapsed_us;
            }

            total_mem += mem;

            if mem > max_mem {
                max_mem = mem;
            }
        }

        let avg_time = total_time / RUNS as u128;
        let avg_mem = total_mem / RUNS;

        println!(
            "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
            size,
            format!("{}.{:06}", avg_time / 1_000_000, avg_time % 1_000_000),
            format!("{}.{:06}", max_time / 1_000_000, max_time % 1_000_000),
            avg_mem,
            max_mem
        );
    }
}
RUST

RUN cargo build --release

CMD ["./target/release/rust-benchmark"]
EOF

docker build -t rust-benchmark "$WORKDIR"
docker run --rm --init rust-benchmark