クイックソート・アルゴリズムにおける、いくつかの話題

ーーーーーーーー

ピボット（pivot）の選択

    http://www.flint.jp/blog/?entry=109
        flint blog: 「選択アルゴリズム」と「中央値の中央値」

ーーーーーーーー

番兵（sentinel）
	条件判定の数を減らすために置いたダミーデータ

（例）
配列内の特定のデータ（の位置）を探す。ただし、特定データが存在しない場合もある。
	配列{5,1,4,2,9}の内から3を探す。
	→ 配列の末尾に3を仮に置いておく {5,1,4,2,9,3}
	→ 探したものが配列の末尾にあった場合には、元の配列には存在していなかったことが分かる。

【改良前】
	int[] x = new int[10];
	// x[] へデータを入力し、データ数をnとする。
	int k = 3; // 探すべきデータ
	for(i = 0, i < n; i++) {
	    if (x[i] == k)	// i 番目に見つかったら、
	        break;    	// break文でループから抜け出す。
	}
	if(i < n) {
	    // i 番目に見つかった
	} else {
	    // 見つからなかった。
	}

【改良中】
	int[] x = new int[10];
	// x[] へデータを入力し、データ数をnとする。
	int k = 3; // 探すべきデータ
	for(i = 0, i < n && x[i] != k; i++) {} // ループ本体の処理を継続判定へ移動させる
					// ループ本体は空文{}、&& は論理積をとる演算子
	if(i < n) {
	    // i 番目に見つかった
	} else {
	    // 見つからなかった。
	}

【改良後】
	int[] x = new int[10];
	// x[] へデータを入力し、データ数をnとする。
	int k = 3; // 探すべきデータ k を番兵として、x[] の最後に追加しておく
	for(i = 0, x[i] != k; i++) {} // 継続条件判定のひとつ（i < n）が不用になる
	if(i < n) {
	    // i 番目に見つかった
	} else {
	    // 見つからなかった。
	}

ーーーーーーーー

アルゴリズムの評価（計算量）

	http://home.ipc.gunma-ct.ac.jp/~yanaka/20180525/20180525_4_complexity.txt

○計算量（complexity 直訳すると複雑性）

	時間計算量：処理の回数→実行時間
	領域計算量：作業用データの量→記憶容量

	問題（データ）のサイズｎの関数で表現する
		例．ｎの二乗
		　　log(n)

	最悪値（○）
	最良値
	平均値（○）

○時間計算量

（例）バブルソート（ソーティングのアルゴリズムのひとつ）の時間計算量

問題のサイズをｎとして、
比較の回数を調べる。
交換の回数を調べる。

外側のループは(n-1)回だけ繰り返す。
内側のループは、
　　外側ループの１回目のとき、(n-1)回だけ繰り返し、
　　　　　　　　２　　〃　　、(n-2)　　　〃
　　　　　　　　：
　　　　　　　　：
　　　　　　　　n-1 　〃　　、１回だけ繰り返す。
したがって、比較の回数の合計は、
　　(n-1) + (n-2) + … + 2 + 1 = n(n-1)/2
ただし、
係数の1/2などは、計算機のクロックの違いなどにより、
無視することができ、
ｎの１次の項は２次の項に比べて小さいので無視できる。
結局、「ｎの二乗に比例する計算量である」といえる。
これを、
「O(nの二乗)」と書いて「オーダー、ｎの二乗」という。

クイックソートの平均の時間計算量は、O(n・log(n))。

バケットーソートの時間計算量は、O(n + m)。
（ここに、ｎはデータの個数、ｍはデータが取り得る値の場合の数。）

○ランダウの記号
	https://ja.wikipedia.org/wiki/ランダウの記号
		ランダウの記号 - Wikipedia

○各種のソートアルゴリズムの計算量の比較

データサイズ	バブル		クイック	バケット
	ｎ	ｎ・ｎ		ｎlogｎ		ｎ（＋ｍ）
	10	   100	
       100	 10000
      1024	約100万		  10240		   1024

○理論的にソーティングの時間計算量を見積もる。

ｎ個のデータの並びのとりうる場合の数はいくつか？
　　n(n-1)(n-2)…3・2・1 = n!
ｐ：あるデータの並びが実現する確率。
　　p = 1/(n!)

情報量 I の式
	 I = - log(p)
	   = log(n!)
	　　≒ n・log(n)	   

ーーーーーーーー