東欧の響き、ハンガリアン・フォークダンスでクイックソート法が楽しく理解できる動画
ジプシーバイオリンの軽快な響きとハンガリーの民族舞踊をみながら、コンピュータープログラムが数字の大小を並べ替える方法の一つ「クイックソート法」の原理を勉強できる1度で2回美味しい動画です。
10個の数字を並べ替え、というとものすごく簡単なようですが「2つの数の大小を比べる」しかできないコンピューターにはきちんと手順を教えてあげなければいけません。いくつか方法がありますが、クイックソート法は中でも高速と言われている方法です。
さてバラバラにならんだ数字をクイックソート法で並べていきましょう。Wikipediaの解説と併せてごらんください。
Wikipediaではまず適当に「ピボット」を置くとしていますが、この動画ではまず左端（黒い帽子）をピボッド役にして、自分より小さい数字を右から探していきます。
自分より小さい数（「2」）が見つかったので場所交代。
次にピボッド役は自分より大きい数を自分の左側に探し、順番に移っていきます。
これでピボッドの左には自分より小さい数、右には自分より大きい数が並びます。
あとは塊ごとにこれを繰り返していきます。動画はこちらから。なおコンピューターならミリ秒単位で終わりますが、この動画では6分少々かかります。コンピューターはすごいですね。
▶ Quick-sort with Hungarian (Küküllőmenti legényes) folk dance – YouTube
バブルソート版はこちら。
▶ Bubble-sort with Hungarian (“Csángó”) folk dance – YouTube
選択ソート版はこちらから。あまり高速なアルゴリズムではないので、動画も途中で巻きが入ります。
▶ Select-sort with Gypsy folk dance – YouTube
関連記事
テトリスで自動的にドット絵を描いていくすごいアルゴリズムが開発される - DNA
科学の勝利、Kinectを使って1人でも「アルゴリズム行進」を楽しめる - DNA
一部のスキャナで「勝手に原稿の数字を書き換える」エラーが出ることが明らかに - DNA
現代経済学に挑戦「超科学を根拠に投資するファンド」が登場 - DNA
容量なんと1メガバイト以下でほぼ完全に物理演算ベースのFPSゲーム「A New Zero」 - DNA
