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

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

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

目次（項目クリックでジャンプできます）

選択ソートの概要

目標

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

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

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

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

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

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

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

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

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

import numpy as np

# 選択ソートを行う関数(data=配列データ、n=dataの要素数）
def selection_sort(data, n):
    for i in range(n):
        j = np.argmin(data[i:]) + i
        data[i], data[j] = data[j], data[i]
    return data

import numpy as np

# 選択ソートを行う関数(data=配列データ、n=dataの要素数）

def selection_sort(data, n):

for i in range(n):

j = np.argmin(data[i:]) + i

data[i], data[j] = data[j], data[i]

return data

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

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

処理回数とオーダー

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

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

検証のためのPythonコード

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

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

import numpy as np
from matplotlib import pyplot as plt

x = np.arange(1, 11, 1)
y = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

def selection_sort(data, n):
    count = 0
    axis = np.arange(1, 11, 1)

    # ここからグラフ描画
    # フォントの種類とサイズを設定する。
    plt.rcParams['font.size'] = 14
    plt.rcParams['font.family'] = 'Times New Roman'

    # 目盛を内側にする。
    plt.rcParams['xtick.direction'] = 'in'
    plt.rcParams['ytick.direction'] = 'in'

    # グラフの上下左右に目盛線を付ける。
    fig = plt.figure()
    ax1 = fig.add_subplot(111)
    ax1.yaxis.set_ticks_position('both')
    ax1.xaxis.set_ticks_position('both')

    # 軸のラベルを設定する。
    ax1.set_xlabel('x')
    ax1.set_ylabel('y')
    ax1.set_xticks(np.arange(1, 11, 1))
    ax1.set_xlim(0, 11)
    ax1.set_ylim(0, 14)

    # データプロットの準備。
    ax1.bar(axis, data, label='initial')
    ax1.bar(0, 0, label='operated')
    ax1.bar(0, 0, label='sorted')
    plt.text(1, 12, 'count=' + str(count), fontsize=20)

    # グラフを表示する。
    fig.tight_layout()
    fig.legend()
    plt.savefig('fig_' + str("{:05}".format(count)) + '.png')
    plt.close()

    for i in range(n):
        count += 1
        j = np.argmin(data[i:]) + i
        data[i], data[j] = data[j], data[i]
        # ここからグラフ描画
        # フォントの種類とサイズを設定する。
        plt.rcParams['font.size'] = 14
        plt.rcParams['font.family'] = 'Times New Roman'

        # 目盛を内側にする。
        plt.rcParams['xtick.direction'] = 'in'
        plt.rcParams['ytick.direction'] = 'in'

        # グラフの上下左右に目盛線を付ける。
        fig = plt.figure()
        ax1 = fig.add_subplot(111)
        ax1.yaxis.set_ticks_position('both')
        ax1.xaxis.set_ticks_position('both')

        # 軸のラベルを設定する。
        ax1.set_xlabel('x')
        ax1.set_ylabel('y')
        ax1.set_xticks(np.arange(1, 11, 1))
        ax1.set_xlim(0, 11)
        ax1.set_ylim(0, 14)

        # データプロットの準備。
        ax1.bar(axis, data, label='initial')
        ax1.bar([axis[i], axis[j]], [data[i], data[j]], label='operated')
        ax1.bar(axis[:i], data[:i], label='sorted')
        plt.text(1, 12, 'count=' + str(count), fontsize=20)

        # グラフを表示する。
        fig.tight_layout()
        fig.legend()
        plt.savefig('fig_' + str("{:05}".format(count)) + '.png')
        plt.close()


    # ここからグラフ描画
    # フォントの種類とサイズを設定する。
    plt.rcParams['font.size'] = 14
    plt.rcParams['font.family'] = 'Times New Roman'

    # 目盛を内側にする。
    plt.rcParams['xtick.direction'] = 'in'
    plt.rcParams['ytick.direction'] = 'in'

    # グラフの上下左右に目盛線を付ける。
    fig = plt.figure()
    ax1 = fig.add_subplot(111)
    ax1.yaxis.set_ticks_position('both')
    ax1.xaxis.set_ticks_position('both')

    # 軸のラベルを設定する。
    ax1.set_xlabel('x')
    ax1.set_ylabel('y')
    ax1.set_xticks(np.arange(1, 11, 1))
    ax1.set_xlim(0, 11)
    ax1.set_ylim(0, 14)

    # データプロットの準備。
    ax1.bar(0, 0, label='initial')
    ax1.bar(0, 0, label='operated')
    ax1.bar(axis, data, label='sorted')
    plt.text(1, 12, 'count=' + str(count), fontsize=20)

    # グラフを表示する。
    fig.tight_layout()
    fig.legend()
    plt.savefig('fig_' + str("{:05}".format(count+1)) + '.png')
    plt.close()

    return data

