単純選択法(選択ソート)について
単純選択法は、以下のような手順で並べ替えていくアルゴリズムです。
データ列の中から一番小さい値を選択し、それを0番目の要素と交換する。
次に、残りのデータ列の中から一番小さい値を選択し、それを1番目の要素と交換する。
これをデータの最後まで繰り返し行う事により、先頭から順に並べ替えていきます。
一番小さい値を選択しながら整列していくので、単純選択法は選択ソート(selection sort)と呼ばれています。
選択ソートはバブルソートと比較回数は同じですが、各ループでの交換回数が最大１回となっているので選択ソートの方が高速です。
単純選択法のイメージ
以下の図は単純選択法を使ってデータを小さい順(昇順)に並べ替える様子のイメージです。
[単純選択法のイメージ]
サンプルコード
単純選択法のアルゴリズムを以下のプログラミング言語で紹介します。
- Tcl
- Python
サンプルコードについて
各プログラミング言語の基本的な制御構造とデータ構造を使って記述しています。
必要であれば、for, foreach、リスト、配列などに書き換えたり、関数化を行って練習してください。
Tcl
[サンプル：selection-sort.tcl]
#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"
# 単純選択法(selection sort:選択ソート)
# arr : 数値リスト
# n : 要素数
# i,j : 要素のindex
# tmp : 交換用
# indexMin : 最小値の位置
array set arr {0 40 1 10 2 30 3 50 4 20}
set n [array size arr]
set i 0 ;# 外側のループカウンタ。
while {$i < $n - 1} {
set indexMin $i ;# i番目を暫定で最小値とする。
set j [expr $i + 1] ;# 内側のループカウンタ。
# 最小値の位置を探す。
# このループでindexMinには未整列中の最小値の位置がセットされる。
while {$j < $n} {
if {$arr($j) < $arr($indexMin)} {
set indexMin $j
}
incr j
}
# 最小値とi番目の値を交換する。
set tmp $arr($i)
set arr($i) $arr($indexMin)
set arr($indexMin) $tmp
incr i
}
parray arr
[実行例]
$ ./selection-sort.tcl arr(0) = 10 arr(1) = 20 arr(2) = 30 arr(3) = 40 arr(4) = 50
Python
[サンプル：selection-sort.py]
#!/usr/bin/env python3
# 単純選択法(selection sort:選択ソート)
# arr : 数値リスト
# n : 要素数
# i,j : 要素のindex
# tmp : 交換用
# indexMin : 最小値の位置
arr = [40, 10, 30, 50, 20]
print(arr)
n = len(arr) # 要素数
i = 0 # 外側のループカウンタ。
while i < n-1:
indexMin = i # i番目を暫定で最小値とする。
j = i+1 # 内側のループカウンタ。
# 最小値の位置を探す。
# このループでindexMinには未整列中の最小値の位置がセットされる。
while j < n:
if arr[j] < arr[indexMin]:
indexMin = j
j += 1
# 最小値とi番目の値を交換する。
tmp = arr[i]
arr[i] = arr[indexMin]
arr[indexMin] = tmp
i += 1
print(arr)
[実行例]
$ ./selection-sort.py [40, 10, 30, 50, 20] [10, 20, 30, 40, 50]
コメント