manthanthakker40

MergeSort

Jan 2nd, 2017
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.15 KB | None | 0 0
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package mergesort;
  7.  
  8. import java.util.Scanner;
  9.  
  10. /**
  11.  *
  12.  * @author manth
  13.  */
  14. public class MergeSort {
  15.  
  16.     /**
  17.      * @param args the command line arguments
  18.      */
  19.     static int n;
  20.     static double input[];
  21.     static String ALGO="MergeSort";
  22.     public static void main(String[] args) {
  23.  
  24.         //input();
  25.        
  26.         randinput();
  27.         System.out.println(" INPUT IS ");
  28.        
  29.         display(input);
  30.         long startTime = System.currentTimeMillis();
  31.         mergesort(input,0,input.length-1);
  32.         Long endTime=System.currentTimeMillis();
  33.         System.out.println("\n\ntime elapsed in sorting is "+ (endTime-startTime)+" Milliseconds \n\n");
  34.         System.out.println("OUTPUT OF SORTED NUMBERS IS ");
  35.         System.out.println("Numbers are sorted by "+ ALGO);
  36.         display(input);
  37.  
  38.      
  39.     }
  40.    
  41.    
  42.     public static void display(double [] input)
  43.     {
  44.        
  45.         for(int i=0;i<input.length;i++)
  46.         {
  47.             System.out.println(input[i]+" ");
  48.         }
  49.     }
  50.     public static void randinput()
  51.     {
  52.         Scanner sc=new Scanner(System.in);
  53.         System.out.println(" BUBBLE SORT \n ENTER TOTAL NUMBERS TO SORT");
  54.         try{
  55.         n=Integer.parseInt(sc.nextLine());
  56.         }catch(Exception e)
  57.         {
  58.             System.out.println(" Please Enter a valid integer "+e);
  59.         }  
  60.         input=new double[n];
  61.         for(int i=0;i<n;i++)
  62.         {
  63.             input[i]=Math.random()*1000;
  64.         }
  65.     }
  66.     public static void input()
  67.     {
  68.         Scanner sc=new Scanner(System.in);
  69.         System.out.println(" \n ENTER TOTAL NUMBERS TO SORT");
  70.         try{
  71.         n=Integer.parseInt(sc.nextLine());
  72.         }catch(Exception e)
  73.         {
  74.             System.out.println(" Please Enter a valid integer "+e);
  75.         }  
  76.         input=new double[n];
  77.  
  78.         for(int i=0;i<n;i++)
  79.         {
  80.             input[i]=sc.nextInt();
  81.         }
  82.         System.out.println(" INPUT RECORDED ");
  83.         System.out.println(" Numbers are getting sorted by algorithm: "+ ALGO);
  84.  
  85.     }
  86.    
  87.    
  88.    
  89.    
  90.    
  91.     ////////////////////////////////////////////////////////////////////////
  92.      public static void mergesort(double input[],int low, int high)
  93.     {
  94.         int mid;
  95.         if(low<high)
  96.         {
  97.             mid=(low+high)/2;
  98.             mergesort(input,low,mid);
  99.             mergesort(input,mid+1,high);
  100.             merge(input,low,mid,mid+1,high);
  101.         }
  102.        
  103.     }
  104.     public static void merge(double input[],int l1,int u1,int l2,int u2)
  105.     {
  106.         double temp[]=new double[u2-l1+1];
  107.         int n=0;
  108.         int i=l1;
  109.         int j=l2;
  110.         while(i<=u1&&j<=u2)
  111.         {
  112.             temp[n++]=input[i]<input[j]?input[i++]:input[j++];
  113.         }
  114.         while(i<=u1)
  115.             temp[n++]=input[i++];
  116.         while(j<=u2)
  117.             temp[n++]=input[j++];
  118.        
  119.         n=0;
  120.         for(int k=l1;k<=u2;k++)
  121.             input[k]=temp[n++];
  122.          
  123.        
  124.        
  125.     }
  126.     /////////////////////////////////////////////////////////////////////
  127. }
Advertisement
Add Comment
Please, Sign In to add comment