Quick Sort

AIM

To write a Java program for the implementation the quick sort

ALGORITHM

Step1   :start the program

Step2:  declare and initialize the array size

Step3:  enter the number of elements to be quick sorted.

Step4:  enter the elements using for loop

Step5:  call the function quick(1,noe)

            Void quick(int first,int last)

Step6:  if the first element is less than the last

(a)    then the first element is taken as the pivot &i=first, &j=last

(b)   the condition is checked for i<j if true

Step7:  set a loop to check the elements

            (a)while (a[pivot]>=a[i]&&i<last)i++;

            (b)while (a[pivot]>=a[j]&&j>first)j--;

Step8:  if (i>j)

            Swap(i,j)

Step9:  sort the elements and display the sorted values.

PROGRAM

Quick Sort

import java.io.*;

class quicksortalg

{

   int noe;

   int[] a=new int[100];

    public void sort()

   {

           try

           {

                    System.out.println("Enter the number of elements:");

                    DataInputStream din=new DataInputStream(System.in);

                    noe=Integer.parseInt(din.readLine());         

                   System.out.println("Enter the elements:");

                   for(int i=1;i<=noe;i++)

                   a[i]=Integer.parseInt(din.readLine());

                    System.out.println("The array:");

                  display();

           }

           catch(Exception e){}

           quick(1,noe);

  }

   public void swap(int i,int j)

  {

     int t;

     t=a[i];a[i]=a[j];a[j]=t;

  }

 public void quick(int first,int last)

  {

    if(first<last)

    {

      int pivot=first;

      int i=first;

      int j=last;

      while(i<j)

      {     

         while(a[pivot]>=a[i] && i<last) i++;

         while(a[pivot]<=a[j] && j>first) j--;

         if(i<j) swap(i,j);

       }

      swap(pivot,j);

      quick(first,j-1);

      quick(j+1,last);

    }

  }

   public void display()

   {

     for(int i=1;i<=noe;i++)

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

   }

}

class quicksort

{

   public static void main(String args[])throws IOException

   {

      quicksortalg q1=new quicksortalg();

      q1.sort();

      System.out.println("The sorted array:");

      q1.display();

   }

OUTPUT

Enter the number of elements:

5

Enter the elements:

2

96

1

45

63

The array:

2

96

1

45

63

The sorted array:

1

2

45

63

96

  

RESULT:

            Thus the program for quick sort has been implemented using Java and the output is verified.