ならべる——差しこみで

よみもの＋手を動かす時間：およそ25分

速さの裏には、そろえた人がいる

前のレッスンの二分探索は、半分をまるごと捨てられる手順でした。ただしあの速さには前提があります——数列が、あらかじめそろっていることです。

では、そのそろえる仕事は誰がやるのでしょう。バラバラの列を順番どおりにならべる仕事を、プログラミングの世界ではソートと呼びます。今日はその仕事の、いちばん人間らしい手順から始めます。

レッスン1を思い出してください。コースの冒頭で、実験室が数の列をならべる様子を「中身の説明ぬきで」再生しました。そして演習で、あなたはトランプの手札をならべる自分の手順を、曖昧さのない日本語で書きました。

あのとき再生されたものと、あなたが書いたものは、同じ手順です。名前を挿入ソート（そうにゅうソート）——差しこんでならべる手順、といいます。今日は名前だけでなく、回数の物差しもあてます。

トランプの手つきを、曖昧さのないことばに直すとこうなります。

再生して、ずらして差しこむ動きに注目してください。差しこむ場所をあけるために、大きい数たちが1つずつ右へ動いていきます。

数列（コンマ区切りで打ちかえられます）

差しこみでならべるくらべた回数 0

528193

ならべる前。左はしの1枚は、それだけで「そろっている」

1 / 22 場面

どの瞬間も、左側はつねに「そろった列」です。手に取った1枚の行き先だけを考えればよい——これが、この手順が人間の手に自然になじむ理由です。

数列を打ちかえて、くらべた回数を観察してみてください。同じ6個でも、ならびかたで回数がまるで違います。

最良の場合は6個で5回——個数より1つ少ない回数で、確認だけして終わります。最悪の場合は15回。レッスン2で学んだとおり、手順の力くらべに使うのは最悪の場合のほうです。

では、逆順の枚数を倍にしてみます。[12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] を実験室に打ちこむと、66回です。

6枚で15回、12枚で66回。枚数が倍になると、最悪の回数はほぼ4倍になりました。比例なら「倍になったら倍」のはずですから、これは比例より急な、別のかたちです。

このかたちは n²（エヌの2乗） と呼ばれます。正体は「毎回、左のぜんぶとくらべてぜんぶずらす」の積み重ねです。かたちどうしの本格的なくらべあいはレッスン6でやるので、今日は「比例より急な坂に出会った」とだけ覚えてください。

ここまで読むと「遅い手順」に見えるかもしれません。でもそれは、最悪の場合だけを見た言い分です。

ほぼそろっている列に、この手順はめっぽう強いのです。12枚のうち最後の2枚だけが入れかわった [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 11] を試すと、12回で終わります。同じ12枚でも、逆順の66回とは別世界です。

✎ 演習：逆順7枚を予想する

逆順の7枚 [7, 6, 5, 4, 3, 2, 1] をならべると、くらべる回数は何回になるでしょう。まず紙の上で予想してから、実験室に打ちこんで確かめてください。

ヒント1（考え方）

逆順では、手に取った1枚は左のぜんぶとくらべることになります。2枚目は1回、3枚目は2回、4枚目は3回——この調子で、最後の7枚目まで足してみてください。

こたえ

1 + 2 + 3 + 4 + 5 + 6 = 21回です。6枚の15回は 1+2+3+4+5、12枚の66回は 1+2+…+11。最悪の回数の正体が「1からの足し算」だと分かると、枚数が倍でほぼ4倍になる理由も、この足し算が長く・高くなることだと見えてきます。