【アルゴリズムの勉強】Pythonで選択ソートを書いてみた

学習エントリ。

Pythonで選択ソートを実装する。

選択ソートってなんぞ

選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。
このアルゴリズムを改良したソート法として、ヒープソートが挙げられる。

選択ソート - Wikipedia

example_list = [5,2,10,1,18,3,7,4]
ASC, DESC = 1, 2

def selectSort(list,order):
    for i in xrange(0,len(list)):
        if order == ASC:
            min = list[i]
            num = i
            for j in xrange(num + 1,len(list)):
                if min > list[j]:
                    min = list[j]
                    num = j
                if num == i:
                    continue
                list[i],list[num] = list[num],list[i]
        elif order == DESC:
            max = list[i]
            num = i
            for j in xrange(num + 1,len(list)):
                if max < list[j]:
                    max = list[j]
                    num = j
                if num == i:
                    continue
                list[i],list[num] = list[num],list[i]
    return list


print("ASC is...")
print(selectSort(example_list,ASC)) #[1, 2, 3, 4, 5, 7, 10, 18]
print("DESC is...")
print(selectSort(example_list,DESC)) #[18, 10, 7, 5, 4, 3, 2, 1]

ポイントっぽいところ

・1. 順番にlistを取り出し、最初の値を比較対象とする
・2. 最小値or最大値を仮に比較対象とする
・3. 比較対象とそれ以降の要素（list[j]）を一つ一つ比べ、最小値or最大値を求める
・4. 求めた最大値or最小値と比較対象をスワップ