「クイックソート、実装できますか？」
わたし自身は資格の勉強で名前を聞いたことがあるだけで実装したことがありませんでした。
この記事では、テスト駆動開発（TDD）の手法を用いて、Rustでクイックソートをゼロから実装し、さらにパフォーマンスを計測して「弱点」を発見、そしてそれを克服するまでのプロセスを詳細に追います。
なお、今回の開発ではアシスタントとしてGoogleのGemini CLIを活用しました。その際の実際のやり取りも交えながら、リアルな開発の流れをお届けします。
Step 1: TDDの第一歩 – 最も単純なテストから始めよう
TDDの基本サイクルは「Red-Green-Refactor」。まず「失敗するテスト(Red)」を書き、そのテストを「パスさせる最小限のコード(Green)」を書き、最後に「コードを綺麗にする(Refactor)」という流れです。
> 自分: TDDでクイックソートを実装したい。最初のステップは？
>
> Gemini CLI: 最も単純なケース、空のスライスと単一要素のスライスのテストから書きましょう。この提案に従い、まずは配列が空のケースと、要素が1つだけのケースのテストを書きます。
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_empty_slice() {
let mut arr: Vec<i32> = vec![];
quicksort(&mut arr);
assert_eq!(arr, &[]);
}
#[test]
fn test_single_element_slice() {
let mut arr = vec![42];
quicksort(&mut arr);
assert_eq!(arr, &[42]);
}
}Code language: Rust (rust)このテストをパスさせる quicksort 関数は、最初は「何もしない」だけで十分です。この小さな成功体験が、開発のリズムを作ります。
fn quicksort<T: Ord>(_slice: &mut [T]) {
// この関数は意図的に空のままです。
//
// 要素が0個、または1個のスライスは、
// その時点ですでに「ソート済み」と見なせます。
// したがって、何も操作を加える必要がないため、
// この空の関数で最初のテストは成功します。
}Code language: Rust (rust)Step 2: アルゴリズムの心臓部をテストで固める
クイックソートの核となるのは、ピボット（基準値）を基準に配列を分割するパーティション処理です。この一番複雑な部分こそ、TDDの力が発揮されます。
> 自分: 次はパーティション関数のテストを書いてほしい。
>
> Gemini CLI: 承知いたしました。関数の「あるべき振る舞い」を定義するテストを生成します。このテストコードが、これから作る関数の「仕様書」となります。
#[test]
fn test_partition() {
let mut arr = vec![2, 8, 7, 1, 3, 5, 6, 4];
let pivot_val = 4; // 最後の要素をピボットとするルール
let pivot_idx = partition(&mut arr);
// 1. ピボットの最終的な位置は正しいか？
assert_eq!(arr[pivot_idx], pivot_val);
// 2. ピボットの左は、すべてピボット以下の値か？
for i in 0..pivot_idx {
assert!(arr[i] <= pivot_val);
}
// 3. ピボットの右は、すべてピボット以上の値か？
for i in pivot_idx + 1..arr.len() {
assert!(arr[i] >= pivot_val);
}
}Code language: Rust (rust)このテストをパスするように、partition 関数を実装します。
fn partition<T: Ord>(slice: &mut [T]) -> usize {<t: ord="">
let pivot_index = slice.len() - 1;
let mut i = 0;
for j in 0..pivot_index {
if slice[j] <= slice[pivot_index] {
slice.swap(i, j);
i += 1;
}
}
slice.swap(i, pivot_index);
i
}</t:>Code language: Rust (rust)Step 3: 全体完成！しかし、本当に”クイック”なのか？
心臓部ができたので、再帰呼び出しで全体を組み上げ、クイックソートを完成させます。
fn quicksort<T: Ord>(slice: &mut [T]) {
if slice.len() <= 1 {
return;
}
let pivot_index = partition(slice);
let (left, right) = slice.split_at_mut(pivot_index);
quicksort(left);
if !right.is_empty() {
quicksort(&mut right[1..]);
}
}Code language: Rust (rust)> 自分: 実装が動いたけど、本当に速いか確かめたい。弱点を見つけるための比較コードを書いてくれないか？
>
> Gemini CLI: 良いアイデアですね。バブルソートと比較し、さらに弱点を突く「ソート済みデータ」のシナリオを含む計測コードを提案します。提案されたコードを元に、main関数でパフォーマンスを計測します。
use std::time::Instant;
use rand::seq::SliceRandom;
use rand::thread_rng;
fn bubble_sort<T: Ord>(slice: &mut [T]) {
if slice.is_empty() {
return;
}
let len = slice.len();
for i in 0..len {
for j in 0..(len - 1 - i) {
if slice[j] > slice[j + 1] {
slice.swap(j, j + 1);
}
}
}
}
fn main() {
const DATA_SIZE: usize = 20_000;
// --- ケース1: ランダムなデータ ---
println!("--- Case 1: Random Data (size: {}) ---", DATA_SIZE);
let mut rng = thread_rng();
let mut vec1: Vec<i32> = (0..DATA_SIZE as i32).collect();
vec1.shuffle(&mut rng);
let mut vec2 = vec1.clone();
println!("Sorting with Quicksort...");
let now = Instant::now();
quicksort(&mut vec1);
let elapsed = now.elapsed();
println!("Quicksort took: {:.2?}", elapsed);
println!("\nSorting with Bubble Sort...");
let now = Instant::now();
bubble_sort(&mut vec2);
let elapsed = now.elapsed();
println!("Bubble sort took: {:.2?}", elapsed);
println!();
// --- ケース2: 既にソート済みのデータ (クイックソートの最悪ケース) ---
println!("--- Case 2: Sorted Data (size: {}) ---", DATA_SIZE);
let mut vec1_sorted: Vec<i32> = (0..DATA_SIZE as i32).collect();
let mut vec2_sorted = vec1_sorted.clone();
println!("Sorting with Quicksort (worst case)...");
let now = Instant::now();
quicksort(&mut vec1_sorted);
let elapsed = now.elapsed();
println!("Quicksort took: {:.2?}", elapsed);
println!("\nSorting with Bubble Sort (best case)...");
let now = Instant::now();
bubble_sort(&mut vec2_sorted);
let elapsed = now.elapsed();
println!("Bubble sort took: {:.2?}", elapsed);
}Code language: Rust (rust)結果は衝撃的なものでした。ソート済みデータに対して、クイックソートがバブルソートに大差で負けてしまったのです。
| データ種別 | クイックソート | バブルソート |
| ランダムデータ | 3.24ms | 434.20ms |
| ソート済みデータ | 127.17ms | 36.14ms |
Step 4: 弱点克服！魔法の呪文「三数中央値」
> 自分: 計測結果で弱点がわかった。どうすれば改善できる？
>
> Gemini CLI: その原因はピボット選択の偏りです。解決策として「三数中央値」を提案します。こちらが実装例です。「三数中央値」とは、配列の「最初」「真ん中」「最後」の3つの値を比較し、その中央値をピボットとして採用する手法です。quicksort関数を以下のように修正します。
fn quicksort<T: Ord>(slice: &mut [T]) {
if slice.len() <= 1 {
return;
}
// --- 三数中央値によるピボット選択 ---
let mid = (slice.len() - 1) / 2;
let high = slice.len() - 1;
// 最初・真ん中・最後の3つの値をソートする
if slice[0] > slice[mid] {
slice.swap(0, mid);
}
if slice[0] > slice[high] {
slice.swap(0, high);
}
if slice[mid] > slice[high] {
slice.swap(mid, high);
}
// 中央値を最後の要素と交換して、ピボットとして使用する
slice.swap(mid, high);
// ------------------------------------
let pivot_index = partition(slice);
let (left, right) = slice.split_at_mut(pivot_index);
quicksort(left);
if !right.is_empty() {
quicksort(&mut right[1..]);
}
}Code language: Rust (rust)この改善により、パフォーマンスは劇的に向上しました。
| データ種別 | クイックソート（改善前） | クイックソート（改善後） |
| ソート済みデータ | 127.17ms | 193.75µs |
実行時間は約650倍も高速化され、ミリ秒（ms）からマイクロ秒（µs）の領域に突入しました。
さいごに
今回の実装を通して、TDDが単なるテスト手法ではなく、複雑な問題を一歩ずつ、自信を持って解決に導くための強力な羅針盤であることを実感しました。また、計測によって初めて具体的な改善点が見え、リファクタリングによってコードが真に強くなるプロセスを体験できました。
今回は開発アシスタントとしてGemini CLIを活用しましたが、思考の整理、テストコードの生成、エラー解決のヒントなど、多くの場面で開発をスムーズに進めることができました。皆さんもこのようなツールをうまく活用して、新しい技術の学習を楽しんでみてください。
最終的なmain.rsのコードは以下です。
use rand::seq::SliceRandom;
use rand::thread_rng;
use std::time::Instant;
fn quicksort<T: Ord>(slice: &mut [T]) {
// 要素が2つ以下の場合は、単純な比較・交換が効率的
if slice.len() <= 1 {
return;
} else if slice.len() == 2 {
if slice[0] > slice[1] {
slice.swap(0, 1);
}
return;
}
// --- 三数中央値によるピボット選択 ---
let mid = (slice.len() - 1) / 2;
let high = slice.len() - 1;
// 最初・真ん中・最後の3つの値をソートする
if slice[0] > slice[mid] {
slice.swap(0, mid);
}
if slice[0] > slice[high] {
slice.swap(0, high);
}
if slice[mid] > slice[high] {
slice.swap(mid, high);
}
// これで slice[mid] が中央値になる
// 中央値を最後の要素と交換して、ピボットとして使用する
slice.swap(mid, high);
// -------------------------------------
let pivot_index = partition(slice);
let (left, right) = slice.split_at_mut(pivot_index);
quicksort(left);
// rightスライスはピボット自身を含むため、空でないことを確認してから
// ピボットを除いた部分に対して再帰呼び出しを行う
if !right.is_empty() {
quicksort(&mut right[1..]);
}
}
fn partition<T: Ord>(slice: &mut [T]) -> usize {
let pivot_index = slice.len() - 1;
let mut i = 0;
for j in 0..pivot_index {
if slice[j] <= slice[pivot_index] {
slice.swap(i, j);
i += 1;
}
}
slice.swap(i, pivot_index);
i
}
// O(n^2) のソートアルゴリズムとしてバブルソートを追加
fn bubble_sort<T: Ord>(slice: &mut [T]) {
if slice.is_empty() {
return;
}
let len = slice.len();
for i in 0..len {
for j in 0..(len - 1 - i) {
if slice[j] > slice[j + 1] {
slice.swap(j, j + 1);
}
}
}
}
fn main() {
const DATA_SIZE: usize = 20_000; // データサイズ
// --- ケース1: ランダムなデータ ---
println!("--- Case 1: Random Data (size: {}) ---", DATA_SIZE);
// gen() の代わりに shuffle() を使ってランダムなベクタを生成
let mut rng = thread_rng();
let mut vec1: Vec<i32> = (0..DATA_SIZE as i32).collect();
vec1.shuffle(&mut rng);
let mut vec2 = vec1.clone();
println!("Sorting with Quicksort...");
let now = Instant::now();
quicksort(&mut vec1);
let elapsed = now.elapsed();
println!("Quicksort took: {:.2?}", elapsed);
println!("\nSorting with Bubble Sort...");
let now = Instant::now();
bubble_sort(&mut vec2);
let elapsed = now.elapsed();
println!("Bubble sort took: {:.2?}", elapsed);
println!();
// --- ケース2: 既にソート済みのデータ (クイックソートの最悪ケース) ---
println!("--- Case 2: Sorted Data (size: {}) ---", DATA_SIZE);
let mut vec1_sorted: Vec<i32> = (0..DATA_SIZE as i32).collect();
let mut vec2_sorted = vec1_sorted.clone();
println!("Sorting with Quicksort (worst case)...");
let now = Instant::now();
quicksort(&mut vec1_sorted);
let elapsed = now.elapsed();
println!("Quicksort took: {:.2?}", elapsed);
println!("\nSorting with Bubble Sort (best case)...");
let now = Instant::now();
bubble_sort(&mut vec2_sorted);
let elapsed = now.elapsed();
println!("Bubble sort took: {:.2?}", elapsed);
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_empty_slice() {
let mut arr: Vec<i32> = vec![];
quicksort(&mut arr);
assert_eq!(arr, &[]);
}
#[test]
fn test_single_element_slice() {
let mut arr = vec![42];
quicksort(&mut arr);
assert_eq!(arr, &[42]);
}
#[test]
fn test_two_elements_slice() {
let mut arr = vec![2, 1];
quicksort(&mut arr);
assert_eq!(arr, &[1, 2]);
}
#[test]
fn test_partition() {
let mut arr = vec![2, 8, 7, 1, 3, 5, 6, 4];
let pivot_val = 4; // ピボットの値（最後の要素を想定）
let pivot_idx = partition(&mut arr);
assert_eq!(pivot_idx, 3);
assert_eq!(arr[pivot_idx], pivot_val);
for i in 0..pivot_idx {
assert!(arr[i] <= pivot_val);
}
for i in pivot_idx + 1..arr.len() {
assert!(arr[i] >= pivot_val);
}
}
#[test]
fn test_general_slice() {
let mut arr = vec![3, 5, 1, 4, 2];
quicksort(&mut arr);
assert_eq!(arr, &[1, 2, 3, 4, 5]);
}
}
Code language: Rust (rust)
コメント