バブルソートと挿入ソート
単純なソートです。
「バブルソートと挿入ソート」はCoddyKit上の無料C Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
単純なソート
バブルソートと挿入ソートは、最も単純な比較ソートです。どちらも最悪の場合は O(n²) ですが、理解しやすく、小規模またはほぼ整列済みの配列に適しています。
バブルソートの仕組み
バブルソートは配列を繰り返し走査し、順序が逆になっている隣接要素の組を交換します。1回の走査が終わるたびに、残っている最大の要素が末尾の確定位置まで浮かび上がります。
2つの整数の交換
再利用可能な交換ヘルパーを使うと、ソートのコードを簡潔に保てます。
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int main(void) {
int x = 1, y = 2;
swap(&x, &y);
printf("%d %d\n", x, y);
return 0;
}バブルソートの実装
二重ループを使います。外側のループが走査回数を数え、内側のループが隣接する組を比較して交換します。i回目の走査後には、末尾のi個の要素が整列済みになります。
#include <stdio.h>
void bubble_sort(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]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}早期終了の最適化
1回の走査で交換が1度も発生しなければ、配列はすでに整列済みなので停止できます。これにより、整列済みの入力に対するバブルソートの計算量は O(n) になります。
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
bubble_sort(a, 5);
printf("sorted with early exit\n");
return 0;
}挿入ソートの仕組み
挿入ソートは、配列の先頭に整列済みの領域を構築します。新しい要素ごとに、整列済みでそれより大きい要素を右へ移動し、新しい要素を空いた位置に入れます。手元のトランプを並べ替える方法に似ています。
挿入ソートの実装
要素key = a[i]を取り出し、a[0..i-1]内のそれより大きい要素を1つ右のスロットへ移動してから、空いた位置にkeyを挿入します。
#include <stdio.h>
void insertion_sort(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;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}ほぼ整列済みのデータに対する挿入ソート
挿入ソートは、配列がほぼ整列済みのときに力を発揮します。各要素の移動が数か所だけで済むため、計算量は O(n) に近づきます。そのため、ハイブリッドソートの仕上げの手順として使われます。
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
}
int main(void) {
int a[] = {1, 2, 4, 3, 5}; /* one out of place */
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}安定性
どちらのソートも安定です。等しい要素は、厳密な大小比較の場合にだけ交換または移動されるため、元の相対順序が保たれます。複数のキーでレコードを並べ替える場合、安定性が重要になります。
計算量の比較
どちらも平均の場合と最悪の場合の計算量は O(n²) ですが、実際の動作には違いがあります。
- バブルソート：交換回数が多く、実際のコードではほとんど使われません
- 挿入ソート：書き込み回数が少なく、小規模またはほぼ整列済みの配列に適しています
最適化した場合、どちらも最良計算量は O(n) です。
操作回数を数える
最悪の場合である逆順に整列された配列に対して、挿入ソートが行う比較回数を数えます。
#include <stdio.h>
int main(void) {
int a[] = {5, 4, 3, 2, 1};
int n = 5; long cmp = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
printf("comparisons = %ld\n", cmp);
return 0;
}確認問題
単純なソートについての理解を確認しましょう。
まとめ
2つの単純な O(n²) ソートを学びました。
- バブルソートは、各走査で隣接する要素の組を交換します
- 挿入ソートは、整列済みの先頭部分に要素を移動して挿入します
- どちらも安定で、最適化すれば整列済みの入力に対して O(n) になります
- 小規模なデータでは、実用上は挿入ソートのほうが適しています
よくある質問
「バブルソートと挿入ソート」レッスンは無料ですか？
はい。「バブルソートと挿入ソート」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「バブルソートと挿入ソート」で何を学びますか？
単純なソートです。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「バブルソートと挿入ソート」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。