2020-12-222020-12-22IT

【Python】Selection Sortを学びながらPythonの基礎を身につける記事

当ページのリンクには広告が含まれています。

✓目次

Selection Sortとは
Pythonの基礎について
- [Python基礎]range関数
Selection Sortのコーディング
まとめ

Selection Sortとは

ソートアルゴリズムの一種です。

データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す（厳密には、データ列の最後より1つ手前までの繰り返しでよい。一つ前まで交換済みであれば、最後（残り）は必ず最大値になるからである）。

選択ソート - Wikipedia

Pythonの基礎について

Selection Sortを実装するために必要な知識は以下の記事にもまとめていますので参照ください。Bubble Sortの学習もしていただくと良いと思います。

ここでは、追加で学んでおくべきPythonの基礎について整理します。

[Python基礎]range関数

例えば、1から9までの数字を表示しなさい、と言われた時に、num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]とリストを作って、これを表示するコードを書いてもいいですが、面倒ですよね。

こんな時に、pythonのrange関数が役に立ちます。

for i in range(10):
    print(i)

# 0
# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8
# 9

では、リストの3番目から表示してほしい、という場合はどうするでしょうか？その場合は、以下のような書き方をすればOKです。

for i in range(3, 10):
    print(i)

# 3
# 4
# 5
# 6
# 7
# 8
# 9

では、2つ飛ばしで値を表示してほしい、という場合はどうでしょうか？
これも簡単で、3つめの引数に2と入れるだけです。

for i in range(3, 10, 2):
    print(i)

# 3
# 5
# 7
# 9

これを応用して、10回’hello’という文字列を出力する事もできます。ここではついでにindex番号も出力しています。

for i in range(10):
    print(i, "hello!")

# 0 hello!
# 1 hello!
# 2 hello!
# 3 hello!
# 4 hello!
# 5 hello!
# 6 hello!
# 7 hello!
# 8 hello!
# 9 hello!

また、for i in range(10)としてforループで10回ループを回した後、「もうiは不要ですよ」というのを明示的に示すために、_を用いたりします。

forループの中でもiを使う必要もありません。index番号を使わない場合は、このような書き方をしてもOKです。

for _ in range(10):
    print("hello!")

# hello!
# hello!
# hello!
# hello!
# hello!
# hello!
# hello!
# hello!
# hello!
# hello!

Selection Sortのコーディング

基本的な思考の流れは、Bubble Sortの時と同じです。

まずは、Bubble Sortと同様、関数宣言します。

1
2
3

from typing import List

def selection_sort(numbers: List[int]) -> List[int]:

次に、リストの定義と定義した関数にリストを渡し、range関数とlenメソッドを用いて、リストのindexをprintしてみます。

from typing import List

def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        print(i)
    
    
if __name__ == '__main__':
    nums = [2, 5, 7, 6, 7, 1,]
    selection_sort(nums)

# 0
# 1
# 2
# 3
# 4
# 5

Selection Sortは、先頭の数字を取り出し、前から順番に数字の大小を比較し、もし先頭の数字のほうが大きかったら入れ替える、という処理を繰り返します。

まず、最初の数字のindexを取り出すために、min_index = iを追記します。printは削除します。

from typing import List

def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        min_index = i
 


   
if __name__ == '__main__':
    nums = [2, 5, 7, 6, 7, 1,]
    selection_sort(nums)

forループで、先頭のindex番号を一つ先のindex番号から最後のindex番号まで、先頭の数字とそれ以降の数字を比較する処理を記述します。

from typing import List

def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        min_index = i
        for j in range(i + 1, len(numbers)):      


   
if __name__ == '__main__':
    nums = [2, 5, 7, 6, 7, 1,]
    selection_sort(nums)

もし、先頭のindex番号に含まれた数字のほうが大きかった場合は、数字を入れ替えるので、以下のように記載します。そして最後にreturnでリストを返却します。結果をprintするとうまくソートされていることがわかると思います。

from typing import List

def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        min_index = i
        for j in range(i + 1, len(numbers)):          
            if numbers[min_index] > numbers[j]:
                numbers[min_index], numbers[j] = numbers[j], numbers[min_index]
                      
    return numbers


   
if __name__ == '__main__':
    nums = [2, 5, 7, 6, 7, 1,]
    print(selection_sort(nums))
# -> [1, 2, 5, 6, 7, 7]

最後に、randomを用いて大きめの数字でも試してみるとうまくソートできていることが確認できると思います。

from typing import List

def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        min_index = i
        for j in range(i + 1, len(numbers)):          
            if numbers[min_index] > numbers[j]:
                numbers[min_index], numbers[j] = numbers[j], numbers[min_index]
                      
    return numbers


if __name__ == '__main__':
    import random
    nums = [random.randint(0, 1000) for _ in range(10)]
    print(selection_sort(nums))
# -> [66, 167, 205, 242, 294, 319, 339, 629, 913, 976]

別海としては、min_index = jと記述して、数値比較の際に小さい方の数のindex番号を入れ替える処理をすることを明示的に示すコードの書き方もあります。

from typing import List

def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        min_index = i
        for j in range(i + 1, len(numbers)):
            if numbers[min_index] > numbers[j]:
                min_index = j
        numbers[i], numbers[min_index] = numbers[min_index], numbers[i]
    return numbers
    
    
if __name__ == '__main__':
    import random
    nums = [random.randint(0, 1000) for _ in range(10)]
    print(selection_sort(nums))
# -> [8, 9, 51, 268, 322, 413, 599, 780, 858, 996]