Module 2: Quick Sort implementation in JAVA

Laboratory Component:

Sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n on graph sheet. The elements can be read from a file or can be generated using the random number generator. Demonstrate using Java how the divide -and- conquer method works along with its time complexity analysis: worst case, average case and best case.

importjava.util.Random;

importjava.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<high)

    {

      while(a[i]<=p&&i<high)

       i++;

       while(a[j]>p)

       j--;

      if(i<j)

     {

      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<high)

  {

    int s=partition(a,low,high);

    sort(a,low,s-1);

    sort(a,s+1,high);

    }

}

public static void main(String[] args) 

{

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<n;i++)

a[i]=generator.nextInt(20);

System.out.println("Array before sorting");

for( i=0;i<n;i++)

System.out.println(a[i]+" ");

longstartTime=System.nanoTime();

quicksort m=new quicksort();

m.sort(a,0,n-1);

longstopTime=System.nanoTime();

longelapseTime=(stopTime-startTime);

System.out.println("Time taken to sort array is:"+elapseTime+"nano

seconds");

System.out.println("Sorted array is");

for(i=0;i<n;i++)

System.out.println(a[i]);

}

}