このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
配列を並べ替える
- ソートとは、配列の要素を小さい順から大きい順に並べ替えることです。
- インプレイスでソートします: 配列内で要素を移動させ、戻り値はありません。
- これを行う古典的な3つの手法に、バブル、挿入、選択ソートがあります。
2つの要素の交換
- どのソートも2つの要素を交換する必要があります。一つを一時変数に保存してから上書きします。
int t = a[i]; a[i] = a[j]; a[j] = t;はiとjの位置を交換します。- 一時変数を忘れると片方の値が失われます — 常に保持してください。
バブルソート
- 配列を走査し、各ペアの隣接する要素を比較します:
a[j]とa[j + 1]。 - 順序が逆なら交換します。最も大きい値が末尾まで"泡立ち"ていきます。
- 配列全体が整列するまでパスを繰り返します。
イントロソート(挿入ソート)
- 配列の左側を既にソート済みとして扱い、一度に1つずつ拡大していきます。
- 次の要素をキーとし、大きいソート済みの要素を右へシフトさせてから、キーを隙間に置きます。
- これが多くの人が手元のカードをソートする方法です。
English
#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;
}
よくあるミス
- バブル、選択、挿入ソートはすべて O(n²) です。
- 手動で小さな配列をトレースして、ソートが正しく行われているか確認する。
あなたも試してみよう
- 昇順(小さいものから)で、インプレイスにソートし、戻り値はありません。
- チェッカーは負の数や既にソートされたものを含むいくつかの配列を試します。
mainを書かないでください;チェックツールが用意します。
探索
ソートの実行を見る
バブルソート/選択ソート/挿入ソートはすべて比較して順不同れに交換する。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
void swap(int a[], int i, int j)を完成させて、インデックスiとjの要素を交换する(原地交換、戻り値なし)。mainは書かない。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
void bubble_sort(int a[], int n)を完成させて、バブルソートを使って配列を昇順に原地ソートする。mainは書かない。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
void insertion_sort(int a[], int n)を完成させて、挿入ソートを使って配列を昇順に原地ソートする(各要素をキーとして取り出し、大きい要素を右へシフトする)。mainは書かない。
実行ボタンをクリックして出力を確認してください。