選択ソート
Python での実装例を示す。 In-place 版の実装は以下の通り。
非 in-place 版は上記に配列のコピーを渡すことで実現できるが、例えば以下のように直接実装することもできる。
初期データ: 8 4 3 7 6 5 2 1
太字はソート完了した部分
1 4 3 7 6 5 2 8 (1回目のループ終了時)
1 2 3 7 6 5 4 8 (2回目のループ終了時)
1 2 3 7 6 5 4 8 (3回目のループ終了時)
1 2 3 4 6 5 7 8 (4回目のループ終了時)
1 2 3 4 5 6 7 8 (5回目のループ終了時) この例では、一見して、この時点で既にソート完了したとわかる。しかしデータが多数の場合はそうはいかないし、アルゴリズムで「一見して」ソート完了か否か判断できない。アルゴリズム通りに最後まで処理する必要がある。
1 2 3 4 5 6 7 8 (6回目のループ終了時)
1 2 3 4 5 6 7 8 (7回目のループ終了時)