Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * To change this license header, choose License Headers in Project Properties.
- * To change this template file, choose Tools | Templates
- * and open the template in the editor.
- */
- package quicksort;
- import java.util.Scanner;
- /**
- *
- * @author manth
- */
- public class QuickSort {
- /**
- * @param args the command line arguments
- */
- static int n;
- static double input[];
- static String ALGO="QuickSort";
- public static void main(String[] args) {
- //input();
- randinput();
- System.out.println(" INPUT IS ");
- display(input);
- long startTime = System.currentTimeMillis();
- quicksort(input,0,input.length-1);
- Long endTime=System.currentTimeMillis();
- System.out.println("\n\ntime elapsed in sorting is "+ (endTime-startTime)+" Milliseconds \n\n");
- System.out.println("OUTPUT OF SORTED NUMBERS IS ");
- System.out.println("Numbers are sorted by "+ ALGO);
- display(input);
- }
- public static double[] bubblesort(double []input)
- {
- long startTime = System.currentTimeMillis();
- for(int i=input.length-1;i>0;i--)
- {
- for(int j=0;j<i;j++)
- {
- if(input[j+1]<input[j])
- {
- double temp=input[j+1];
- input[j+1]=input[j];
- input[j]=temp;
- }
- }
- }
- Long endTime=System.currentTimeMillis();
- System.out.println("\n\ntime elapsed in sorting is "+ (endTime-startTime)+" Milliseconds \n\n");
- return input;
- }
- public static double[] insertionsort(double input[])
- {
- long startTime = System.currentTimeMillis();
- int count=0;
- for(int i=1;i<input.length;i++)
- {
- for(int j=i;j>0;j--)
- {
- if(input[j]<input[j-1])
- {
- double temp=input[j];
- input[j]=input[j-1];
- input[j-1]=temp;
- count++;
- }
- else
- break;
- }
- }
- System.out.println(count +" passes");
- long endTime=System.currentTimeMillis();
- System.out.println("\n\n time elapsed in sorting is "+ (endTime-startTime)+" Milliseconds \n\n");
- return input;
- }
- public static double[] shellsort(double input[])
- {
- long startTime = System.currentTimeMillis();
- for(int gap=input.length/2;gap>0;gap=gap/2)
- {
- System.out.print("gap is "+gap);
- for(int i=1;i<input.length;i++)
- {
- for(int j=i;j>0;j-=gap)
- {
- if(input[j]<input[j-gap])
- {
- double temp=input[j];
- input[j]=input[j-gap];
- input[j-gap]=temp;
- }
- else
- break;
- }
- display(input);
- }
- }
- Long endTime=System.currentTimeMillis();
- System.out.println("\n\ntime elapsed in sorting is "+ (endTime-startTime)+" Milliseconds \n\n");
- return input;
- }
- public static void display(double [] input)
- {
- for(int i=0;i<input.length;i++)
- {
- System.out.println(input[i]+" ");
- }
- }
- public static void randinput()
- {
- Scanner sc=new Scanner(System.in);
- System.out.println(" BUBBLE SORT \n ENTER TOTAL NUMBERS TO SORT");
- try{
- n=Integer.parseInt(sc.nextLine());
- }catch(Exception e)
- {
- System.out.println(" Please Enter a valid integer "+e);
- }
- input=new double[n];
- for(int i=0;i<n;i++)
- {
- input[i]=Math.random()*1000;
- }
- }
- public static void input()
- {
- Scanner sc=new Scanner(System.in);
- System.out.println(" \n ENTER TOTAL NUMBERS TO SORT");
- try{
- n=Integer.parseInt(sc.nextLine());
- }catch(Exception e)
- {
- System.out.println(" Please Enter a valid integer "+e);
- }
- input=new double[n];
- for(int i=0;i<n;i++)
- {
- input[i]=sc.nextInt();
- }
- System.out.println(" INPUT RECORDED ");
- System.out.println(" Numbers are getting sorted by algorithm: "+ ALGO);
- }
- ////////////////////////////////////////////////////////////////////////
- public static void mergesort(double input[],int low, int high)
- {
- int mid;
- if(low<high)
- {
- mid=(low+high)/2;
- mergesort(input,low,mid);
- mergesort(input,mid+1,high);
- merge(input,low,mid,mid+1,high);
- }
- }
- public static void merge(double input[],int l1,int u1,int l2,int u2)
- {
- double temp[]=new double[u2-l1+1];
- int n=0;
- int i=l1;
- int j=l2;
- while(i<=u1&&j<=u2)
- {
- temp[n++]=input[i]<input[j]?input[i++]:input[j++];
- }
- while(i<=u1)
- temp[n++]=input[i++];
- while(j<=u2)
- temp[n++]=input[j++];
- n=0;
- for(int k=l1;k<=u2;k++)
- input[k]=temp[n++];
- }
- public static void quicksort(double input[],int left,int right)
- {
- int div=0;
- int pivot=right;
- int f=left;
- int l=right;
- while((left<right))
- {
- while((left<right)&&input[left]<=input[pivot])
- {
- left++;
- }
- while((left<right)&&input[right]>input[pivot])
- {
- right--;
- }
- if(left==right)
- {
- double temp=input[left];
- input[left]=input[pivot];
- input[pivot]=temp;
- div=left;
- }
- else
- {
- double temp=input[left];
- input[left]=input[right];
- input[right]=temp;
- // System.out.print("here");
- }
- }
- //System.out.println("pass");
- // display(input);
- if(f<l)
- {
- quicksort(input,f,div-1);
- quicksort(input,div+1,l);
- }
- // System.out.println("div is"+div);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment