情報の勉強高校 情報Ⅰ

第3章 コンピュータとプログラミング

整列(並べかえ・ソート)

データを小さい順・大きい順に並べかえる手順(整列・ソート)を学びます。2つの値を入れかえるしくみと、選択ソート・バブルソートで1回ごとに配列がどう変わるか、比較と入れかえの回数が分かります。

説明

1. 背の順に並ぶとき

体育の時間に背の順に並ぶとき、隣の人と背を比べて、逆なら場所を入れ替わります。これをくり返すと、最後には全員が背の順になります。

このように、データを決まった順に並べかえることを整列(せいれつ)、またはソートと呼びます。小さい順を昇順(しょうじゅん)、大きい順を降順(こうじゅん)といいます。並んでいれば、二分探索にぶんたんさくが使えたり、順位がすぐ分かったりします。

はじめ291341822昇順(小さい順)813222941降順(大きい順)412922138
校庭で高校生たちが背の順に並ぼうとしていて、背を比べた1人が前の場所へ移ろうとしている絵
隣と背を比べて、逆なら場所を入れ替わる。

2. 2つの値の入れかえには「置き場所」が要る

並べかえの基本の動きは、2つの値の入れかえです。ジュースと牛乳の入ったコップの中身を入れかえるには、空のコップが1つ要りますね。プログラムも同じです。

いきなり Data[0] = Data[3] とすると、Data[0] の 29 が消えてしまいます。そこで先に temp(一時的に置いておく変数)に 29 を取っておきます。この3行はセットで覚えましょう。

Data[0]Data[3]tempはじめ298① temp = Data[0]29829② Data[0] = Data[3]8829③ Data[3] = temp82929
  1. (01)Data = [29, 13, 41, 8, 22]
  2. (02)temp = Data[0]
  3. (03)Data[0] = Data[3]
  4. (04)Data[3] = temp
  5. (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つは自動的に決まります。

1回目291341822最小 8 → [0] と入れかえ2回目813412922最小 13 はもう [1] → そのまま3回目813412922最小 22 → [2] と入れかえ4回目813222941最小 29 はもう [3] → そのまま完成813222941比較 10 回・入れかえ 2 回

4. バブルソート:隣同士を比べて入れかえ

バブルソートは、隣同士を左から順に比べ、左の方が大きければ入れかえる方法です。1回通すと、一番大きい値が右端まで運ばれます。泡(バブル)が浮かんでいくように見えるので、この名前があります。

2回目は、決まった右端を除いて同じことをします。1回ごとに、右から1つずつ位置が決まります。本によっては右から左へ比べて、小さい値を左端へ運ぶ形もありますが、考え方は同じです。

1回目を詳しく(隣同士を左から比べる)29 と 13291341822入れかえ29 と 41132941822そのまま41 と 8132941822入れかえ41 と 22132984122入れかえ1回目のあと13298224141 が決まる2回目のあと13822294129 が決まる3回目のあと81322294122 が決まる4回目のあと813222941完成比較 10 回・入れかえ 6 回

5. 比較と入れかえの回数

5個を選択ソートで並べるとき、比較は1回目 4回、2回目 3回、…と1つずつ減り、合計 4 + 3 + 2 + 1 = 10回です。データが n 個なら n(n−1)/2 回になります。バブルソートの比較の回数も同じです(この形のとき)。

入れかえの回数は違います。選択ソートは1回につき多くても1回なので、全部で n−1 回以下です。バブルソートは、順番が逆になっている2つの組の数だけ入れかえます。例では、選択ソートが2回、バブルソートが6回でした。

5個のとき、1回ごとの比較の回数1回目4 回2回目3 回3回目2 回4回目1 回4 + 3 + 2 + 1 = 10 = 5 × 4 ÷ 2(縦4・よこ5の長方形のちょうど半分)データの数 n比較 n(n−1)/251010451004,9501,000499,500

6. 選択ソートをプログラムで書く

選択ソートを、共通テストの書き方で書くと下のようになります。外側の繰り返しの i が「今決める位置」、内側の j が「最小を探す」役目です。最小の位置を saisho に入れておき、最後に temp を使って入れかえます。

「1行進む」で動かし、配列の値が変わる所(色が付く)を確かめましょう。

7. ほかの並べかえ方

並べかえの方法はほかにもあります。挿入ソートは、トランプの手札のように、1つずつ取り出して、並んでいる部分の正しい位置に差し込む方法です。クイックソートは、基準の値を1つ決め、それより小さいグループと大きいグループに分けることをくり返します(基準と同じ値があるときは、どちらのグループに入れるかを決めておきます)。

クイックソートは、データが多いとき、普通は選択ソートやバブルソートよりずっと少ない回数で終わります。ただし並び方によっては遅くなることもあります。詳しくは「アルゴリズムの比較(効率)」で見ます。

基準(22)より小さいか大きいかで2つに分ける2913418223517138172229413522 より小さい22 より大きい分けたそれぞれを、また同じように分けていく

ひとことで言うと比較と入れかえをくり返し、1回ごとに1つずつ位置を決めて並べる。

例題

例題1 選択ソートの途中の並び

配列 [5, 3, 8, 1, 6] を選択ソートで小さい順に並べます。3回目が終わったとき、配列はどうなっていますか。

例題2 バブルソートの比較と入れかえの回数

配列 [4, 1, 3, 2] をバブルソートで小さい順に並べます。比較の回数と、入れかえの回数を答えましょう。

練習

1
「昇順」に並んでいるものはどれですか。
2
変数 a と b の値を入れかえるプログラムとして正しいものはどれですか(「/」は行の区切りです)。
3
配列 [7, 2, 9, 4] を選択ソートで小さい順に並べます。1回目が終わったときの配列はどれですか。
4
配列 [6, 3, 5, 1] をバブルソート(隣同士を左から比べ、左が大きければ入れかえる)で並べます。1回目が終わったときの配列はどれですか。
5
6個のデータを選択ソートで並べるとき、比較の回数は全部で何回ですか。

さわってみよう

選択ソートとバブルソートを並べて動かす

同じ並びを、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])
問1
空欄 ア に入れるのに最も適当なものを選べ。
問2
空欄 イ に入れるのに最も適当なものを選べ。
問3
空欄を正しく埋めて実行したとき、i = 0 の回(1回目)が終わった時点の配列 Kosu として正しいものを選べ。
問4
空欄を正しく埋めて実行したとき、(06)〜(08)行目の入れかえは全部で何回行われるか答えよ。

ちょっと寄り道:豆知識・こぼれ話

試験に出るとはかぎりませんが、知っていると情報がもっと面白くなる話です。

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. 共通テスト用プログラム表記の例示