import java.util.Scanner;

public class QuickSort {

    public static void quicksort(int[] a, int lb, int ub) {
        int pivot, start, end;
        pivot = a[lb];
        start = lb;
        end = ub;

        if (start < end) {
            while (start < end) {
                while (start < end && a[start] <= pivot) {
                    start++;
                }
                while (a[end] > pivot) {
                    end--;
                }
                if (start < end) {
                    swap(a, start, end);
                }
            }
            swap(a, lb, end);

            quicksort(a, lb, end - 1);
            quicksort(a, end + 1, ub);
        }
    }

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

    public static void display(int[] a) {
        System.out.println("Sorted array:");
        for (int i : a) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter array size:");
        int n = scanner.nextInt();
        int[] a = new int[n];

        System.out.println("Enter elements into array:");
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        quicksort(a, 0, n - 1);
        display(a);

        scanner.close();
    }
}