C・C++のバブルソート（bubble sort）
このレッスンでは、順番が逆になっている隣り合う要素の組を何度も入れ替えて、バブルソートを実装します。
はじめに
バブルソートは配列を何度もたどり、そのたびに隣り合う要素の組を比べて、順番が逆なら入れ替えます。1回たどるごとに、まだ並んでいない中で最大の値が配列の末尾へ移っていきます。
大切なポイント
- 空のデータ、要素が1つのデータ、重複を含むデータ、並べ替え済みのデータで試しましょう。
- まず正しく動かし、最適化はその後にしましょう。
- 実際のコードでは、標準ライブラリの既製の関数を優先しましょう。
C・C++のバブルソート（bubble sort）のビジュアライザー
O(n)再生またはステップを使って、比較とデータ移動を順に確認できます。
CとC++のコード例
C
main.c
#include <stdio.h>
int main(void) {
int values[] = {5, 1, 4, 2};
for (int end = 3; end > 0; --end) {
int changed = 0;
for (int index = 0; index < end; ++index) {
if (values[index] > values[index + 1]) {
int temporary = values[index];
values[index] = values[index + 1];
values[index + 1] = temporary;
changed = 1;
}
}
if (!changed) break;
}
for (int index = 0; index < 4; ++index) {
printf("%d ", values[index]);
}
}
1 2 4 5C++
main.cpp
#include <iostream>
#include <vector>
int main() {
std::vector values{5, 1, 4, 2};
for (auto end = values.end(); end != values.begin(); --end) {
bool changed = false;
for (auto item = values.begin(); item + 1 != end; ++item) {
if (*item > *(item + 1)) {
std::iter_swap(item, item + 1);
changed = true;
}
}
if (!changed) break;
}
for (int value : values) {
std::cout << value << ' ';
}
}
1 2 4 5CとC++の比較
変数changedは、その走査で入れ替えがあったかを記録します。入れ替えが1回もなければ配列はもう並んでいるので、ループを早めに終えます。そのため、最初から並んでいる配列ならO(n)で済みます。最悪の場合はO(n²)かかるので、主に学習用です。実際のC++のコードでは、ふつうstd::sortを使います。
C
ループ、ポインタ、長さ、一時的なバッファをすべて明示的に書きます。
C++
イテレーターと標準アルゴリズムが、処理とデータの保存方法を切り離します。
発展問題
両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。
- 比較を1回ずつ紙の上でたどってみましょう。
- 重複した値や、とても大きい値・小さい値で試しましょう。
- 自分で書いたコードの実行時間を測り、標準ライブラリと比べましょう。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