ソートアルゴリズム：選択ソートとは

ソートアルゴリズムとは

ソートアルゴリズムの意味は、ソートとアルゴリズムの意味を理解すれば分かります。

ソートとは、ある規則に則って、データを並び替えることを指します。

アルゴリズムは、ある課題に対してどのように解決するのかその方法や考え方を指します。

したがって、ソートアルゴリズムとは、バラバラのデータを規則的にどのように並び替えるのかという考え方のことです。

その中の１つである選択ソートを紹介します。

今回は、バラバラの数値データを昇順に並び替えることを考えます。

選択ソートとは

選択ソートとは、バラバラの数値データから最小値(最大値)を選択して、ソートしていく方法です。

バブルソートは、隣の値を比較して交換するのに対して、選択ソートは、最小値(最大値)を選択して交換するので、交換回数が少なくて済みます。

プログラムで書いてみよう

Pythonで選択ソートのプログラムを書いてみようと思います。

最小値を選択してソートする方法のプログラムを書きます。

最初、要素番号０を暫定の最小値として、１つずつ値を比較します。

比較して、暫定の最小の要素より小さい要素があれば、暫定の最小を交代します。

データの最後まで比較し終えたとき、暫定の最小の要素は、そのデータの中での最小の要素になります。

def select(data):
    length = len(data)
    min=0
    for i in range(1,length):
        if data[min] > data[i]:
            min = i
    data[0],data[min] = data[min],data[0]
    return data

data=[5,4,3,2,1]
print(data)
cdata=select(data)
print(cdata)

実行結果

[5, 4, 3, 2, 1]
[1, 4, 3, 2, 5]

これを、繰り返していきます。繰り返しとともに１つずつ要素番号が決まるため、比較する範囲は、どんどん狭くなります。

def select(data):
    length = len(data)
    for i in range(length):
        min=i
        for j in range(min+1,length):
            if data[min] > data[j]:
                min = j
        data[i],data[min] = data[min],data[i]
    return data

data=[5,4,3,2,1]
print(data)
cdata=select(data)
print(cdata)

実行結果

[5, 4, 3, 2, 1]
[1, 2, 3, 4, 5]

上手く昇順に並び替えることができたようです。

他にもソートアルゴリズムがあるので、紹介できればと思います。