/* クイックソート */
import java.util.*;
class QuickSort {
    public static void main (String[] args) {
        int   seed = 3885;                   // 擬似乱数の種
        int   size = 1000;                   // 配列の大きさ
        int[] data = make_array(size, seed); // 配列データを作成

    	quick_sort(data, 0, data.length-1);  // 配列データをクイックソート
        print_array(data);                   // ソート結果を表示
        if (!is_sorted_array(data)) {        // ソート結果をチェック
            System.out.println("bad sorted");
        }
    }

    // 配列中の2つのデータ data[i]と data[j]の値を交換する．
    static void swap (int[] data, int i, int j) {
        int tmp=data[i]; data[i]=data[j]; data[j]=tmp;
    }

    // 整数の大きさ sizeの配列をつくり，種を seedとした
    // 擬似乱数で初期化する．種が同じならば同じデータ列となる．
    // この配列をソートするデータ列として使用する．
    // sizeで割った余りとしているのは，重複データを作るためである．
    static int[] make_array (int size, long seed) {
        Random random = new Random(seed);
        int[]  data = new int[size];

        for (int i=0; i<data.length; i++) {
            // 0〜size-1 の範囲でランダムにデータを生成
            data[i] = Math.abs(random.nextInt()) % size;
        }
        return data;
    }

    // 整数配列の中身を表示するメソッド．ソートの様子を知るのに便利．
    static void print_array (int[] data) {
        for (int i=0; i<data.length; i++) {
            System.out.print(data[i]+" ");
        }
        System.out.println(); // 改行する
    }

    // 整数配列 dataが昇順ならば true，さもなくば falseを返すメソッド．
    // データ数が多い時に，ソート結果をチェックするのに便利．
    static boolean is_sorted_array(int[] data) {
        for (int i=0; i<data.length-1; i++) {
            if (data[i]>data[i+1]) {
                return false;
            }
        }
        return true;
    }

    static void quick_sort (int[] data, int from, int to) {
	if (from>=to) return;        // 範囲が十分に狭ければリターン
	int pivot=data[(from+to)/2]; // ピボットを真中から選ぶ
	int left=from, right=to;     // 分割用のインデックス

	while (left<=right) {
	    while (data[left]<pivot)  left++; // pivot以上を探す
	    while (data[right]>pivot) right--; // pivot以下を探す
	    if (left<=right) {
		swap(data, left, right);
		left++; right--;
	    }
	}
	quick_sort(data, from, right); // 再帰的に左側をクイックソート
	quick_sort(data, left, to);    // 再帰的に右側をクイックソート
    }
}