何ゴト?

日々の何事かを書いていきます。

しめじソートの話:ピタゴラスイッチ【2018/05/18】

おもしろい並び替えの話がありました。

↓こちらのバラバラの15本のしめじを背の順に並べるにはどうすればよいでしょうか?

わかりやすいように、背の高さを数字で表してみます。

しめじたちを真ん中の1番と5番の辺りで、2つに分けます。

(【11】【6】【3】【14】【12】【4】【9】【1】)(【5】【15】【10】【7】【13】【8】【2】)

そして、このグループをまた2つに分けます。

(【11】【6】【3】【14】)(【12】【4】【9】【1】)(【5】【15】【10】【7】)(【13】【8】【2】)

さらに2つに分けていき、それぞれのグループが2つになるまで分けると、8つのグループができました。

(【11】【6】)(【3】【14】)(【12】【4】)(【9】【1】)(【5】【15】)(【10】【7】)(【13】【8】)(【2】)

それぞれのグループで、長い方を右側に置きます。

(【6】【11】)(【3】【14】)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)

次に、一番左のグループとその隣のグループの長い方を上に置き2つを比べます。

【11】【14】←ココ

(【6】空)(【3】空)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)

長さの勝った方を残します。負けた方はいったん元に戻します。

【14】

(【6】【11】)(【3】空)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)

となりにあった短いものと、今負けたものを比べます。

【14】

【11】【3】←ココ

(【6】空)(空 空)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)

勝った方を残し、負けた方は元に戻します。

【11】【14】

(【6】【空】)(【3】【空】)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)

最後に残った2本を比べて同じようにすれば、

【11】【14】

【6】【3】←ココ

(【空】 【空】)(【空】 【空】)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)

キレイに並んだ4本組ができます。

(【3】【6】【11】【14】)

(【空】 【空】)(【空】 【空】)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)

他のも同じようにすると、↓こうなります。

(【3】【6】【11】【14】)(【1】【4】【9】【12】)(【5】【7】【10】【15】)(【2】【8】【13】)

また隣のグループと背の高いもの同士を比べて並べるを

(【1】【3】【4】【6】【9】【11】【12】【14】)(【2】【5】【7】【8】【10】【13】【15】)

繰り返していくと、

(【1】【2】【3】【4】【5】【6】【7】【8】【9】【10】【11】【12】【13】【14】【15】)

全部キレイに並びました。