import java.io.*;
class qsort {
    int arr[], l, u;
    int arrt[];
    int size;
    public qsort(int ele[]) {
        arr = ele;
        l = 0;
        size = arr.length;
        u = arr.length - 1;
    }
    public void startsort() {
        sort(l, u);
    }
    public void sort(int lb, int ub) {
        if (lb > ub)
            return;
        int arrt[] = new int[size];
        int tc = lb;
        int pivot = arr[lb];
        if (lb == ub) {
            arrt[lb] = pivot;
            return;
        }
        for (int i = lb; i <= ub; i++) {
            if (pivot > arr[i]) {
                arrt[tc] = arr[i];
                tc++;
            } else
                continue;
        }
        int index = tc;
        arrt[tc] = pivot;
        tc++;
        for (int i = lb; i <= ub; i++) {
            if (pivot < arr[i]) {

                arrt[tc] = arr[i];
                tc++;
            } else
                continue;
        }
        for (int i = lb; i <= ub; i++) {
            arr[i] = arrt[i];
        }
        if (lb < ub) {
            sort(lb, index - 1);
            sort(index + 1, ub);
        }
    }
    public void display() {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
public class Quicksort {
    public static void main(String[] args) throws IOException {
        BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the size of array");
        int size = Integer.parseInt(obj.readLine());
        int arr[] = new int[size];
        System.out.println("Enter The array");
        for (int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(obj.readLine());
        }
        qsort qs = new qsort(arr);
        System.out.println("Array Before sort:");
        qs.display();
        System.out.println();
        System.out.println("Array after sort");
        qs.startsort();
        qs.display();
    }
}

/* Output
Enter the size of array
7
Enter The array
15
32
45
25
34
29
14
Array Before sort:
15 32 45 25 34 29 14 
Array after sort
14 15 25 29 32 34 45
 */