C言語のソートアルゴリズム。バブル・選択・挿入ソートをアニメーションで可視化。
| アルゴリズム | 計算量（平均） | 特徴 |
|---|---|---|
| バブルソート | O(n²) | 最も単純。隣同士を比較・交換 |
| 選択ソート | O(n²) | 最小値を探して先頭に置く |
| 挿入ソート | O(n²) | トランプの手札整理と同じ。ほぼ整列済みなら高速 |
| クイックソート | O(n log n) | 実用最速。C標準の qsort() はこれがベース |
void bubbleSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j+1]) { // 交換（swap） int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } } }
void selectionSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[minIdx]) minIdx = j; // 最小値の位置を記録 } // i番目と最小値を交換 int tmp = a[i]; a[i] = a[minIdx]; a[minIdx] = tmp; } }
void insertionSort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; // 挿入する値 int j = i - 1; while (j >= 0 && a[j] > key) { a[j+1] = a[j]; // 右にずらす j--; } a[j+1] = key; // 正しい位置に挿入 } }
A. 一般的にはQuickSort（クイックソート）が最速です。平均時間計算量は O(n log n) で、実装も効率的です。ただしデータの特性に応じて、MergeSort(マージソート)やHeapSort(ヒープソート)の方が速い場合もあります。プロの実装では用途に合わせて使い分けます。
A. バブルソートは教育用、挿入ソートはほぼソート済みデータに有効、クイックソートは一般的用途（標準ライブラリqsort()で採用）、マージソートはリスト構造や外部ソートに使います。学習初期はバブルソート→挿入ソート→クイックソートの順に習うのが効果的です。
A. 安定ソートは「同じ値を持つ要素の相対的な位置が変わらないソート」です。例えば学生を点数でソートする際、同じ点数なら元の順序が保たれるのが安定です。安定: バブル・挿入・マージ ソート。不安定: 選択・クイック・ヒープソート。
A. 時間計算量は「データサイズnに対する処理時間の増加傾向」を表します。O(n²)は n が10倍になると処理時間は100倍、O(n log n)なら約33倍です。O(n)が線形、O(n log n)が実用的な高速、O(n²)以上は小規模向けです。
この講座の理解度をチェックしましょう！
バブルソートは隣接要素を繰り返し比較・交換するため、最悪の場合 O(n²) の時間がかかります。
クイックソートはピボットで分割統治するため、平均 O(n log n) で高速です。ただし最悪の場合は O(n²) になります。
安定ソートでは、同じキーを持つ要素の相対的な順序がソート後も維持されます。マージソートは安定、クイックソートは不安定です。