import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static int partition(int[] arr,int low,int high){
        int i=low;
        int j=high;
        while(i<j){
            while(i<=high-1 && arr[i]<=arr[low])
            {
                i++;
            }
            while(j>=1 && arr[j]>arr[low]){
                j--;
            }
            if(i<j){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
            
        }
        int temp=arr[low];
            arr[low]=arr[j];
            arr[j]=temp;
            return j;
    }
    public static void quick_sort(int[] arr,int low,int high){
        if(low<high){
            int j=partition(arr,low,high);
            quick_sort(arr,low,j-1);
            quick_sort(arr,j+1,high);
        }
    }
    public static void main(String[] args) {
        int[] arr=new int[5];
        arr[0]=4;
        arr[1]=1;
        arr[2]=3;
        arr[3]=9;
        arr[4]=2;
        //int j=0;

        quick_sort(arr,0,4);
        for(int i=0;i<5;i++){
            System.out.println(arr[i]);
        }
    }
}