## Java program to Sort a given set of n integer elements using Quick Sort method and compute its time complexity

				
import java.util.Random;
import java.util.Scanner;
public class quicksort {
static int max=2000;
int partition (int[] a, int low,int high)
{
int p,i,j,temp;
p=a[low];
i=low+1;
j=high;
while(low
{
while(a[i]<=p&&i
i++;
while(a[j]>p)
j--;
if(i
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
{
temp=a[low];
a[low]=a[j];
a[j]=temp;
return j;
}
}
return j;
}
void sort(int[] a,int low,int high)
{
if(low
{
int s=partition(a,low,high);
sort(a,low,s-1);
sort(a,s+1,high);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub

int[] a;
int i;
System.out.println("Enter the array size");
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();
a= new int[max];
Random generator=new Random();
for( i=0;i
a[i]=generator.nextInt(20);
System.out.println("Array before sorting");
for( i=0;i
System.out.println(a[i]+" ");
long startTime=System.nanoTime();
quicksort m=new quicksort();
m.sort(a,0,n-1);
long stopTime=System.nanoTime();
long elapseTime=(stopTime-startTime);
System.out.println("Time taken to sort array is:"+elapseTime+"nano
seconds");
System.out.println("Sorted array is");
for(i=0;i
System.out.println(a[i]);
}
}


OUTPUT:
Enter the array size
10
Array before sorting
16
17
12
2
10
3
18
15
15
17
Time taken to sort array is:16978 nano seconds
Sorted array is
23
10
12
15
15
16
17
17
18