MIT Open course: Introduction to Algorithmsのまとめ(4~6回)

勉強の続き。

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

第四回
◯クイックソート
・ある数(ピボット)をソートされた位置に順番に移動させる方法
・入力に依存しないように、変形版としてランダムクイックソートがある(ピボットをランダムに選択)
・分析(証明)
計算時間,E[T(n)]=nlogn

第五回
◯ソートアルゴリズム速度まとめ
・クイックソート O(nlogn)
・ヒープソート O(nlogn)
・マージソート O(nlogn)
・Insertion Sort O(n^2)

◯比較ソートモデル(Comparison Sorting model)
・数列の順番を決定するのに比較のみを用いるモデル
・上の4つはいずれもこのモデルに属する
・決定木で書ける(ノードは比較式、葉は答え)
・nが大きくなると、木は巨大になるので書けない。(全並び替えが木ある必要がある)
・このモデルのもとでは、最速でもnlogn!!!←(葉の数)>=n!, (葉の数)<=2^h, worst case計算時間はh(木の高さ)

◯Counting sort
・全要素を含むバッファを別に用意しといて、各要素が何回ずつ出現したかを数える
・線形計算時間

◯Radix sort
・小さい桁から順番にcounting sortしていく
・線形計算時間
・要素が限定されているときに有効(ビット列とか)

第六回
◯Order Statistics n
・この配列からk番目に小さい要素を見つける
・naive→ソートしてk番目 O(nlogn)

◯Rand-select
・クイックソートのようにピボットを選ぶが、kが含まれるであろう側のグループのみしか考えない　O(n)
・unlucky case、例えばピボットを選んで1とn-2にわかれた場合、T(n)=T(n-1)+Θ(n)でO(n^2)→どうにかならないか?

◯no-name Rand-select
・ピボットを工夫して選択(二つのサイズがともに1/4以上になるように)
1.5個の要素をもつ[n/5]個のグループにわけ、グループごとにmedianを見つける
2.medianのmedianを見つける
3.それをpivotにしてrand-select
・必見!ピボットの選択方法が神がかっている。なぜ5個か

QuickSort.java

public class QuickSort extends Sort{

	public int[] sort(int[] A)
	{
		sort(A,0,A.length - 1);
		return A;
	}
	public void sort(int[] A,int p, int q)
	{
		if( p < q)
		{
			int r = partition(A,p,q);
			sort(A,p,r-1);
			sort(A,r + 1,q);
		}
	}
	
	public int partition(int[] A, int p, int q){
		
		int i=p;
		int pivot = A[p];
		for(int k = p+1;k<= q;k++){
			if(A[k] < pivot)
			{
				int temp = A[i+1];
				A[i+1] = A[k];
				A[k] = temp;
				i++;
			}
		}
		int temp = A[i];
	http://d.hatena.ne.jp/J0__0K/port	A[i] = A[p];
		A[p] = temp;
		
		return i;
	}
	
	public int[] combine(int[] subA, int[] subB){
		int m = subA.length;
		int n = subB.length;
		int[] array = new int[m + n];
		
		System.arraycopy(subA, 0, array, 0, m);
		System.arraycopy(subB, 0, array, m, n);
		return array;
	}
}

CountingSort.java

import java.util.Arrays;

public class CountingSort extends Sort{
	public int[] sort(int[] A)
	{
		int n = A.length;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for(int i = 0;i< n;i++){
			min = Math.min(min, A[i]);
			max = Math.max(max, A[i]);
		}
		int nn = max - min + 1;
		
		int[] B = new int[n];
		int[] C = new int[nn];
		Arrays.fill(C, 0);
		
		for(int i = 0;i< n;i++)
			C[A[i]-min]++;
		for(int i = 1;i< nn;i++)
			C[i]+=C[i-1];
		for(int i = n-1;i>=0;i--)
			B[--C[A[i]-min]] = A[i];
		return B;
	}
}

QuickSelect.java

public class QuickSelect {
	public int select(int[] A, int idx)
	{
		return select(A,0,A.length - 1,idx);
	}
	public int select(int[] A,int p, int q, int idx)
	{
		int r = partition(A,p,q);
		if( r == p + idx - 1 )
			return A[r];
		else if(r > p + idx- 1)
			return select(A,p,r-1,idx);
		else
			return select(A,r+1,q,idx-(r-p)-1);
			
	}
	
	public int partition(int[] A, int p, int q){
		int i=p;
		int pivot = A[p];
		for(int k = p+1;k<= q;k++){
			if(A[k] < pivot)
			{
				int temp = A[i+1];
				A[i+1] = A[k];
				A[k] = temp;
				i++;
			}
		}
		int temp = A[i];
		A[i] = A[p];
		A[p] = temp;
		
		return i;
	}
}