DATA STRUCTURE ME LAB PROGRAMS-->7. QUICKSORT

QUICKSORT

Program Coding:

 

import java.io.*;

public class quick

{

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

   {

       int i,n=0;

      

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

       n=Integer.parseInt(br.readLine());

       int array[]=new int[n];

       System.out.println("Enter the elements one by one:\n");

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

       {

          System.out.println("Enter the element" +(i+1));

          array[i]=Integer.parseInt(br.readLine());

       }

       System.out.println("       Quick Sort\n\n");

       System.out.println("Values Before the sort:\n");

       for(i = 0; i < array.length; i++)

            System.out.print( array[i]+"  ");

       System.out.println();

       quickSort(array,0,array.length-1);

       System.out.print("Values after the sort:\n");

       for(i = 0; i <array.length; i++)

           System.out.print(array[i]+"  ");

       System.out.println();

       System.out.println("PAUSE");

  }

  public static int partition(int arr[], int left, int right)

  {

 

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

      while (i <= j)

      {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j)

            {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      }    

      return i;

  } 

 

 

 

 

public static void quickSort(int arr[], int left, int right)

  {

 

      int index = partition(arr, left, right);

      if (left < index - 1)

            quickSort(arr, left, index - 1);

      if (index < right)

            quickSort(arr, index, right);

  }

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Output:

 

QUICKSORT:

Enter the no.of elements:

3

Enter the elements one by one,

Enter the element1:

60

Enter the element2:

40

Enter the element3:

2

QUICKSORT

Values before the sort:

60

40

2

Values after the sort:

2

40

60

PAUSE