sort = selection_sort(y.copy(), len(y))
print(y)
print(sort)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

import numpy as np

from matplotlib import pyplot as plt

x = np.arange(1, 11, 1)

y = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

def selection_sort(data, n):

count = 0

axis = np.arange(1, 11, 1)

# ここからグラフ描画

# フォントの種類とサイズを設定する。

plt.rcParams['font.size'] = 14

plt.rcParams['font.family'] = 'Times New Roman'

# 目盛を内側にする。

plt.rcParams['xtick.direction'] = 'in'

plt.rcParams['ytick.direction'] = 'in'

# グラフの上下左右に目盛線を付ける。

fig = plt.figure()

ax1 = fig.add_subplot(111)

ax1.yaxis.set_ticks_position('both')

ax1.xaxis.set_ticks_position('both')

# 軸のラベルを設定する。

ax1.set_xlabel('x')

ax1.set_ylabel('y')

ax1.set_xticks(np.arange(1, 11, 1))

ax1.set_xlim(0, 11)

ax1.set_ylim(0, 14)

# データプロットの準備。

ax1.bar(axis, data, label='initial')

ax1.bar(0, 0, label='operated')

ax1.bar(0, 0, label='sorted')

plt.text(1, 12, 'count=' + str(count), fontsize=20)

# グラフを表示する。

fig.tight_layout()

fig.legend()

plt.savefig('fig_' + str("{:05}".format(count)) + '.png')

plt.close()

for i in range(n):

count += 1

j = np.argmin(data[i:]) + i

data[i], data[j] = data[j], data[i]

# ここからグラフ描画

# フォントの種類とサイズを設定する。

plt.rcParams['font.size'] = 14

plt.rcParams['font.family'] = 'Times New Roman'

# 目盛を内側にする。

plt.rcParams['xtick.direction'] = 'in'

plt.rcParams['ytick.direction'] = 'in'

# グラフの上下左右に目盛線を付ける。

fig = plt.figure()

ax1 = fig.add_subplot(111)

ax1.yaxis.set_ticks_position('both')

ax1.xaxis.set_ticks_position('both')

# 軸のラベルを設定する。

ax1.set_xlabel('x')

ax1.set_ylabel('y')

ax1.set_xticks(np.arange(1, 11, 1))

ax1.set_xlim(0, 11)

ax1.set_ylim(0, 14)

# データプロットの準備。

ax1.bar(axis, data, label='initial')

ax1.bar([axis[i], axis[j]], [data[i], data[j]], label='operated')

ax1.bar(axis[:i], data[:i], label='sorted')

plt.text(1, 12, 'count=' + str(count), fontsize=20)

# グラフを表示する。

fig.tight_layout()

fig.legend()

plt.savefig('fig_' + str("{:05}".format(count)) + '.png')

plt.close()

# ここからグラフ描画

# フォントの種類とサイズを設定する。

plt.rcParams['font.size'] = 14

plt.rcParams['font.family'] = 'Times New Roman'

# 目盛を内側にする。

plt.rcParams['xtick.direction'] = 'in'

plt.rcParams['ytick.direction'] = 'in'

# グラフの上下左右に目盛線を付ける。

fig = plt.figure()

ax1 = fig.add_subplot(111)

ax1.yaxis.set_ticks_position('both')

ax1.xaxis.set_ticks_position('both')

# 軸のラベルを設定する。

ax1.set_xlabel('x')

ax1.set_ylabel('y')

ax1.set_xticks(np.arange(1, 11, 1))

ax1.set_xlim(0, 11)

ax1.set_ylim(0, 14)

# データプロットの準備。

ax1.bar(0, 0, label='initial')

ax1.bar(0, 0, label='operated')

ax1.bar(axis, data, label='sorted')

plt.text(1, 12, 'count=' + str(count), fontsize=20)

# グラフを表示する。

fig.tight_layout()

fig.legend()

plt.savefig('fig_' + str("{:05}".format(count+1)) + '.png')

plt.close()

return data

sort = selection_sort(y.copy(), len(y))

print(y)

print(sort)

まとめ

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

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

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

選択ソートの概要

目標

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

処理回数とオーダー

検証のためのPythonコード

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

まとめ

コメントを残すコメントをキャンセル

最近の投稿

アーカイブ

カテゴリー

選択ソートの概要

目標

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

処理回数とオーダー

検証のためのPythonコード

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

まとめ

SNSでもご購読できます。

コメントを残す コメントをキャンセル

最近の投稿

アーカイブ

カテゴリー

コメントを残すコメントをキャンセル