シェーカーソートで配列を並び替える

シェーカーソートを使用する

シェーカーソート (shaker sort) は、カクテルシェイカーを振るようにデータが両端へ動いていく様子から カクテルソート (cocktail sort) とも呼ばれる比較ソートである。バブルソートと同様に隣り合う要素だけを入れ替えるが、左から右への走査と右から左への走査を交互に繰り返す点が異なる。

右方向の走査: 左端から右端手前まで進み、a[i] > a[i+1] なら交換する。これでそのラウンドでは最大の要素が右端側へ寄る。
左方向の走査: 右端から左端手前まで戻り、同様に逆順なら交換する。最小の要素が左端側へ寄る。
範囲の縮小: 右方向のあと右端は確定した最大として比較範囲から外し、左方向のあと左端は確定した最小として外す。
終了条件: ある走査で一度も交換が起きなければ全体がソート済みとして終了する。

「タートル問題」と呼ばれる現象で、バブルソートでは小さな値が左端へ届くのに多くのパスを要することがあるが、シェーカーソートでは逆向きの走査があるため、極端に左にしか進めない値も早めに動かしやすくなる。

時間計算量は最悪でも O(n²) で、空間計算量は O(1)。隣接交換のみなので安定なソートである。

procedure shaker_sort(A)
  begin = 0
  end = length(A) - 1
  while begin < end
    swapped = false
    for i from begin to end - 1
      if A[i] > A[i + 1] then
        swap(A[i], A[i + 1])
        swapped = true
    end = end - 1
    if not swapped then
      break
    swapped = false
    for i from end down to begin + 1
      if A[i - 1] > A[i] then
        swap(A[i - 1], A[i])
        swapped = true
    begin = begin + 1
    if not swapped then
      break

実運用ではマージソートやクイックソートなどが選ばれることが多いが、実装が単純で挙動を視覚化しやすい教育的なアルゴリズムとして有用である。

バブルソートと同じく O(n²) だが、データによっては逆向き走査によりステップ数が抑えられる場合がある。それでも大規模データ向けの第一選択にはならないことが多い。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000038	0.000520	1662	1668
512	0.000121	0.000425	1666	1672
1024	0.000420	0.000734	1674	1680
2048	0.001524	0.001751	1690	1696
4096	0.005669	0.012543	1722	1728
8192	0.022262	0.053954	1786	1792
16384	0.107373	0.581424	1917	1924
32768	0.420701	1.401350	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 shaker_sort(a: &mut [usize]) {
    if a.len() <= 1 {
        return;
    }
    let mut left = 0;
    let mut right = a.len() - 1;
    while left < right {
        let mut swapped = false;
        for i in left..right {
            if a[i] > a[i + 1] {
                a.swap(i, i + 1);
                swapped = true;
            }
        }
        if !swapped {
            break;
        }
        right -= 1;
        swapped = false;
        for i in (left + 1..=right).rev() {
            if a[i - 1] > a[i] {
                a.swap(i - 1, i);
                swapped = true;
            }
        }
        if !swapped {
            break;
        }
        left += 1;
    }
}

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

    shaker_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