もっと かしこく ならべる

一マスずつは おそい

前回の やり方は たんじゅんで よかったです。
となりを くらべて、大きいのを うしろに。
でも 列が 長くなると
くらべる ことが 多すぎます。
カードが 二倍に なると
比較は 四倍に 跳びます。
四つなら すぐですが、
三十二なら 気が 遠くなります。

列を 二倍に してみましょう。(長さ 二倍 → 比較は 四倍に 爆発)

ぼうが こわいほど たまりますね。
列が 長くなるほど
おそさが ひどく なります。
もんだいは 列ぜんたいを
一つの かたまりと 見て
最後まで くらべる ことに あります。
では かたまりを
分けて みたら どうでしょう?

半分に 分ける

長い 列を まるごと あつかわず、
半分に 分けましょう。
その 半分も また 半分に、
その 半分も 半分に。
分け続けると
最後には 一マスだけ 残ります。
でも 一マスは
もう 並んでいるのと 同じです。
ひとりだから くらべる ものが ないのです。

一つの 束を 半分ずつ 分け続けて。(8 → 4+4 → 2+2+2+2 → 一マスずつ)

分ければ おしまいでしょうか?
いいえ、分けた ものは
また 集めて 列に します。
一マスを
二つずつ 組にして 合わせ、
その 合わせた ものを また 合わせ。
そして 並んだ 二つを
合わせる のが、思いのほか かんたんです。
次で 見ましょう。

並んだ 二つを 合わせる

並んだ 二つの 束が あります。
二つを 一列に 合わせるのに、
こつは 先頭だけ 見る ことです。
二つの 束の 一マス目を くらべ
小さい 方を 結果に 落とします。
その 場所は 次の マスが うめ、
また 先頭どうし くらべます。
ファスナーを 閉めるように
一マスずつ かみあって 合わさります。

二つの 束の 先頭を くらべ 小さい 方を 落とします。(ファスナーのように 一マスずつ 合わせる)

ふしぎ じゃ ないですか?
ばらばら 全体を くらべる ときは おそかったのに、
それぞれ 並んだ 二つを 合わせる ときは
先頭だけ 見れば よいので 速いです。
分けた おかげで
小さく 並んだ かけらが でき、
その かけらを 少しずつ 合わせると
いつのまにか まるごとの 列に なります。

なぜ 速いか、層の 数

なぜ これが 速いのでしょう?
半分に 分けるから
分ける 層が わずかです。
列が 二倍に なっても
層は ちょうど 一つ ふえるだけ。
そして 一層を 合わせる 費用は
列の 長さほどです。
だから 全体の 費用は
層の 数 かける 列の 長さ。
一マスずつ(長さ かける 長さ)より
ずっと ゆっくり 大きくなります。

層を 広げ、列の 長さを 変えて。(層の 数 x 一層 = 一マスずつより ゆっくり ふえる)

正確な 式は あとで もっと 学びます。
今は 感じだけ 持ち帰りましょう。
半分に 分けると
層は のろのろ ふえ、
各層は かるく 合わさるので、
全体が 速くなる という こと。
分けて 合わせる この 一手が
速さを がらりと 変えるのです。

まとめましょう

一本の 線で つなぐと こうです。
一マスずつ くらべる 並べかえは
列が 長いほど おそい。
だから 列を 半分に 分け、
最後まで 分けて 一マスに、
つまり もう 並んだ かけらに します。
その 並んだ 二つを ファスナーのように 合わせ、
層の 数だけ 合わせれば よいので
列 ぜんたいが ずっと 速く そろいます。
分けて 合わせる。
これが かしこい 並べかえの 核です。

四つの 段階を 順に 押して 一周。(分ける → 一マス → 合わせる → 層の 数だけ = 速い)

ここでは 合わせるのに いつも 落ち着いて 半分に 分けました。
でも、分ける 基準を
少し ちがえる 親せきも います。
まん中では なく
ある 一マスを 目じるしに して
小さい ものと 大きい ものに 分ける 方法です。
その 目じるしを どう 選ぶかは
あとの はなしに のこして おきます。
今日は これだけ 持ち帰りましょう。
半分に 分けて 合わせれば 速くなる。