サイクルソートで配列を並び替える

サイクルソートを使用する

サイクルソート (cycle sort) は、各要素が 整列後に置かれるべき位置 を数え、その位置へ 1要素ずつ書き込むサイクル（循環） を繰り返して配列を整える比較ソートである。隣同士の交換を何度も行うバブルソートと異なり、書き込み回数を抑えたい 場面（書き込みが読み取りより高コストなメディアなど）で理論的に注目されることがある。

サイクルの開始: 未処理の左端を start とする。そこにある値を item として保持する。
目標位置の計算: start より右側で item より小さい要素の個数を数え、start に足した位置を pos（書き込み先）とする。pos == start ならその要素はすでに正しい位置にあるので次へ進む。
1回目の書き込み: A[pos] と item を入れ替える。item には追い出された値が入る。
サイクルの継続: 追い出された item について手順2〜3を繰り返し、pos が再び start に戻るまで続ける。1サイクルで start の位置は確定する。
繰り返し: start を1つ進め、配列末尾の手前まで繰り返す。

procedure cycle_sort(A)
  n = length(A)
  for start from 0 to n - 2
    item = A[start]
    pos = start
    for i from start + 1 to n - 1
      if A[i] < item then
        pos = pos + 1
    if pos = start then
      continue
    while pos < n and A[pos] = item do
      pos = pos + 1
    swap(A[pos], item)
    while pos ≠ start
      pos = start
      for i from start + 1 to n - 1
        if A[i] < item then
          pos = pos + 1
      while pos < n and A[pos] = item do
        pos = pos + 1
      swap(A[pos], item)

等しい値が複数あるときは while A[pos] = item で 同値の衝突 を避け、同じ位置へ書き込まないようにする。比較回数・書き込み回数とも最悪 O(n²) である。追加配列を使わなければ 空間計算量は O(1) のインプレースソートだが、追い出しを伴う書き込みの性質上 一般に不安定 である。

クイックソートやマージソートのように漸近的に有利な手法と比べると、比較・書き込みともに二次時間になりやすく、一般用途では採用されにくい。一方で「各要素をせいぜい1回ずつ正しい位置へ運ぶ」という発想は、書き込みコストのモデル化や教育用の題材として理解しやすい。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000014	0.000206	1662	1668
512	0.000060	0.000514	1665	1672
1024	0.000227	0.000730	1674	1680
2048	0.000898	0.001239	1690	1696
4096	0.003498	0.006040	1721	1728
8192	0.014015	0.024486	1786	1792
16384	0.055415	0.317743	1918	1924
32768	0.226216	0.496424	2178	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 cycle_sort(a: &mut [usize]) {
    let n = a.len();
    for cycle_start in 0..n.saturating_sub(1) {
        let mut item = a[cycle_start];
        let mut pos = cycle_start;
        for i in cycle_start + 1..n {
            if a[i] < item {
                pos += 1;
            }
        }
        if pos == cycle_start {
            continue;
        }
        while pos < n && a[pos] == item {
            pos += 1;
        }
        std::mem::swap(&mut a[pos], &mut item);
        while pos != cycle_start {
            pos = cycle_start;
            for i in cycle_start + 1..n {
                if a[i] < item {
                    pos += 1;
                }
            }
            while pos < n && a[pos] == item {
                pos += 1;
            }
            std::mem::swap(&mut a[pos], &mut item);
        }
    }
}

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

    cycle_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