＜アルゴリズムの基本⑦＞ 繰り返し処理（５）　配列データの最大値・最小値を求める

今回は、配列データの最大値・最小値を求めるアルゴリズムについてまとめます。

目的

• 配列データの最大値・最小値を求める
• 前提条件：
  • 要素数がＮ個の配列に、0～100の範囲の整数が格納されているとする
  • 最大値を格納する変数ＭＡＸを定義し、初期値をデータの先頭の値とする
  • 最小値を格納する変数ＭＩＮを定義し、初期値をデータの先頭の値とする

擬似コード例

今回のアルゴリズムの擬似コード例を示します。まず、最大値（最小値）を格納する変数MAX（MIN）を準備し配列の一番最初のデータを初期値として設定します。その後、変数MAX（MIN)と各要素の値を比較して、条件にあった場合に変数MAX（MIN）を更新します。これを配列の全要素に対して繰り返し実施します。

Procedure MAX_CAL(DATA, N):
	MAX ← DATA[0]　
	idx ← 0
	while idx < N do
		if DATA[idx] > MAX
			MAX ← DATA[idx]
		end-if
    	idx ← idx +1
	end-while
	return MAX

Procedure MIN_CAL(DATA, N):
	min ← DATA[0]
	idx ← 0
	while idx < N do
		if DATA[idx] < MIN
			MIN ← DATA[idx]
		end-if
	idx ← idx +1
	end-whild
	return MIN

Pythonコード例

上記アルゴリズムのPythonコード例を示します。

>>> def cal_max(data, n):
...     val_max = data[0]
...     idx = 0
...     while idx < n:
...         if data[idx] > val_max:
...             val_max = data[idx]
...         idx += 1
...     
...     return val_max
... 
>>> def cal_min(data, n):
...     val_min = 999
...     idx = 0
...     while idx < n:
...         if data[idx] < val_min:
...             val_min = data[idx]
...         idx += 1
...     
...     return val_min

出力結果
>>> data = [89, 27, 29, 58, 92, 98, 73, 52, 2, 51]
>>> cal_max(data, len(data))
98
>>> cal_min(data, len(data))
2

処理速度の検証

このアルゴリズムはたかだかnのオーダなので、処理時間はデータ量に比例して増加します。実験結果を以下に示します。前回までと同様に横軸はデータ数を基底10の対数値、縦軸は処理時間（の対数値）です。（コード例はこちら）

まとめ

今回は配列データの最大値、最小値を求めるアルゴリズムをまとめました。

（参考文献：杉浦賢、図解でかんたんアルゴリズム　情報処理のかなめとなる考え方が手に取るようにわかる、Softbank Creative）