Sorting: bubble, selection, and insertion · ソート：バブルソート、選択ソート、挿入ソート
Putting an array in order
- Sorting rearranges an array so the items go from smallest to largest.
- We sort in place: we move items around inside the same array, with no return value.
- Three classic methods do this: bubble, insertion, and selection sort.
配列を並べ替える
- ソートとは、配列の要素を小さい順から大きい順に並べ替えることです。
- インプレイスでソートします: 配列内で要素を移動させ、戻り値はありません。
- これを行う古典的な3つの手法に、バブル、挿入、選択ソートがあります。
Swapping two elements
- Every sort needs to swap two items. Save one in a temporary, then overwrite.
int t = a[i]; a[i] = a[j]; a[j] = t;exchanges positionsiandj.- Forgetting the temporary loses one of the values — always keep it.
2つの要素の交換
- どのソートも2つの要素を交換する必要があります。一つを一時変数に保存してから上書きします。
int t = a[i]; a[i] = a[j]; a[j] = t;はiとjの位置を交換します。- 一時変数を忘れると片方の値が失われます — 常に保持してください。
Bubble sort
- Go through the array and compare each pair of neighbours:
a[j]anda[j + 1]. - If they are in the wrong order, swap them. The biggest value "bubbles" to the end.
- Repeat the passes until the whole array is in order.
バブルソート
- 配列を走査し、各ペアの隣接する要素を比較します:
a[j]とa[j + 1]。 - 順序が逆なら交換します。最も大きい値が末尾まで"泡立ち"ていきます。
- 配列全体が整列するまでパスを繰り返します。
Insertion sort
- Treat the left part of the array as already sorted, and grow it one item at a time.
- Take the next item as a key, shift bigger sorted items to the right, then drop the key into the gap.
- This is how many people sort playing cards in their hand.
イントロソート（挿入ソート）
- 配列の左側を既にソート済みとして扱い、一度に1つずつ拡大していきます。
- 次の要素をキーとし、大きいソート済みの要素を右へシフトさせてから、キーを隙間に置きます。
- これが多くの人が手元のカードをソートする方法です。
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
Common mistakes
- Bubble, selection and insertion sort are all O(n²).
- Trace a small array by hand to check your sort.
よくあるミス
- バブル、選択、挿入ソートはすべて O(n²) です。
- 手動で小さな配列をトレースして、ソートが正しく行われているか確認する。
Now you try
- Sort ascending (smallest first), in place, with no return value.
- The checker tries several arrays, including negatives and an already-sorted one.
- Do not write a
main— the checker provides one.
あなたも試してみよう
- 昇順（小さいものから）で、インプレイスにソートし、戻り値はありません。
- チェッカーは負の数や既にソートされたものを含むいくつかの配列を試します。
mainを書かないでください；チェックツールが用意します。
Watch a sort run · ソートの実行を見る
Bubble / selection / insertion all compare and swap into order. · バブルソート／選択ソート／挿入ソートはすべて比較して順不同れに交換する。
Complete void swap(int a[], int i, int j) so it exchanges the items at index i and j, in place (no return). Do not write a main. · void swap(int a[], int i, int j)を完成させて、インデックスiとjの要素を交换する（原地交換、戻り値なし）。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do not write a main. · void bubble_sort(int a[], int n)を完成させて、バブルソートを使って配列を昇順に原地ソートする。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Complete void insertion_sort(int a[], int n) so it sorts the array ascending, in place, using insertion sort (take each item as a key and shift bigger items right). Do not write a main. · void insertion_sort(int a[], int n)を完成させて、挿入ソートを使って配列を昇順に原地ソートする（各要素をキーとして取り出し、大きい要素を右へシフトする）。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。