QuickSort.java


package Sorting;
import java.util.*;
public class QuickSort {
public static void main(String[] san){
    while(true){
    Scanner input=new Scanner(System.in);
    int num=input.nextInt();   // input how many numbers
    int[] a=new int[num+1]; 
    for(int i=1;i<=num;i++)
        a[i]=input.nextInt();     // array input
   
    quickSort(a,1,a.length-1);
   
   
    for(int i=1;i<=num;i++)
        System.out.printf("%d ",a[i]);
    }
}

public static void quickSort(int [] a,int p,int r){     //first of all p=pivot=1 and r= last element of the array A
    int q;
    if(p<r){
        q=Partition(a,p,r);
        quickSort(a,p,q-1);                // Left Sub Group
        quickSort(a,q+1,r);               // Right Sub Group
    }
}

public static int Partition(int [] a,int p,int r){
    int x,i,j,t;
    x=a[r];
    i=p-1;
    for(j=p;j<=r-1;j++){
        if(a[j]<=x)           //if A[j]>x   do nothing
        {
            i++;
            t=a[i];
            a[i]=a[j];
            a[j]=t;   
        }
    }
    t=a[i+1];
    a[i+1]=a[r];
    a[r]=t;
   
   
    return i+1;
}
}