Javaで学ぶアルゴリズム 第3弾：順位付け

#Javaで学ぶアルゴリズム < 順位付け >

##はじめに
Javaは授業で触れただけで全くの初心者であり，何もわかっていない．なので，基本的なアルゴリズムをJavaで実装し，アルゴリズムの理解を深めるとともに，Javaにも慣れていきたい．
その第3弾として順位付けを扱う．

##順位付け
順位付けには様々な方法がある．また，数値であれば，高い順なのか低い順なのかという話も出てくる．ここでは3つの例を取り上げて，順位付けについての理解を深める．

##実装
例の説明を行った後に，Javaで実装したソースコードとそのときの出力を示し，考察を記述する．

####例①：非常に単純な順位付け
おそらく誰もがはじめに浮かぶような方法である．その説明を以下に図として示す．

いま，61点の人の順位を求めている．順位は1~ということであるから，自分よりも大きな値がなければ1位になる．つまり，初期値は1となる．次にソースコードとそのときの出力を示すが，その中でほかのアルゴリズムが必要になってくることが分かってくる．

#####ソースコード

ranking1.java

//2020/12/14
//@Yuya Shimizu
//---------------------------
//*		順位付け（単純版）	*
//---------------------------

import java.awt.*;
import java.awt.event.*;

//パネルの設定
class ranking_Panel1 extends Panel{
	//順位付けを行い，その結果を描画する関数
	public void paint(Graphics g){
		final int Num = 10;		//データ数
		int[] a = {56, 25, 67, 88, 100, 61, 55, 67, 76, 56};	//データリスト
		int[] ranking = new int[Num];	//ランクを格納するリストを生成
		int i, j;
		
		for (i=0; i<Num; i++){
			ranking[i] = 1;		//初期値1
			for(j=0; j<Num; j++){
				/* 各データと比較する（すべて） */
				if (a[j] > a[i])
					/* 自分よりも大きければ，+1（順位を下げていく） */
					ranking[i] ++;
			}
		}
		//描画
		g.drawString("得点　順位", 10, 20);
		for (i=0; i<Num; i++){
			g.drawString("" + a[i], 10, i*20+40);
			g.drawString("" + ranking[i], 50, i*20+40);
		}
	}
}

//フレームの設定
class ranking_Frame1 extends Frame{
	public ranking_Frame1(){
		setSize(200, 300);//200×300の大きさでフレームを作成
		//×ボタンを押したら終了
		addWindowListener(new WindowAdapter(){
			public void windowClosing(WindowEvent e){
				System.exit(0);
			}
		});
		Panel p=new ranking_Panel1();//パネルオブジェクトpに先ほど設定したパネルを指定
		add(p);	//フレームにそのパネルを貼り付け
	}
}

//クラス
public class ranking1{
	//メイン関数
	public static void main(String[] args){
		Frame w=new ranking_Frame1();
		w.show();
	}
}

#####出力

上の説明であったように，同じ点数は同じ順位になっている．また，ソースコードの中で，データと比較するところがあるが，ここでは毎回全データとの比較を行っており，無駄な作業が入っている．データが$n$個の場合，繰り返し数が$n^2$となってしまう．そのため，データ数が増える場合には，好ましくない．よって，繰り返し回数を減らせるようなアルゴリズムが求められる．

#####例②：繰り返し回数を減らす順位付け（正の数）
同じ結果をもたらす順位付けだが，その方法を工夫することで，繰り返し回数を減らすことができる．先ほどと同様にして，図にて以下にその方法を示す．

ある大きさの配列を用意する．この大きさは点数の範囲を網羅していればどのような大きさでもアルゴリズム上，動くはずである．ここでは，単純化のため100の大きさにしている．101は余分に足している．最終的な結果が自分の右隣に現れるため，今回100というデータはあるので，余分に101というインデックスの配列が必要であった．以下にソースコードとそのときの出力を示す．

#####ソースコード

ranking2.java

//2020/12/14
//@Yuya Shimizu
//---------------------------
//*		順位付け（改良版）	*
//---------------------------

import java.awt.*;
import java.awt.event.*;

