t-hom’s diary

主にVBAネタを扱っているブログ…とも言えなくなってきたこの頃。

そんなに沢山のソートアルゴリズム、意味あるの?って方へ

みなさん本日は情報処理試験お疲れ様でした。
(私は今回申し込みすらしてないけど)

本当は試験前にこの記事を書きたかったんだけど文章悩んでるうちに試験が終わってしまった。まぁ今回ダメだった方、決意を新たにした方もいると思うので一応公開するか。

さて、何かを学習しようとしたときに障害になる考え方がある。
「それ、意味あるの?」ってやつだ。

試験のためと割り切れる方は良いけど、試験でしか役に立たないような知識を無理やり頭に詰め込むのってなんか空しい。

そこで今回は情報処理試験で出てくるソートアルゴリズムの存在意義について書こうと思う。まずもって数が多すぎる。そんなにいる?意味ある?

そもそも自前でソートなんてする?

まあ普通はプログラミング言語にはソート機能が組み込まれていたり、専用のライブラリなんかも充実してるので、いまどき自前でソートなんてやらんでしょって意見もある。

ところが、そうでもない。たとえばVBAでプログラムを組んでてデータをオブジェクトでコレクションに入れて管理しようと思うと、コレクションにはソート機能が無いし、そもそもオブジェクトなのでどのプロパティーをキーにソートするのかなど細かく調整したい場合もある。それで、コレクションをソートするプログラムを組んだことがある。

各ソートの存在意義

選択ソート

まず一番小さい数を探して、次に二番目に小さい数を探して。。というソート。すこぶる遅い。
このソートの存在意義は、実装がとにかく簡単ってことと、前提知識なしに誰でも思いつくソートであること。

挿入ソート

データを適切な位置に挿入していくソート。普段は遅いけど、ほぼ整列済のデータに対しては数あるソートの中でも最も高速になることがある。この特性が挿入ソートの存在意義。実装も簡単。
クイックソートで大体並んで来たら挿入ソートに切り替えると高速になるそうだ。

バブルソート

隣どうしのデータを比較して交換するソート。このソートの存在意義は、直観的に理解できることと実装が簡単であることだ。いくら自前ソートの機会が減ってるとはいえプログラマを自認するならバブルソートくらいは書けないとね。

クイックソート

名前どおり高速なソート。このソートの存在意義はとにかく速いことだが、アルゴリズムは少し複雑になる。しかし常に最速かというとそんなことはなく、データの特性によってはすこぶる遅くなる。

シェルソート

改良版の挿入ソート。かなり高速なソートで、データの特性によって並はずれて遅くなるということもない。比較するデータの間隔のチューニングが難しい。

ヒープソート

配列を木構造に見立てたソート。このソートもかなり高速で、データの特性によって並はずれて遅くなるということもない。

マージソート

データを分割して分割して分割してこれ以上分割できなくなったところで統合して統合して統合してという順でソートしていく。統合時にソートされる。

このソートは比較的メモリ使用量が大きいけれどかなり高速である。

加えて重要なのは安定ソートであるということ。安定ソートとは、たとえば氏名で並び替えた後に都道府県で並び替えると、各都道府県データのなかでは氏名順の並びをキープしているようなソートのこと。

クイックソートシェルソートヒープソートなどの他の高速ソートは不安定ソートなので、都道府県順で並び替えると氏名の順はぐちゃっとなってしまうけど、マージソートは崩れない。

他の安定ソートとしてはバブルソート、挿入ソートがある。遅いけど。

高速かつ安定ソートで、さらにデータの並び順で速度が変わることがないと三拍子そろった個人的には最強ではないかと思うソート。

ただまあクイックソートほど速くはないし、メモリを食うソートなのでこれもケースバイケース。

まとめ

確かに安定・高速・簡潔・元の並びに依存しないと四拍子そろった最強のソートがあればこんなにたくさんソートを覚える必要がなかったかもしれないが、逆にいえばこの多様性こそがプログラミングの学習において重要であるともいえる。

「並び替え」というひとつの課題でこれだけ多彩な回答が存在するというのは、自分が作ったプログラムに対してもより良い方法があるのではないかという考察のきっかけになる。

今回取り上げたソートはすべて基本情報の出題範囲であるが、それぞれに長所・短所があって面白い。

最後にこの記事の執筆のきっかけになったサイトを紹介する。
www.toptal.com

これを見て、シェルソートはやっ!!まじで!?と思ったのがきっかけ。
このソートは完全にノーマークだった。

当ブログは、amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、 Amazonアソシエイト・プログラムの参加者です。