class Sort {
    public static void main(String[] args){
	int[] a = {1,2,3,4};
	qsort(a);
	print(a);
	a = new int[]{4,3,2,1};
	qsort(a);
	print(a);
	a = new int[]{1,1,1,1};
	qsort(a);
	print(a);
    }
	
    public static void qsort(int[] a){
	qsort(a,0,a.length-1);
    }

    public static void qsort(int[] a, int l, int u){
	if (l>=u) return;
	int p = partition(a,l,u);
	qsort(a,l,p-1);
	qsort(a,p+1,u);
    }
    
    public static int partition(int[] a, int l, int u){
	int p = l++;
	while (l<=u){
	    while (a[l]<=a[p] && l<u) l++;
	    while (a[u]>a[p]) u--;
	    if (l<=u){
		swap(a,l,u);
		l++; 
	    }
	}
	swap(a,u,p);
	return u;
    }
    
    static void swap(int[] a, int i, int j){
	int t = a[i];
	a[i] = a[j];
	a[j] = t;
    }

    static void print(int[] a){
	for (int i=0;i<a.length;i++){
	    System.out.print(a[i]+" ");
	}
	System.out.println();
    }
}