JAvaソート(二)

クイックソート:
       まず、表の中の1つの要素を区分要素として選択する.次に、表を区分し、区分要素より小さいすべての要素を区分要素の左側に配置し、区分要素より大きいすべての要素をその右側に拡大する.最後に、このような戦略で2つの区分のフィールドをソートする.

public static void quickSort (Comparable[] data, int min, int max) {
		int pivot;
		
		if (min < max){
			pivot = partition(data, min, max);
			quickSort(data, min, pivot-1);
			quickSort(data, pivot+1, max);
		}
	}
	
	//            
private static int partition (Comparable[] data, int min, int max){
		//            
		Comparable partitionValue = data[min];
		
		int left = min;
		int right = max;
		
		while (left < right ) {
			//            
			while (data[left].compareTo(partitionValue) <= 0 && left < right)
				left ++;
			//            
			while (data[right].compareTo(partitionValue) > 0 )
				right --;
			
			if (left < right)
				swap(data, left, right);
		}
		swap(data, min, right);
		return right;
	}

集計ソート:
      最初は表をほぼ等しい両端に分割し、各ワード表に対して自身を再帰的に呼び出す.この再帰的な呼び出しプロセスを継続し、再帰の基礎状況に達するまで、このとき表は1つの要素しか含まれていないワード表に分かれている.
再帰呼び出し構造は、アルゴリズムが2つの再帰呼び出しから得る2つの順序付きサブセグメントを1つの順序付きテーブルに結合する.

public static void mergeSort(Comparable[] data, int min, int max) {
		if(min < max) {
			int mid = (min + max) / 2;
			mergeSort(data, min, mid);
			mergeSort(data, mid + 1, max);
			merge(data, min, mid, max);
		}
	}
public static void merge(Comparable[] data, int first, int mid, int last) {
		
		Comparable[] temp = new Comparable[data.length];
		
		int first1 = first, last1 = mid;	//endpoints of first subarray
		int first2 = mid + 1, last2 = last;	//endpoints of second subarray
		int index = first1;
		
		while(first1 <= last1 && first2 <= last2) {
			if(data[first1].compareTo(data[first2]) < 0) {
				temp[index] = data[first1];
				first1 ++;
			}
			else {
				temp[index] = data[first2];
				first2 ++;
			}
			index ++;
		}
		//Copy remaining elements from first subarray, if any 
		while(first1 <= last1) {
			temp[index] = data[first1];
			first1 ++;
			index ++;
		}
		//Copy remaining elements from second subarray, if any 
		while(first2 <= last2) {
			temp[index] = data[first2];
			first2 ++;
			index ++;
		}
		
		//Copy merged data into original array
		
		for (index = first; index <= last; index++)
			data[index] = temp[index];
		
	}