Pythonでマージソートの挙動を可視化してスッキリするページ

  • このエントリーをはてなブックマークに追加
Advertisements

ランダムなデータをソートするアルゴリズムは動画にして観察するとなぜだか癒されます。マージソートをプログラミングするためには再帰処理も覚える必要があり勉強にもなります。という事で、ここではソートの中でも一際人気なマージソートをPythonで可視化しながら学びます。

こんにちは。wat(@watlablog)です。マージソートの学習は再帰処理も学べる良い題材ですここでは可視化コードを紹介しながら覚えていきます

マージソートの概要

ソートアルゴリズムと計算量

たいていのプログラミング言語には標準でソート(並べ替え)の関数が付属していますが、あえてそのアルゴリズムを学ぶ事でプログラミングにおける考え方を習得します。

当ブログでは既に「Pythonコードと図解で理解するバブルソートのアルゴリズム」でバブルソート、「Pythonで選択ソートのアルゴリズムを実装する方法【動画付】」で選択ソート、「【動画付き】Pythonで挿入ソートのアルゴリズムを実装する方法」で挿入ソートと3つのソートアルゴリズムを学びました。

これらのソートはいずれも計算量が\(O(N^{2})\)と遅いソートに分類されますが、アルゴリズムがシンプルで実装しやすいために少ないデータ量においては選択肢の一つになるでしょう。

シリーズ第4段となるマージソートは最悪計算量が\(O(N \log N)\)と二乗オーダーではない高度なソートに分類されます。

高度な分、マージと再帰処理というテクニックを覚える必要はありますが、プログラミングの学習にはちょうど良い題材です。

また、記事の最後ではマージソートの処理を動画で可視化する事によって理解を深めるとともに癒されます。是非最後までご覧ください。

Pythonコードで「マージ」を体験する

マージソートは完全にランダムなデータを並べ替えるアルゴリズムですが、「マージ」という別途定義されたアルゴリズムを使います。

マージ(Merge)とは、日本語で併合するとか混ぜるという意味があります。マージアルゴリズムと呼ぶ時は、2つのソート済みデータをまとめて1つのソート済みデータに変換するアルゴリズムを指します。

図解すると以下のようになります。

マージの説明図

既にソートされたリストであれば、左から順番に要素を抽出して大小を比較していけば全体がソートされた1つのリストになります。

以下は手順の図解です。リストの長さが異なっている場合、最後は余った分を全体リストに後付けすれば問題ありません。

マージの説明(手順)

これをPythonでプログラミングすると以下のコードとなります。Pythonはちょっと文法を覚えるだけでアルゴリズムをそのまま理解する事ができるため、コード内のコメントで解説は十分と思います。

コードを実行すると以下の結果を得ます。既にソートされたリスト(ndarrayですが)を作成し、マージを行う事で全体がソートされた1つのリストができました。

Pythonコードで「再帰処理」を体験する

マージソートをプログラミングするためには、マージアルゴリズムに加えて再帰処理Recursive processing)を覚える必要があります。

再帰処理とは、あるものを定義する時にそのもの自身を参照する処理の事です。こちらもまずはPythonコードで体験してみましょう。

以下のコードが再帰処理の例です。

過去の基本情報技術者試験の問いを参照しました。この再帰関数は終了条件を指定している所がキーポイントです。終了条件を指定しないと再帰処理は無限ループに陥ってしまいます。

これは処理をノートに書いていけばわかりやすくなりますが、最終的には初期値から1ずつ引いていった値を全て足すという処理になります。

再帰処理をコーディングする事でこのような処理も書く事ができ、一般に再帰処理を覚える事でプログラミングの幅がひろがると言われています。

マージソートの処理イメージ

マージアルゴリズムと再帰処理を体験した事で、マージソートMerge sort)のアルゴリズムをプログラミングする事ができます。

マージソートは完全にランダムなリストを要素数が1になるまで分割します。この「要素数が1になるまで」という処理に再帰処理を使います。

要素数が1になったという事は、これはソート済リストになった事を意味するため、マージ処理を使う事ができます。

そのため分割したリストを逆順にマージしていけば、最終的に全体がソートされたリストを得る事ができます。

コードを紹介する前に、マージソートのイメージを図解しておきましょう。
ちなみにマージソートは同じ数が存在しても、元のリストと並び順が変わらない安定したソートにもなっています。

ついでに動画も見てみましょう。動画の作り方と、もっとスッキリする動画は記事の最後で…。

マージソートの動画(N=10)

図にすると簡単に理解する事ができます。それではPythonでコーディングしていきましょう。

Pythonでマージソートするコード

Advertisements

以下がマージソートの全コードです。マージ関数merge()とマージソート関数merge_sort()を作成しました。マージソート関数内に再帰処理による分割を入れています。

結果は以下。ランダムなリストを入力してソートされました。

Pythonでマージソート処理を動画にするコード

Advertisements

最後はシリーズ恒例、動画を作成するコードを紹介します。ソートが速いのでcreate_gif()関数をちょっといじっています(最後の状態を長く見せるために処理を追加)。

以下が結果です。100個のデータが揃っていく様は気持ちが良いです。是非マシンスペックの許す限りのデータ数でやってみてください。

マージソートの動画(N=100)

まとめ

この記事ではマージアルゴリズムと再帰処理を学び、マージソートアルゴリズムのコードを紹介しました。

ソート1つとっても様々な手法があり、人類のアイデアの多さに脱帽しますね。

ちょっと高度なマージソートも理解する事ができました!
Twitterでも関連情報をつぶやいているので、wat(@watlablog)のフォローお待ちしています!

  • このエントリーをはてなブックマークに追加

SNSでもご購読できます。

コメントを残す

*