manthanthakker40

AllSortingAlgosCombined

Jan 2nd, 2017
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.24 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 allsortingalgos;
  7.  
  8. import java.util.Scanner;
  9.  
  10. /**
  11.  *
  12.  * @author manth
  13.  */
  14. public class AllSortingAlgos {
  15.  
  16.     /**
  17.      * @param args the command line arguments
  18.      */
  19.      static int n;
  20.     static double input[];
  21.     static String ALGO="QuickSort";
  22.     public static void main(String[] args) {
  23.        
  24.         Scanner sc=new Scanner(System.in);
  25.         //input();
  26.        
  27.         randinput();
  28.         System.out.println(" INPUT IS ");
  29.        
  30.         display(input);
  31.         long startTime = System.currentTimeMillis();
  32.         System.out.println("Select the type of sorting algorithm : \n1.Bubble Sort\n2.Selection Sort\n3.Insertion Sort\n4.Shell Sort\n5.MergeSort\n6.QuickSort");
  33.         switch(Integer.parseInt(sc.nextLine()))
  34.         {
  35.             case 1: bubblesort(input);
  36.             break;
  37.             case 2: insertionsort(input);
  38.             break;
  39.             case 3:  insertionsort(input);
  40.             break;
  41.             case 4: shellsort(input);
  42.             break;
  43.             case 5:mergesort(input,0,input.length-1);
  44.             break;
  45.             case 6: quicksort(input,0,input.length-1);
  46.             break;
  47.            
  48.                
  49.         }
  50.        
  51.         Long endTime=System.currentTimeMillis();
  52.         System.out.println("\n\ntime elapsed in sorting is "+ (endTime-startTime)+" Milliseconds \n\n");
  53.         System.out.println("OUTPUT OF SORTED NUMBERS IS ");
  54.         System.out.println("Numbers are sorted by "+ ALGO);
  55.         display(input);
  56.  
  57.      
  58.     }
  59.     public static double[] bubblesort(double []input)
  60.     {
  61.             long startTime = System.currentTimeMillis();
  62.             for(int i=input.length-1;i>0;i--)
  63.             {
  64.                 for(int j=0;j<i;j++)
  65.                 {
  66.                     if(input[j+1]<input[j])
  67.                     {
  68.                         double temp=input[j+1];
  69.                         input[j+1]=input[j];
  70.                         input[j]=temp;
  71.                     }
  72.                 }
  73.             }
  74.             Long endTime=System.currentTimeMillis();
  75.             System.out.println("\n\ntime elapsed in sorting is "+ (endTime-startTime)+" Milliseconds \n\n");
  76.                 return input;
  77.  
  78.     }
  79.    
  80.     public static double[] insertionsort(double input[])
  81.     {
  82.        
  83.         long startTime = System.currentTimeMillis();
  84.         int count=0;
  85.         for(int i=1;i<input.length;i++)
  86.         {
  87.            
  88.             for(int j=i;j>0;j--)
  89.             {
  90.                 if(input[j]<input[j-1])
  91.                 {
  92.                     double temp=input[j];
  93.                     input[j]=input[j-1];
  94.                     input[j-1]=temp;
  95.                     count++;
  96.                 }
  97.                 else
  98.                     break;
  99.             }
  100.         }
  101.         System.out.println(count +" passes");
  102.        
  103.        
  104.        
  105.         long endTime=System.currentTimeMillis();
  106.         System.out.println("\n\n time elapsed in sorting is "+ (endTime-startTime)+" Milliseconds \n\n");
  107.         return input;
  108.     }
  109.    
  110.     public static double[] shellsort(double input[])
  111.     {
  112.          long startTime = System.currentTimeMillis();
  113.        
  114.          for(int gap=input.length/2;gap>0;gap=gap/2)
  115.          {
  116.                 System.out.print("gap is "+gap);
  117.          
  118.                 for(int i=1;i<input.length;i++)
  119.                 {
  120.  
  121.                     for(int j=i;j>0;j-=gap)
  122.                     {
  123.                         if(input[j]<input[j-gap])
  124.                         {
  125.                             double temp=input[j];
  126.                             input[j]=input[j-gap];
  127.                             input[j-gap]=temp;
  128.                            
  129.                         }
  130.                         else
  131.                             break;
  132.                     }
  133.                     display(input);
  134.                 }
  135.        
  136.          }
  137.         Long endTime=System.currentTimeMillis();
  138.             System.out.println("\n\ntime elapsed in sorting is "+ (endTime-startTime)+" Milliseconds \n\n");
  139.         return input;
  140.     }
  141.     public static void display(double [] input)
  142.     {
  143.        
  144.         for(int i=0;i<input.length;i++)
  145.         {
  146.             System.out.println(input[i]+" ");
  147.         }
  148.     }
  149.     public static void randinput()
  150.     {
  151.         Scanner sc=new Scanner(System.in);
  152.         System.out.println(" BUBBLE SORT \n ENTER TOTAL NUMBERS TO SORT");
  153.         try{
  154.         n=Integer.parseInt(sc.nextLine());
  155.         }catch(Exception e)
  156.         {
  157.             System.out.println(" Please Enter a valid integer "+e);
  158.         }  
  159.         input=new double[n];
  160.         for(int i=0;i<n;i++)
  161.         {
  162.             input[i]=Math.random()*1000;
  163.         }
  164.     }
  165.     public static void input()
  166.     {
  167.         Scanner sc=new Scanner(System.in);
  168.         System.out.println(" \n ENTER TOTAL NUMBERS TO SORT");
  169.         try{
  170.         n=Integer.parseInt(sc.nextLine());
  171.         }catch(Exception e)
  172.         {
  173.             System.out.println(" Please Enter a valid integer "+e);
  174.         }  
  175.         input=new double[n];
  176.  
  177.         for(int i=0;i<n;i++)
  178.         {
  179.             input[i]=sc.nextInt();
  180.         }
  181.         System.out.println(" INPUT RECORDED ");
  182.         System.out.println(" Numbers are getting sorted by algorithm: "+ ALGO);
  183.  
  184.     }
  185.    
  186.    
  187.    
  188.    
  189.    
  190.     ////////////////////////////////////////////////////////////////////////
  191.      public static void mergesort(double input[],int low, int high)
  192.     {
  193.         int mid;
  194.         if(low<high)
  195.         {
  196.             mid=(low+high)/2;
  197.             mergesort(input,low,mid);
  198.             mergesort(input,mid+1,high);
  199.             merge(input,low,mid,mid+1,high);
  200.         }
  201.        
  202.     }
  203.     public static void merge(double input[],int l1,int u1,int l2,int u2)
  204.     {
  205.         double temp[]=new double[u2-l1+1];
  206.         int n=0;
  207.         int i=l1;
  208.         int j=l2;
  209.         while(i<=u1&&j<=u2)
  210.         {
  211.             temp[n++]=input[i]<input[j]?input[i++]:input[j++];
  212.         }
  213.         while(i<=u1)
  214.             temp[n++]=input[i++];
  215.         while(j<=u2)
  216.             temp[n++]=input[j++];
  217.        
  218.         n=0;
  219.         for(int k=l1;k<=u2;k++)
  220.             input[k]=temp[n++];
  221.          
  222.        
  223.        
  224.     }
  225.    
  226.     public static void quicksort(double input[],int left,int right)
  227.     {
  228.         int div=0;
  229.         int pivot=right;
  230.         int f=left;
  231.         int l=right;
  232.         while((left<right))
  233.         {
  234.             while((left<right)&&input[left]<=input[pivot])
  235.             {
  236.                 left++;
  237.             }
  238.             while((left<right)&&input[right]>input[pivot])
  239.             {
  240.                 right--;
  241.             }
  242.             if(left==right)
  243.             {
  244.                 double temp=input[left];
  245.                 input[left]=input[pivot];
  246.                 input[pivot]=temp;
  247.                 div=left;
  248.                    
  249.             }
  250.             else
  251.             {
  252.                 double temp=input[left];
  253.                 input[left]=input[right];
  254.                 input[right]=temp;
  255.                // System.out.print("here");
  256.             }
  257.            
  258.         }
  259.         //System.out.println("pass");
  260.           // display(input);
  261.         if(f<l)
  262.         {
  263.         quicksort(input,f,div-1);
  264.         quicksort(input,div+1,l);
  265.         }
  266.        // System.out.println("div is"+div);
  267.     }
  268.    
  269. }
Advertisement
Add Comment
Please, Sign In to add comment