Pages

Labels

Quicksort Program in Java

import java.io.*;
import java.util.*;

public class QuickSort{
   public static void main(String argv[])throws IOException{
       final int SIZE =30;
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       System.out.println("Enter the number of elements you want to enter");
       int n = Integer.parseInt(br.readLine());
       int [] arr =new int [SIZE];
       System.out.println("Enter the elements of the array");
       for (int i=0 ; i < n; i++)
         arr[i] = Integer.parseInt(br.readLine());

       Quicksort(arr, 0, n-1);

       for (int i=0 ; i < n ; i++)
          System.out.print(arr[i] + " ");
      System.out.println();
   }
   public static void Quicksort(int arr[], int f, int l){
      if (f >= l) return;
      int pivot_index = partition(arr, f, l);
      Quicksort(arr, f, pivot_index);
      Quicksort(arr, pivot_index+1, l);
   }
 
   public static int partition(int arr[], int f, int l){
      int pivot = arr[f];
      while (f < l)
      {
         /*if (arr[f] == pivot || arr[l] == pivot)
         {
            System.out.println("Only distinct integers allowed - C321");
            System.out.println("students should ignore this if statement");
            System.out.exit(0);
         }*/
         while (arr[f] < pivot)
             f++;
         while (arr[l] > pivot)
             l--;
         swap (arr, f, l);
      }
      return f;
   }
   public static void swap (int arr[], int x, int y){
      int temp = arr[x];
      arr[x] = arr[y];
      arr[y] = temp;
   }
}