アルゴリズム(順位付け)

Java

お題

5点満点のテストがある。これを9人が受けたときの結果に対して順位付けをせよ。なお、9人の点数はランダムとする。

実行例

[実行例1]
***テストの点数***
[4, 1, 3, 5, 0, 0, 4, 2, 2]
***順位***
[2, 7, 4, 1, 8, 8, 2, 5, 5]

[実行例2]
***テストの点数***
[0, 0, 4, 5, 0, 1, 0, 5, 5]
***順位***
[6, 6, 4, 1, 6, 5, 6, 1, 1]

点数が同じ人は同一の順位になっていることに着目してもらい。

考え方

①すべてのデータに対して、それよりも点数の多い人の人数を数える(わかりやすさ優先)

これがもっとも単純な考え方だ。1つのデータとすべてのデータを比較し、そのデータよりも大きい人の数を数える方法だ。

import java.util.Arrays;
import java.util.Random;

public class Main {
	public static void main(String[] args) {
		Random rand = new Random();
		//点数用の配列
		int[] data = new int[9];
		//ランダムな点数を入れる
		for(int i=0;i<data.length;i++) {
			data[i] = rand.nextInt(10);
		}
		//表示
		System.out.println("***テストの点数***");
		System.out.println(Arrays.toString(data));
		
		//結果用の配列
		int[] results = new int[data.length];
		//とりあえず全員1位にしておく
		for(int i=0;i<results.length;i++) {
			results[i]=1;
		}
		//最初の人から最後の人まで回すループ
		for(int i=0;i<data.length;i++) {
			//すべてのデータと比較するためのループ
			for(int j=0;j<data.length;j++) {
				//もし大きい点数があったら
				if(data[i] < data[j]){
					//順位が一つ下がる
					results[i]++;
				}
			}
		}
		//表示
		System.out.println("***順位***");
		System.out.println(Arrays.toString(results));
	}
}

②基準点の人ととの比較を繰り返し、その都度順位を変動させていく(効率優先)

先程の方法はわかりやすのだが効率が悪い。効率の良い方法を考えみよう。
先程は、同じ人同士の比較を何度も繰り返すことになるのだが、以下の方法だと同じ人との比較は1度きりとなる。

import java.util.Arrays;
import java.util.Random;

public class Main {
	public static void main(String[] args) {
		Random rand = new Random();
		//点数用の配列
		int[] data = new int[9];
		//ランダムな点数を入れる
		for(int i=0;i<data.length;i++) {
			data[i] = rand.nextInt(6);
		}
		//表示
		System.out.println("***テストの点数***");
		System.out.println(Arrays.toString(data));

		//結果用の配列
		int[] results = new int[data.length];
		//とりあえず全員1位にしておく
		for(int i=0;i<results.length;i++) {
			results[i]=1;
		}
		//最初の人から最後の1人手前まで回すループ(基準点)
		for(int i=0;i<data.length-1;i++) {
			//基準点以降に対して回るループ
			for(int j=i+1;j<data.length;j++) {
				//もし基準点の点数が低かったら
				if(data[i] < data[j]){
					//基準点の順位が一つ下がる
					results[i]++;
				//基準点のほうが大きかったら
				}else if(data[i] > data[j]){
					//比較対象の順位を下げる
					results[j]++;
				}
			}
		}
		//表示
		System.out.println("***順位***");
		System.out.println(Arrays.toString(results));
	}
}

最初の方法は9*9の81回比較しているのに対し、この方法だと
8+7+6+5+4+3+2+1 =36回の比較で済んでいる。

データ数が多い場合などはこの計算量の差が大きくなってくるので、こちらの方法を用いたほうがよいだろう。

Java
スポンサーリンク
シェアする
mjpurinをフォローする
ジョイタスネット

コメント

タイトルとURLをコピーしました