プロクラスの森です。
最近見つけた面白いムービー。
波形のようなデータが、だんだんきれいな並びに整頓されていきます。
なんだか不思議な動きですよね。
「15 Sorting Algorithms in 6 Minutes」というこのムービーは、コンピューターによる色んなソートアルゴリズムの様子のアニメーションにしたものだそうです。
ソート (sort) とは、データの集合を一定の規則に従って並べること。
見た通り、長さの順にデータを整頓している訳です。
こうやって視覚化すると、少しずつ整頓されていく様子が面白いですね。なんとなく自然の動きや、微生物の動きを見ているような気分になります。
きれいな並びになるまでに、色々なパターンがあります。
これは、それぞれ並び替えのアルゴリズム(手順)が違うから。
Insertion Sortやら、Cocktail Shaker Sortやら、画面の左上に小さくアルゴリズムの名称が表示されています。どれも最終的には同じように整頓されるのですが、方法はこんなに色々あるんですね。
ソートの元祖 バブルソート (bubble sort)
最も原始的なのが、ムービー後半4:00頃に登場するバブルソート (bubble sort)。
隣同士の要素を比較して入れ替える、を繰り返す、というもので、プログラムも比較的単純。
バブルソートという名は、次の値が一つづつ選び出されてくるところを、水面に泡が一つづつ浮かんでくる様子に例えて名付けられたネーミングだそうです。（一つ一つ出てくる光景から、何をイメージするかは色々あるとは思いますが）
このムービーだと、右側に一つずつ大きい数が移動していきます。
今の主流 クイックソート (quick sort)
一般的に最も少ない手順で整頓を終えることができると言われているのが、ムービーの0:40頃に登場するクイックソート (quick sort)。
バブルソートと比べると遥かに大量のデータを整頓しており、効率の違いは歴然です。
仕組みは複雑なので割愛しますが、面白い動きです。
ただ「じゃあもう全部クイックソートでいいじゃん！」と思ってしまいそうですが、対象となるデータの並びや数によっては必ずしも高速ではなく、他の方法の方が速いという場合もあります。
そんなわけで、状況に応じたこんなに色んなソート方法があるんですね。
こんな風に個性的なソートアルゴリズムですが、実際のプログラミングではすでに用意されているソート関数を使うことが多く、アルゴリズムの中身を理解する機会はそんなにないかもしれません。（ベテランの方の領域ではないかと思います）
でも普段見る機会のないソートの様子をこうして視覚化すると、コンピューターもまじめに働いて案外大変なんだなあと、しみじみ思うのでした。