ソート
何故だか忘れたけど、読書会でソートの話題が出たので話題に出たソート、出なかったソートを紹介しておく。
ボゴソート
なんで最初がこれなんだ、というのは気にしない。
簡単に言うと、適当に選んで、偶然そろうのを待つという方法。
もちろん実用性なんて皆無。
選択ソート
ソート対象の中から、一番小さいもの順に選択していく方法。
個人的にはこのソートの発想というか、考え方が一番わかりやすいと思う。
ただ、実際に使うことはあんまりない。
5 2 4 6 3 1 0 0 | 2 4 6 3 1 5 (5と0を交換) 0 1 | 4 6 3 2 5 (2と1を交換) 0 1 2 | 6 3 4 5 (4と2を交換) 0 1 2 3 | 6 4 5 (6と3を交換) 0 1 2 3 4 | 6 5 (6と4を交換) 0 1 2 3 4 5 | 6 (6と5を交換)
挿入ソート
簡単なソートの中ではたぶんもっとも使用されるソート。
ソート済みデータの正しい場所に新しい要素を挿入していく方法。
トランプを並び替えるときに多くの人が自然にやっている方法はこれに近いかな。
クイックソート等、他のソートのソート対象が少なくなったときに用いられることが多い。
5 2 4 6 3 1 0 2 5 | 4 6 3 1 0 (縦棒までを見るとソート済み) 2 4 5 | 6 3 1 0 2 4 5 6 | 3 1 0 2 3 4 5 6 | 1 0 (3と6を交換、3と5を交換、3と4を交換) 1 2 3 4 5 6 | 0 0 1 2 3 4 5 6
人間は挿入すべき部分に「目星」を付けることができるから、交換を繰り返す必要はないというのがちょっと違うかな。
入力データがソート済みに近ければ近いほどO(N)に近づいていく。
マージソート
要素が1つになるまで分割していって、隣り合った要素をマージしていく方法。
マージの際に、マージ対象の先頭要素の小さい方から取り出していくためソートできる。
5 2 4 6 3 1 0 5 2 4 | 6 3 1 0 5 | 2 4 | 6 3 | 1 0 5 | 2 | 4 | 6 | 3 | 1 | 0 5 | 2 4 | 3 6 | 0 1 (青い縦線をマージ) 2 4 5 | 0 1 3 6 (赤い縦線をマージ) 0 1 2 3 4 5 6 (黒い線をマージ)
クイックソート
一つpivotを選び、そのpivotより小さいものと大きいものに振り分けて、振り分けたデータに対して同じ操作を行っていく方法。
5 2 4 6 3 1 0 (一番左5をpivotとして選択) 1 2 4 0 3 | 5 | 6 (1と6をpivotとして選択) 0 | 1 | 4 2 3 | 5 | 6 | (0と4をpivotとして選択) | 0 | 1 | 3 2 | 4 | 5 | 6 | (3をpivotとして選択) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
とりあえず、ここで挙げたソートの特徴くらいは知っておいて損はないと思う。
