<アルゴリズムの基本⑦> 繰り返し処理(5) 配列データの最大値・最小値を求める

アルゴリズム その他

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

目的

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

擬似コード例

今回のアルゴリズムの擬似コード例を示します。まず、最大値(最小値)を格納する変数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)

Learn more...

書籍でもう少し詳しく学びたい場合はこちらもどうぞ。筆者もかなり参考にさせてもらっています!

シェアする
ひびきをフォローする
Hbk project