selectionSort

タグ: ,

引数に指定された配列を選択ソートで並び替えます。

構文
selectionSort( Var array )
引数
array
ソートする数値を格納した配列。参照引数。
戻値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE selectionSort(Var array[])
	FOR n = 0 TO UBound(array)
		DIM mini = n
		FOR m = n + 1 TO UBound(array)
			IFB array[m] < array[mini] THEN
				mini = m
			ENDIF
		NEXT
		swap(array[n], array[mini])
	NEXT
FEND

//////////////////////////////////////////////////
// 【引数】
//   a : 変数bと交換する値。参照引数。 
//   b : 変数aと交換する値。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
	DIM tmp = a
	a = b
	b = tmp
FEND

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND

選択ソート

選択ソートは、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えを行うことでソートします。

アルゴリズム

  1. データ列の中で一番小さい値を探し、1番目の要素と交換する。
  2. 次に2番目以降のデータ列の中で一番小さい値を探し、2番目の要素と交換する。
  3. これをデータ列の最後まで繰り返す。
最悪計算時間 \(O(n^{2})\)
最良計算時間 \(O(n^{2})\)
平均計算時間 \(O(n^{2})\)