Untitled

mail@pastecode.io avatar
unknown
java
12 days ago
3.4 kB
1
Indexable
Never
import java.util.*;
import java.io.*;
public class Main{
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            while(st==null || !st.hasMoreTokens()){
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        String nextLine(){
            String str="";
            try {
                str=br.readLine().trim();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    static class FastWriter {
		private final BufferedWriter bw;
		public FastWriter() {
			this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
		}
		public void print(Object object) throws IOException {
			bw.append("" + object);
		}
		public void println(Object object) throws IOException {
			print(object);
			bw.append("\n");
		}
		public void close() throws IOException {
			bw.close();
		}
	}
	
	public static void swap(int i, int j, int[]arr){
	    int temp = arr[i];
	    arr[i] = arr[j];
	    arr[j] = temp;
	}
	
	public static int partition(int l, int r, int[] arr){
	    int pvt = l;
	    int i = l,j = r;
	    while(i<j){
	        while(i<r && arr[pvt]<=arr[i]){
	            i++;
	        }
	        while(j>l && arr[pvt]>arr[j]){
	            j--;
	        }
	       // System.out.println(arr[i]+" "+arr[j]+" "+arr[pvt]);
	        if(i<j) swap(i,j,arr);
	       // for(int x:arr){
	       //     System.out.print(x+" ");
	       // }
	       // System.out.println();
	    }
	    swap(j,pvt,arr);
	    return j;
	   
	}
	public static void quickSort(int l, int r, int[]arr){
	    if(l<r){
	        int p = partition(l,r,arr);
	       // for(int i:arr){
	       //     System.out.print(i+" ");
	       // }
	       // System.out.println();
	        quickSort(l,p-1,arr);
	        quickSort(p+1,r,arr);

	    }
	}
	
    public static void main(String[] args) {
        try {
            FastReader sc=new FastReader();
            FastWriter out = new FastWriter();
            
            //write code here
            Random rnd = new Random();
        	    int n = sc.nextInt();
                int[] arr = new int[n];
                for(int i = 0; i<n;i++){
                    arr[i] = sc.nextInt();
                }
                for(int i = 0;i<n;i++){
                    
                    int j = rnd.nextInt(n-1);
                    swap(i,j,arr);
                }
                quickSort(0,n-1,arr);
                for(int i:arr){
                    System.out.print(i+" ");
                }
            out.close();
        
        }
        catch (Exception e) {
            e.printStackTrace() ;
            return;
        }
    }
    
}
Leave a Comment