C・C++のクイックソート（quick sort）
このレッスンでは、基準となる要素（ピボット）のまわりで配列を分割して、クイックソートを実装します。
はじめに
クイックソートは1つの要素をピボット（pivot）に選び、ピボットより小さい要素が左に、それ以外が右にくるように配列を並べ直します。この時点でピボットは最終的な位置に収まっているので、アルゴリズムは左右の部分を再帰で並べ替えていきます。
大切なポイント
- 空のデータ、要素が1つのデータ、重複を含むデータ、並べ替え済みのデータで試しましょう。
- まず正しく動かし、最適化はその後にしましょう。
- 実際のコードでは、標準ライブラリの既製の関数を優先しましょう。
C・C++のクイックソート（quick sort）のビジュアライザー
O(n log n)再生またはステップを使って、比較とデータ移動を順に確認できます。
CとC++のコード例
C
main.c
#include <stdio.h>
void swap(int *left, int *right) {
int temporary = *left;
*left = *right;
*right = temporary;
}
int partition(int *values, int low, int high) {
int pivot = values[high];
int boundary = low;
for (int scan = low; scan < high; ++scan) {
if (values[scan] < pivot) {
swap(&values[boundary++], &values[scan]);
}
}
swap(&values[boundary], &values[high]);
return boundary;
}
void quick_sort(int *values, int low, int high) {
if (low >= high) return;
int pivot = partition(values, low, high);
quick_sort(values, low, pivot - 1);
quick_sort(values, pivot + 1, high);
}
int main(void) {
int values[] = {9, 4, 7, 3, 10, 5};
quick_sort(values, 0, 5);
for (int index = 0; index < 6; ++index) {
printf("%d ", values[index]);
}
}
3 4 5 7 9 10C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
if (last - first < 2) return;
auto pivot = *(last - 1);
auto middle = std::partition(first, last - 1,
[pivot](int value) { return value < pivot; });
std::iter_swap(middle, last - 1);
quick_sort(first, middle);
quick_sort(middle + 1, last);
}
int main() {
std::vector values{9, 4, 7, 3, 10, 5};
quick_sort(values.begin(), values.end());
for (int value : values) {
std::cout << value << ' ';
}
}
3 4 5 7 9 10CとC++の比較
Cの関数partitionは最後の要素をピボットにし、変数boundaryでピボットより小さい要素の領域の境目を記録します。最後にピボットをboundaryの位置に入れ替えます。C++のバージョンはstd::partitionで分割の手順を短く書いています。平均の計算量はO(n log n)ですが、ピボットの選び方が悪いとO(n²)まで遅くなることがあります。
C
ループ、ポインタ、長さ、一時的なバッファをすべて明示的に書きます。
C++
イテレーターと標準アルゴリズムが、処理とデータの保存方法を切り離します。
発展問題
両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。
- 比較を1回ずつ紙の上でたどってみましょう。
- 重複した値や、とても大きい値・小さい値で試しましょう。
- 自分で書いたコードの実行時間を測り、標準ライブラリと比べましょう。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