Pythonで選択ソートのアルゴリズムを実装する方法【動画付】

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

Pythonを使ったアルゴリズム学習シリーズです。今回は「選択ソート」の概要を図付きで説明し、Pythonでプログラミングする方法を紹介します。また、動作結果をアニメーションで示すことで理解を深めます。

こんにちは。wat(@watlablog)です。ここでは選択ソートのアルゴリズムをPythonで実装することを目標とします

選択ソートの概要

目標

プログラミングにおいて、既に先人が完成させているはずのアルゴリズムを写経したりして学ぶことがなぜ重要かは「Pythonコードと図解で理解するバブルソートのアルゴリズム」で記載した通りです。

今回はソート(並べ替え)アルゴリズムの中でもバブルソートに次いで有名な選択ソート(Selection sort)について学習します。

選択ソートの目標はバブルソートと同様にデータを昇順、または降順に並べ替えることです。以下に入力データと出力データの関係図を示しますが、選択ソートは最小値(降順の場合は最大値)を探索して順番に並べていく処理を行う特徴があります。

選択ソートの目標

フローチャートとPythonコードの例

図だけでは曖昧なので、フローチャートを以下に示します。

ここで示すminjは最小値を示すデータ指標です(要素の中で最小値が何番目か)。

Loop1はデータの要素数分のループが回ります。しかし最小値探査部分でも明示はしていませんが、探査のためのループ(別のアルゴリズム)も回ることになります。

その後、i番目の要素とminj番目の要素を交換(swap)する処理を行い、ループ終了時にソートが完了します。

選択ソートのフローチャート

以下にdef関数の形式で書いたPythonコードを示します。引数にデータ配列data、dataの要素数nを渡しています。ここではソートのアルゴリズムを学習することが主目的であるため、最小値探査アルゴリズムはnumpyのargminを使いました。

以下に本コードの処理アニメーション例をGIF動画で示します。ソート済のデータ(緑色)が左側から確定していくのはバブルソートと同様ですが、バブルソートが隣り合った要素同士で比較していたのに対し、選択ソートはi番目からn番目までの最小値と直接値を交換しているのが特徴です。

選択ソートの処理アニメーション

「順次最小値をソート済のすぐ隣に持ってくる」というのがシンプルな説明でしょうか?

選択ソートの図解

処理回数とオーダー

上記アニメーションのカウント(グラフ内のcount数)はデータの要素数10で止まっていますが、実際には毎ループで残りの要素数内の最小値(または最大値)を同じくループで探すことになるため、比較や交換といった処理回数はデータ数を\(N\)とすると\(N(N-1)/2\)回行われます。

そのため選択ソートのオーダーは\(O(N^{2})\)となります。

検証のためのPythonコード

先ほどは関数部分のみでしたが、実際に配列を作成して選択ソートアルゴリズムを使ってみるコードを以下に示します(コピペで動くはず)。

サンプルデータはrandomを使ってランダムな数値配列を生成しています。

本コードを実行すると、コンソールにソート前の配列(上)とソート後の配列(下)がプリントされます。確かに昇順になっていることを確認しました。

ちなみに、「np.argmin」を「np.argmax」に変更することで降順にすることが可能です。

おまけ:選択ソートアニメーション

記事の途中で紹介したアニメーションは以下のコードで処理中の画像をmatplotlibで1つずつプロット保存して作成しました(汎用性は何も考えていないやっつけコードですが…)。

まとめ

本記事では、バブルソートに次いで有名な選択ソートを学び、動画を用いた概要の説明と共にPythonによるコードを紹介しました。

選択ソートも\(O(N^{2})\)オーダーで速いソートではありませんが、考え方がシンプルなので他のコードにも応用が効きそうです。

選択ソートも習得しました!いつもはライブラリに頼っているアルゴリズムも、あえて学ぶと頭の体操になりますね!Twitterでも関連情報をつぶやいているので、wat(@watlablog)のフォローお待ちしています!

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

SNSでもご購読できます。

コメントを残す

*