＜アルゴリズムの基本⑧＞繰り返し処理（６）配列データの順位付け

今回は、複数のデータを大きい順に順位をつけるアルゴリズムについてまとめます。
データが格納されている配列と同じ要素数の別の配列を準備し、データが格納されている要素と同じ位置に順位を格納します。

目的および条件
擬似コード例
Pythonコード例
1. 実行結果
2. 処理速度について
まとめ

目的および条件

要素数Ｎの配列DATAの各要素を大きい順に順位を付け、順位を別の配列rankに格納する
条件
- 配列rankに対しては、データが格納されている要素と同じ位置に順位を格納する
- 配列DATAの各要素は、0〜100の整数値が格納されている

擬似コード例

まず、配列dataと同じ長さ(N)の新しい配列rankを準備し、あらかじめ全ての要素に1を代入しておきます。この配列rankは配列dataの各要素の大きさの順位を格納する為のものです。その後、配列dataのi番目の要素とそれ以外の全要素を比較し、i番目の要素より大きい場合は配列rankのi番目の要素に１を加算していく・・・という処理を配列dataの全要素（0≦i＜N）に対し繰り返します。
擬似コード例を示します。

Procedure RANKING(data, N):
    Define N length array 'rank' and set '1' into all elements
    i ← 0
    while i < N do
          j ← 0
          whild j < N do
              if data[i] < data[j] then 
                  rank[i] ← rank[i] + 1　
              end-if
              j ← j + 1
          end-while
          i ← i + 1
    end-while

Pythonコード例

Pythonコード例を示します。

>>> def rank(data):
...     rank = [1 for n in range(len(data))]
...     for i in range(len(data)):
...         for j in range(len(data)):
...             if data[i] < data[j]:
...                 rank[i] += 1
...     
...     return rank

実行結果

>>> data = [66, 18, 19, 32, 12, 87, 66, 13, 70, 51]
>>> rank(data)
[3, 8, 7, 6, 10, 1, 3, 9, 2, 5]

処理速度について

これまでと同じように処理速度について確認した結果を以下に示します。横軸はデータ数、縦軸は処理時間を示しており、両軸とも基底10の対数値としています。（コードはこちら）
グラフの傾きは約2ですので、このアルゴリズムの処理速度はたかだかn^2のオーダであることがわかります。n回の繰り返し処理が入れ子になって２回繰り返されている為だと思います。

配列の各要素を大きい順に順位付けする

まとめ

今回は、配列データの順位付けのアルゴリズムについてまとめました。処理速度は高々n^2のオーダとなりました。ソートアルゴリズムについてはもっと効率的なものがあると思いますので別途まとめたいと思います。

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