イラストでわかる「クイックソート」のアルゴリズム

計算機科学者のアントニー・ホーア氏が26歳の時に開発したソートアルゴリズムの一種が「クイックソート」です。このクイックソートがどのように動作しているのかをイメージしやすいようにイラスト付きで説明してくれるページが「Illustrated Quicksort algorithm」で、どのようなソートが行われているのかが感覚的にわかりやすく秀逸です。

Illustrated Quicksort algorithm
https://illustrated-algorithms.now.sh/quicksort

使い方は簡単で、「start」をクリックするだけでOK。あとは自動で画面左に表示されているイラストがソートされていくので、その様子を追っていくことでクイックソートのアルゴリズムを理解できます。画面右にはクイックソートを用いて果物をアルファベット順に並べ替えるコードが書かれており……。

「start」をクリックすると、画面右の1番上が白色にハイライトされ、どの位置のコードが実行されているのかわかるようになっています。

まず最初に果物の中から適切な値「ピボット」を選択。選ばれたのは「PEACH(桃)」です。

そして、「PEACH(桃)」よりもアルファベット順で先(LESS)のものと……

アルファベット順で後(GREATER)のものを分けます。

続いて、「PEACH(桃)」よりもアルファベット順で先(LESS)に出てくる果物4つの中から……

再び「ピボット」を選択。今回は「KIWI(キウイ)」が選ばれ……

キウイよりもアルファベット順が先か後かで選り分けます。今度は他の3つの果物全てアルファベット順で先(LESS)でした。

というわけで、アルファベット順で後(GREATER)のものは該当なし。

そして再びアルファベット順で先(LESS)に分類された3つの果物をソート。

ピボットは「GRAPES(ぶどう)」で……

他2つはアルファベット順で先(LESS)、アルファベット順で後(GREATER)のものは該当なし。

そして最後の2つも同じようにソートすると……

2つの果物の並び順が決定します。この2つの果物のピボットとなっていたのは「GRAPES(ぶどう)」なので……

「GRAPES(ぶどう)」を2つの後に配置。これで3つの果物の並び順が決定。

これと同じようにひとつずつ手順を戻っていくことで……

最後には6つの果物の並び順が決定するわけ。

ソートするものの数や並び順によって手順に増減はあるものの、基本的にはこれと同じような順番で並べ替えが進んでいくのがクイックソートです。