import java.util.Random;

/**
 * Created by Danila on 02.09.2016.
 */
public class qs {
    final static int n=100000;
    static int a[] =new int[n];

    static void swap(int i, int j){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }

    static void quickSort(int l, int r){
        Random rand= new Random();

        int x= a[l+(r-l)/2];//rand.nextInt()%(r-l+1) + 1;
        int i = l;
        int j = r;

        while(i <= j) {
            while((a[i] < x)&&(i<=r)) i++;
            while((a[j] > x)&&(j>=l)) j--;
            if(i <= j) {
                swap(i, j);
                i++;
                j--;
            }
        }
        if (i<r)
            quickSort(i, r);
        if (l<j)
            quickSort(l, j);
    }

    public static void main(String[] args) {
        Random rand = new Random();

        for(int i = 0; i < n; i++) {
            a[i]=rand.nextInt(10);
        }
        for(int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
        quickSort(0, n-1);
        for(int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }


    }
}