選択ソートとは？ソートアルゴリズム解説その２

1 選択ソートとは？
2 具体的なアルゴリズム
3 Pythonでの実装例

選択ソートとは？

整列アルゴリズムの1つで、
バラバラのデータの中から
一番小さい値のデータを選択して先頭に追加、
二番目に小さい値を選択して二番目に追加
三番目に小さい値を選択して三番目に追加・・
の操作を繰り返して、全てのデータを順番に並べ替える方法です。

上記の場合は小さいデータから選択して並べ替えていますが、
大きいデータから選択して末尾に追加していく場合でも選択ソートと呼びます。

人間が直感的に並べ替えを行う場合に近い方法と言われています。

具体的なアルゴリズム

選択ソートのアルゴリズムは以下です。

①データ全体を未整列データとする
②未整列データを左端から右端まで走査し、最小のデータを決定する
③最小のデータと未整列データの先頭の値を入れ替える
④未整列データの先頭を整列済みデータとする
⑤手順②に戻って操作を繰り返す。全てが整列済みデータになったら完了。

データ数5つで、
上記手順で整列する例を動画で見てみましょう。

Pythonでの実装例

以下、Pythonでの実装例です

import random
import sys

arrayLength = 20
arrayList = list(range(1,arrayLength+1))
arrayList = random.sample(arrayList, len(arrayList))
coolCount = 1

#######################
#配列の指定された範囲の中から最小値をもつインデックスを返す
#######################
def FindMinIndex(array_list, str_idx, end_idx):
    minValue = sys.maxsize
    minIdx = 0
    oldMinIdx = 0 #描画用

    for i in range(str_idx, end_idx, 1):
        if array_list[i] < minValue:
            minValue = array_list[i]
            oldMinIdx = minIdx
            minIdx = i

    return minIdx

#######################
#
#  メイン処理
#
#######################

idx = 0

while coolCount < arrayLength:
    # $idx～$array_listの末尾まで最小値を探す
    minIdx = FindMinIndex(arrayList, idx, arrayLength)

    # $idxと$minIdxの要素を交換
    arrayList[idx], arrayList[minIdx] = arrayList[minIdx], arrayList[idx]

    print(arrayList)
    idx += 1
    coolCount += 1