ノームソートで配列を並び替える

ノームソートを使用する

ノームソート (gnome sort / stupid sort) は、直感に沿った単純なルールだけで昇順へ整列させる比較ソートである。「庭のノームが並んだ植木鉢を、隣との大小関係を見ながら前後へ動きながら整える」様子になぞらえ、この名前が付いている説明がよくされている。

処理の状態は現在位置 pos（しばしば「ノームの足元」などと呼ぶ）だけでよいことから、状態機械として読みやすく、コードも短く書けるという利点がある。一方で、一般に最悪時間計算量は O(n²) であり、規模が大きいデータ向けではなく、概念的な説明や遊び的な題材として用いられることが多い。

pos = 0 から始める。配列の左端から眺めていく。
pos == 0 または A[pos] >= A[pos - 1] のとき：いま見ている並びがローカルに問題ないので 1ステップ進み、pos += 1 とする。
それ以外：隣との順序が逆なので 隣どうしを交換し、pos -= 1 してひとつ戻って再チェックする（より左側とも整合させる）。
pos == n になるまで繰り返す。

procedure gnome_sort(A)
  pos = 0
  while pos < length(A)
    if pos = 0 or A[pos] >= A[pos - 1] then
      pos = pos + 1
    else
      swap(A[pos], A[pos - 1])
      pos = pos - 1

交換が > だけでトリガされる実装では、等しい値の相対順序は変わらないため安定なソートとして扱える。追加の配列を使わなければ空間計算量は O(1) である。すでにソート済みの列では比較しながら右へ進むだけなので O(n)、逆順に近い並びでは前後への往復が多く O(n²) になる。

バブルソートのように端へ値を運ぶより「小さい不整合が出るたびにすぐその場で直しにいく」挙動が特徴で、単純ながら規模が増えると時間が読みにくくなる側面もある。状態の種類が少なく、コードと動きの対応を追いやすいソートアルゴリズムといえる。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000032	0.000535	1662	1668
512	0.000125	0.000815	1666	1672
1024	0.000504	0.003710	1674	1680
2048	0.001823	0.009579	1690	1696
4096	0.005960	0.027257	1722	1728
8192	0.018772	0.040192	1786	1792
16384	0.062021	0.131856	1918	1924
32768	0.246273	0.455311	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 gnome_sort(a: &mut [usize]) {
    let mut i = 1;
    while i < a.len() {
        if i == 0 || a[i - 1] <= a[i] {
            i += 1;
        } else {
            a.swap(i - 1, i);
            i -= 1;
        }
    }
}

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

    gnome_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