第3章 コンピュータとプログラミング
整列(並べかえ・ソート)
データを小さい順・大きい順に並べかえる手順(整列・ソート)を学びます。2つの値を入れかえるしくみと、選択ソート・バブルソートで1回ごとに配列がどう変わるか、比較と入れかえの回数が分かります。
説明
1. 背の順に並ぶとき
体育の時間に背の順に並ぶとき、隣の人と背を比べて、逆なら場所を入れ替わります。これをくり返すと、最後には全員が背の順になります。
このように、データを決まった順に並べかえることを整列(せいれつ)、またはソートと呼びます。小さい順を昇順(しょうじゅん)、大きい順を降順(こうじゅん)といいます。並んでいれば、二分探索が使えたり、順位がすぐ分かったりします。

2. 2つの値の入れかえには「置き場所」が要る
並べかえの基本の動きは、2つの値の入れかえです。ジュースと牛乳の入ったコップの中身を入れかえるには、空のコップが1つ要りますね。プログラムも同じです。
いきなり Data[0] = Data[3] とすると、Data[0] の 29 が消えてしまいます。そこで先に temp(一時的に置いておく変数)に 29 を取っておきます。この3行はセットで覚えましょう。
- (01)
Data = [29, 13, 41, 8, 22] - (02)
temp = Data[0] - (03)
Data[0] = Data[3] - (04)
Data[3] = temp - (05)
表示する(Data[0], " ", Data[1], " ", Data[2], " ", Data[3], " ", Data[4])
表示:8 13 41 29 22
入れかえは「temp に 取っておく → 上書き → temp から 戻す」の3行。
3. 選択ソート:残りから最小を選んで前へ
選択ソートは、まだ並んでいない部分から一番小さい値を探し、その部分の先頭と入れかえる方法です。1回ごとに、左から1つずつ位置が決まります(青)。
最小を探すときは、「今の最小」(点線の枠)と1つずつ比べていきます。最小がもう先頭にあれば入れかえません。5個なら4回で、最後の1つは自動的に決まります。
4. バブルソート:隣同士を比べて入れかえ
バブルソートは、隣同士を左から順に比べ、左の方が大きければ入れかえる方法です。1回通すと、一番大きい値が右端まで運ばれます。泡(バブル)が浮かんでいくように見えるので、この名前があります。
2回目は、決まった右端を除いて同じことをします。1回ごとに、右から1つずつ位置が決まります。本によっては右から左へ比べて、小さい値を左端へ運ぶ形もありますが、考え方は同じです。
5. 比較と入れかえの回数
5個を選択ソートで並べるとき、比較は1回目 4回、2回目 3回、…と1つずつ減り、合計 4 + 3 + 2 + 1 = 10回です。データが n 個なら n(n−1)/2 回になります。バブルソートの比較の回数も同じです(この形のとき)。
入れかえの回数は違います。選択ソートは1回につき多くても1回なので、全部で n−1 回以下です。バブルソートは、順番が逆になっている2つの組の数だけ入れかえます。例では、選択ソートが2回、バブルソートが6回でした。
6. 選択ソートをプログラムで書く
選択ソートを、共通テストの書き方で書くと下のようになります。外側の繰り返しの i が「今決める位置」、内側の j が「最小を探す」役目です。最小の位置を saisho に入れておき、最後に temp を使って入れかえます。
「1行進む」で動かし、配列の値が変わる所(色が付く)を確かめましょう。
7. ほかの並べかえ方
並べかえの方法はほかにもあります。挿入ソートは、トランプの手札のように、1つずつ取り出して、並んでいる部分の正しい位置に差し込む方法です。クイックソートは、基準の値を1つ決め、それより小さいグループと大きいグループに分けることをくり返します(基準と同じ値があるときは、どちらのグループに入れるかを決めておきます)。
クイックソートは、データが多いとき、普通は選択ソートやバブルソートよりずっと少ない回数で終わります。ただし並び方によっては遅くなることもあります。詳しくは「アルゴリズムの比較(効率)」で見ます。
ひとことで言うと比較と入れかえをくり返し、1回ごとに1つずつ位置を決めて並べる。
例題
例題1 選択ソートの途中の並び
配列 [5, 3, 8, 1, 6] を選択ソートで小さい順に並べます。3回目が終わったとき、配列はどうなっていますか。
- 1回目:全体の最小は 1(添字3)。先頭の 5 と入れかえて [1, 3, 8, 5, 6]。
- 2回目:残り [3, 8, 5, 6] の最小は 3。もう先頭(添字1)にあるので、入れかえません。
- 3回目:残り [8, 5, 6] の最小は 5(添字3)。添字2 の 8 と入れかえて [1, 3, 5, 8, 6]。左の3つ(1, 3, 5)が決まっています。
例題2 バブルソートの比較と入れかえの回数
配列 [4, 1, 3, 2] をバブルソートで小さい順に並べます。比較の回数と、入れかえの回数を答えましょう。
- 4個なので、1回目は3回、2回目は2回、3回目は1回比べます。比較は 3 + 2 + 1 = 6回(4 × 3 ÷ 2)。
- 1回目:4 と 1 を入れかえ、4 と 3 を入れかえ、4 と 2 を入れかえ → [1, 3, 2, 4]。2回目:1 と 3 はそのまま、3 と 2 を入れかえ → [1, 2, 3, 4]。3回目:そのまま。
- 入れかえは 3 + 1 = 4回。これは、順番が逆の組(4と1、4と3、4と2、3と2)の数と同じです。
| 回目 | 比べた2つ | 結果 | 配列 |
|---|---|---|---|
| 1 | 4 と 1 | 入れかえ | [1, 4, 3, 2] |
| 1 | 4 と 3 | 入れかえ | [1, 3, 4, 2] |
| 1 | 4 と 2 | 入れかえ | [1, 3, 2, 4] |
| 2 | 1 と 3 | そのまま | [1, 3, 2, 4] |
| 2 | 3 と 2 | 入れかえ | [1, 2, 3, 4] |
| 3 | 1 と 2 | そのまま | [1, 2, 3, 4] |
練習
[7, 2, 9, 4] を選択ソートで小さい順に並べます。1回目が終わったときの配列はどれですか。[6, 3, 5, 1] をバブルソート(隣同士を左から比べ、左が大きければ入れかえる)で並べます。1回目が終わったときの配列はどれですか。さわってみよう
選択ソートとバブルソートを並べて動かす
同じ並びを、2つの方法で同時に1手ずつ並べかえます。棒の高さが値の大きさです。「逆順」にすると、入れかえの回数がどう変わるか予想してから動かしましょう。
比較の回数は、どの並びでも両方とも15回(6 × 5 ÷ 2)です。入れかえは、「逆順」ではバブルソートが15回、選択ソートは3回。「ほぼ並んでいる」ではどちらも1回です。
プログラムで動かす
比較と入れかえの回数を数えるプログラムです。「書きかえる」で配列の中身を変えて、回数がどう変わるか確かめましょう。
やってみよう(共通テスト形式)
このサイトで作った問題です(過去の試験問題ではありません)。
文化祭で模擬店を出した C さんのクラスでは、5種類の商品の売れた個数を配列 Kosu に入れている。売れた個数を大きい順(降順)に並べかえるため、となりどうしを比べて入れかえるプログラムを作った。配列の添字は 0 から始まる。
(01) Kosu = [18, 25, 9, 31, 14] (02) n = 要素数(Kosu) (03) i を 0 から n - 2 まで 1 ずつ増やしながら繰り返す: (04) j を 0 から ア まで 1 ずつ増やしながら繰り返す: (05) もし Kosu[j] イ Kosu[j + 1] ならば: (06) tmp = Kosu[j] (07) Kosu[j] = Kosu[j + 1] (08) Kosu[j + 1] = tmp (09) 表示する(Kosu[0], " ", Kosu[1], " ", Kosu[2], " ", Kosu[3], " ", Kosu[4])
ちょっと寄り道:豆知識・こぼれ話
試験に出るとはかぎりませんが、知っていると情報がもっと面白くなる話です。
1890年、並べかえと集計を機械にまかせた
アメリカでは10年ごとに国勢調査をしていますが、1880年の調査は、手作業での集計に7〜8年もかかりました。そこでアメリカ政府の国勢調査の事務局は1888年に新しい集計方法を募集し、ハーマン・ホレリスの機械が選ばれました。
1人分の答えを穴の位置で表したカード(パンチカード)を機械に読ませ、項目ごとに数えたり、仕分け箱に分けたりするしくみです。1890年の調査では約6300万人分のデータをこの機械で集計し、前回より早く結果を発表できました。ホレリスの会社は、のちに合併を経て IBM になります。
参考:米国国勢調査局 “The Hollerith Machine”/同 “History and the Census: Herman Hollerith and Mechanical Tabulation”
クイックソートは、辞書を引くために生まれた
クイックソートを考えたのは、イギリスの計算機科学者トニー・ホーアです。1959年、ソ連(今のロシア)のモスクワ大学で機械翻訳の研究をしていたときのことでした。
ロシア語の文の単語をアルファベット順に並べておけば、磁気テープに入ったロシア語・英語の辞書を前から順に1回たどるだけで引ける、と考えたのがきっかけです。こうして生まれた方法は1961年に発表され、今も速い並べかえの代表として使われています。
参考:Computer History Museum “Sir Antony Hoare”(フェロー紹介)/C. A. R. Hoare, “Algorithm 64: Quicksort”, Communications of the ACM, 1961
Python の並べかえの中身
Python の並べかえ(sort)には、Python 2.3 から、ティム・ピーターズが2002年に考えた「Timsort(ティムソート)」という方法が使われるようになりました。
現実のデータは一部が既に並んでいることが多い、という点に目を付け、並んでいる部分を見つけて生かしながら、挿入ソートと併合(マージ)ソートを組み合わせて並べます。また、同じ値同士は元の順番を保つ「安定な」並べかえです。例えば、名簿を学年で並べかえても、同じ学年の中では元の順番が崩れません。
参考:Python 公式ドキュメント “Sorting Techniques”(ソートの安定性・Timsort)/CPython の Objects/listsort.txt(T. Peters)
わからなかったら、ここへもどる
あわせて読む
次はこれ
先生・おうちの方へ
つまずきやすい所:①入れかえで一時変数を使わず、値を消してしまう。②選択ソートとバブルソートで、1回ごとに「どこが決まるか」(左から最小/右から最大)を混同する。③比較の回数と入れかえの回数を区別しない。
このページの決まり:選択ソートは「残りの最小の位置を覚えておき、最後に1回入れかえる」形、バブルソートは「左から右へ比べ、大きい値を右端へ運ぶ」形で説明しています。教材によっては、最小が見つかるたびに入れかえる形や、右から左へ比べる形もあります。比較の回数(n(n−1)/2)は同じですが、入れかえの回数は形によって変わります。試験では問題文のプログラムに従います。
授業で使うとき:「さわってみよう」で、同じ並びを2つの方法で並べ、比較と入れかえの回数を比べさせると、「アルゴリズムの比較(効率)」につながります。数値・問題はすべてこのサイトで作ったもので、プログラムの表示は実行器で確かめています。
学習指導要領:情報Ⅰ (3)ア(イ) / 参考:高等学校学習指導要領(平成30年告示)解説 情報編 情報Ⅰ (3)ア(イ)・イ(イ)(探索や整列などの典型的なアルゴリズム)、文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第3章 学習15「アルゴリズムの比較」(選択ソート・クイックソート)、大学入試センター「令和7年度試験の問題作成の方向性、試作問題等」概要「情報」5. 共通テスト用プログラム表記の例示