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

    }

  }

Implementation of Quick Sort

AIM:

          To write a C program to implement Quick sort

ALGORITHM:

            Step 1: Start the program.

Step 2: Declare the function quicksort(array)

Step 3: less, equal, greater := three empty arrays

Step 4: if length(array) > 1 

Step 5: Then pivot := select any element of array

Step 6: for each x in array

            if x < pivot then add x to less

            if x = pivot then add x to equal

            if x > pivot then add x to greater

        quicksort(less)

        quicksort(greater)

Step 7: array := concatenate(less, equal, greater)

Step 8: Stop the program.

PROGRAM

#include<stdio.h>

void quicksort(int [10],int,int);

int main()

{

int x[20],size,i;

printf("Enter size of the array: ");

scanf("%d",&size);

printf("Enter %d elements: ",size);

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

scanf("%d",&x[i]);

quicksort(x,0,size-1);

printf("Sorted elements: ");

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

printf(" %d",x[i]);

return 0;

}

void quicksort(int x[10],int first,int last)

{

int pivot,j,temp,i;

if(first<last)

{

pivot=first;

i=first;

j=last;

while(i<j)

{

while(x[i]<=x[pivot]&&i<last)

i++;

while(x[j]>x[pivot])

j--;

if(i<j)

{

temp=x[i];

x[i]=x[j];

x[j]=temp;

}

}

temp=x[pivot];

x[pivot]=x[j];

x[j]=temp;

quicksort(x,first,j-1);

quicksort(x,j+1,last);

}

}