並べる

＊次のURLに整列手順例を挙げておきます。必要に応じてご覧ください。　
　　　https://pi-3.net/figblog/sort/sort_add.html　

◇ 選んで並べる 　 　　
　まず、鉛筆を一列に置く。先頭を2本目から末尾まで順に比べ，相手が長ければ場所を入れ換える。同じことを、2本目は3本目から、3本目は4本目から比べ、というように末尾の1本までやると、鉛筆の長さの降順に配列できる。未整列の中から、最長のものを選んで、次々に並べていくわけだ。

　比べる手数は、はじめ全数より1だけ少ない回数だが，どんどん減っていく、しかし、全部の手数は、鉛筆の本数を n として　n2 に比例する。そこで、この方法は2乗時間だと呼ばれる。入れ換える手数も同様になる。整列アルゴリズムでは［挿入ソート］と呼ばれる。

◇ 探して並べる 　 　　　　
　ある鉛筆に着目し、これと先頭よりの隣とを比べて相手より長ければ入れ換えることを先頭に向かって進める。隣が長くなったら止めて、いま着目した次の鉛筆で同じことをやる。これを2本目から末尾まで順にやれば、降順に整列できる。整列済みの中に並ぶべき境所を探して、そこへ入れていくわけだ。

　比べる手数は、はじめ1回だが、どんどん増える．毎度先頭まで比べるとは限らないが、平均でその半分くらいにはなろう。手数の合計はやはり n2 に比例するから、これも2乗時間だ。入れ換える手数も同様になる。鉛筆を縦に並べてやると、長さに応じた場所まで泡の立つように鉛筆が昇っていくから，［泡立ち整列（バブルソート）］という。

◇ 交ぜて並べる 　 　　　　
　鉛筆を幾つか群に分割する。必要に応じて鉛筆の長さを比較しやすい小さい群（最小は要素数１）までさらに分割する。分割後の併合（マージ）は対応する分割列を先頭から比べ，長い方から新しい第３の配列に置く。どちらか一方の分割列が全て終わると，他方の分割列の残りはそのまま第３の配列の後に並べる。次の対応分割列も同様にして、新しい第４の配列を作る。これを繰り返し、一つの降順に整列した配列に併合する。

　［2ウェイ・マージ］と呼ばれる方法だ。比べる手数も入れ換える手数も　n log2 n に比例する。答案を学生番号順に揃えるときなどに重宝する。

◇ 分けて並べる 　 　　　
先頭から順に，末尾と比べて短い鉛筆がある場所を探す。次に，末尾の一つ手前からから逆順に、末尾と比べて長い鉛筆がある場所を探す。両場所の鉛筆を入れ換えて、さらに両方向に進める。ぷつかった所で先頭から探した短い鉛筆と末尾と入れ換える。そうすると、そこに置いた鉛筆より長いものが先頭からそこまでに、また短いものがそこから末尾までに、それぞれ分けられたことになる。同じことを、そこを除いた前半分と後半分とについてやる。こむつかしくいうと、再帰的に実行する。ついには、分けた部分の鉛筆がただ1本ずつになり降順に整列できる。

　［区分化整列］とか［クイックソート］と呼ばれるが，気の利いたプログラミングの本などでちょくちょく出会うものだ。比べる手数は　n log2 n に比例し、入れ換える手数はこれより少なくて済むという。

◇ エイヤッと並べる 　 　　　
最後に、いささか変わった方法を紹介する。
鉛筆の束を片手でゆる目に握り、これを机の上に真直にエイヤッと立てる。一番背の高いものから順に抜きとって並べる。束がなくなるまでやって，降順の整列が完了だ。配列の最小値（最大値）を持つ要素を探してそれを配列の先頭要素と交換することで整列を行う［選択ソート］のアルゴリズムの一種だろう。

　比べる手数はエイヤッの1回、並べる手数は n に比例するから、この方法は線形時間ということになる。前出の2乗時間はいうに及ばず、n log2 n と比べても格段に差がある。こういうものを「ツポにはまった小道具」つまり「ガジェット（gad-get）」というのだそうだ。

〇 整列手順例
　冒頭で言及したとおり、上記本文にほぼ対応した手順例を挙げてあります。
　　　https://pi-3.net/figblog/sort/sort_add.html

📖
本稿は次の文献を参考にしました
　　遊びの発想　別冊サイエンス82(1987) 　A.K．デュードニー著，山崎秀記監修

---

---

👀
何かを［ソート］することにはちょくちょく出くわしますが、その［アルゴリズム］を意識してみるとなかなか面白いものがあります。今回の［並べる］は10年前の原稿。ネタに困り再登場してもらいました。久しぶりに再掲するにあたってチェックのため読み直しましたが、結構な時間をいろいろな［ソート］で楽しみました。［ソート］の手順を考えることは、小学生から学生、大人まで楽しめるよい脳トレだと思います。

本文の手順方式には沿っていませんが、
実に愉快な動画コンテンツがありましたので、併せてご紹介します。
10年前は日本語のコンテンツがあまり見当たらず寂しく感じましたが、今はいろいろとアップされているようです。が、ここでは今回も当時も面白いと感じた「ソート・ダンス」を引用しておきます。

ソートダンス？
楽しみながらよく理解できそうなコンテンツです。
教材により理解の難易度が変わることを教えてくれます。制作はいずれも、
　　　　　　　　Sapientia University, Tirgu Mures (Marosvásárhely), Romania

○ 挿入ソート
整列済み最小配列を作成し、他の要素を適切な位置に挿入して並び替えます。
Insert-sort with Romanian folk dance
　http://www.youtube.com/watch?v=ROalU379l3U&feature=related（上と同じ）
○ バブルソート
基点となる要素とそれ以外の要素の値を比較・交換しながら並び替えます。
Bubble-sort with Hungarian (“Csángó”) folk dance
　http://www.youtube.com/watch?v=lyZQPjUT5B4&feature=related
○ マージソート
配列を再帰的に分割していき、再び併合（マージ）していくことで、並び替えます。
Merge-sort with Transylvanian-saxon (German) folk dance
　http://www.youtube.com/watch?v=XaqR3G_NVoo&feature=related
○ クイックソート
軸要素よりも大きい値と小さい値を入れ替えていくことにより並べ替えます。
Quick-sort with Hungarian (Küküllőmenti legényes) folk dance
　http://www.youtube.com/watch?v=ywWBy6J5gz8&feature=related
○ 選択ソート
配列の中から、 最小あるいは最大の値をもつものを探し、それを先頭要素と交換しながら並び替えます。
Select-sort with Gypsy folk dance
　http://www.youtube.com/watch?v=Ns4TPTC8whw&feature=related
○ シェルソート
ソート効率を高めるため、あらかじめ離れている要素を交換しておき、挿入ソートで並べ替えます。
Shell-sort with Hungarian (Székely) folk dance
　http://www.youtube.com/watch?v=CmPA7zE8mx0&feature=related