//パネルの設定
class ranking_Panel2 extends Panel{
	//順位付けを行い，その結果を描画する関数
	public void paint(Graphics g){
		final int Num = 10, Max = 100, Min = 0;	//データ数, 最大インデックス, 最小インデックス
		int[] a = {56, 25, 67, 88, 100, 61, 55, 67, 76, 56};	//データリスト
		int[] ranking = new int[Max+2];	//ランクを格納するリストをMinからMaxまでと余分に1つの大きさで生成
		int i;
		
		//全ランクを0で初期化
		for (i=0; i<=Max; i++)
			ranking[i] = 0;
		
		//点数をインデックスとして+1
		for (i=0; i<Num; i++)
			ranking[a[i]]++;
		
		ranking[Max+1] = 1;	//余分な配列（右端）を1で初期化
		
		//右隣りの数字を足す
		for (i=Max; i>=Min; i--)
			ranking[i] += ranking[i+1];
		
		g.drawString("得点　順位", 10, 20);
		for (i=0; i<Num; i++){
			g.drawString("" + a[i], 10, i*20+40);
			g.drawString("" + ranking[a[i]+1], 50, i*20+40);	//自分の右隣にあるランクが自分のランク
		}
	}
}

//フレームの設定
class ranking_Frame2 extends Frame{
	public ranking_Frame2(){
		setSize(200, 300);//200×300の大きさでフレームを作成
		//×ボタンを押したら終了
		addWindowListener(new WindowAdapter(){
			public void windowClosing(WindowEvent e){
				System.exit(0);
			}
		});
		Panel p=new ranking_Panel2();//パネルオブジェクトpに先ほど設定したパネルを指定
		add(p);	//フレームにそのパネルを貼り付け
	}
}

//クラス
public class ranking2{
	//メイン関数
	public static void main(String[] args){
		Frame w=new ranking_Frame2();
		w.show();
	}
}

#####出力

同様の結果が得られたことが分かる．この程度のデータ数であるため，実際の処理時間の違いを体験することができなかったが，ソースコードを見ても分かるように，理論上はデータ数$n$，データ範囲$m$であれば，$n+m$回の繰り返しで順位付けができる．

####例③：繰り返し回数を減らす順位付け（負の数）
いま，負の数を含むデータにおいて，小さいもの順に順位付けを行いたいとする．基本的には，先ほど例②で示した方法の逆すなわち，左から行えば実現可能である．ただし，javaでは負の値をインデックスに指定できないので，Bias（かたより）を使って，正の数の範囲でインデックスが取れるように少しずらすという作業が必要となってくる．それ以外の方法は先ほどと同じである．以下にソースコードとそのときの出力を示す．

#####ソースコード

ranking3.java

//2020/12/14
//@Yuya Shimizu
//---------------------------
//*		順位付け（負の値）	*
//---------------------------

import java.awt.*;
import java.awt.event.*;

//パネルの設定
class ranking_Panel3 extends Panel{
	//順位付けを行い，その結果を描画する関数
	public void paint(Graphics g){
		final int Num = 10, Max = 36, Min = -20, Bias = 1-Min; //最小値を配列要素の1に対応させる
		int[] a = {-3, 2, 3, -1, -2, -6, 2, -1, 1, 5};
		int[] ranking = new int[Max+Bias+1];
		int i;
		
		//全ランクを0で初期化
		for (i=Min+Bias; i<=Max+Bias; i++)
			ranking[i] = 0;
		
		//点数とバイアスをインデックスとして+1
		for (i=0; i<Num; i++)
			ranking[a[i]+Bias]++;
		
		ranking[Min+Bias] = 1;	//Min+Bias（いまは1）のインデックスのランクを1とする
		
		//左隣りの数字を足す
		for (i=Min+Bias; i<Max+Bias; i++)
			ranking[i] += ranking[i-1];
		
		g.drawString("得点　順位", 10, 20);
		for (i=0; i<Num; i++){
			g.drawString("" + a[i], 10, i*20+40);
			g.drawString("" + ranking[a[i]+Bias-1], 50, i*20+40);
		}
	}
}

//フレームの設定
class ranking_Frame3 extends Frame{
	public ranking_Frame3(){
		setSize(200, 300);//200×300の大きさでフレームを作成
		//×ボタンを押したら終了
		addWindowListener(new WindowAdapter(){
			public void windowClosing(WindowEvent e){
				System.exit(0);
			}
		});
		Panel p=new ranking_Panel3();//パネルオブジェクトpに先ほど設定したパネルを指定
		add(p);	//フレームにそのパネルを貼り付け
	}
}

//クラス
public class ranking3{
	//メイン関数
	public static void main(String[] args){
		Frame w=new ranking_Frame3();
		w.show();
	}
}

#####出力

うまく順位付けされていることが分かる．

##感想
負の値を直接用いることのできない場合にバイアスをかけるということを今までやったことがなかった．少しプログラムは見づらくなるが，発想としては覚えていても損はないと思った．また，あえてリストを用意することでうまく処理時間の短縮を行う術も得た．

##参考文献
Javaによるはじめてのアルゴリズム入門　　河西 朝雄　著　技術評論社