manthanthakker40

QuickSort

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