import java.util.ArrayList;
import java.util.Arrays;

public class Program01 {

    static void quicksort(ArrayList<Integer> list, int lo, int hi) {
        if(lo < hi) {
            int p = partition(list, lo, hi);
            quicksort(list, lo, p-1);
            quicksort(list, p+1, hi);
        }
    }
    static int partition(ArrayList<Integer> list, int lo, int hi) {
        int pivot = list.get(hi);
        int i = lo -1;
        for (int j = lo; j < hi; j++) {
            if(list.get(j)<= pivot) {
                i++;
                swap(list, i, j);
            }
        }
        swap(list, i+1, hi);
        return i + 1;
    }
    static void swap(ArrayList<Integer> list, int i, int j) {
        int tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }
    static void kiir(ArrayList<Integer> list) {
        for(Integer x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Integer[] t = {8, 2, 7, 3, 4, 9};
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(t));
        quicksort(list, 0, list.size()-1);
        kiir(list);
    }
    
}