package alice.test.codesegment.local.bitonicsort;

public class Sort {
	
	// this method has "stack overflow" problem
	public static void quickSort(DataList data){
		int[] stack = new int[8192];
		int sp = 0;
		int begin = 0;
		int end = data.table.length-1; // index is up to length-1
		while(true){
			while(begin < end){
				if (end-begin< 40){
					bubbleSort(data,begin,end);
					break;
				} else {
					int where = (begin+end)/2;
					int pivot = data.table[where];
					data.table[where] = data.table[begin];
					int p = begin;
					for (int i=begin+1;i<=end;i++){
						if (data.table[i]<pivot){
							p++;
							if (i!=p)data.swap(p,i);
						}
					}
					data.table[begin] = data.table[p];
					data.table[p] = pivot;
					stack[sp++] = p+1;
					stack[sp++] = end;
					end=p-1;
				}
			}
			if (sp==0) return;
			end = stack[--sp];
			begin = stack[--sp];
			
		}
	}
	
	public static void bubbleSort(DataList data ,int begin,int end){
		for (int i=begin;i<end;i++){
			for (int j=end;j>i;j--){
				if (data.table[i] > data.table[j]){
					data.swap(i,j);
				}
			}
		}
		
		
	}
	
	public static void check(DataList data){
		System.out.println("checking ....");
		for (int i = 0; i< data.table.length-1; i++){
			if (data.table[i] > data.table[i+1]){
				System.out.println("MISS "+data.table[i]+" > "+data.table[i+1]+" Position is "+i);
				return;
			}
		}
		System.out.println("sort is succeed");
	}
}