API tools faq
paste
Advertisement
jTruBela

Merge Sort

jTruBela
Nov 9th, 2021 (edited)
838
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 10.91 KB | None | 0 0
raw download clone embed print report
  1. package mergeSort;
  2.  
  3. import java.util.*;
  4.  
  5. public class Merge_Sort {
  6.         public static int[] merge_sort (int[] array, int p, int r) {
  7.        
  8.         if (p < r) {
  9.             int q = (int) Math.floor((p+r)/2);
  10.             Merge_Sort.merge_sort(array,p,q);
  11.             Merge_Sort.merge_sort(array,q+1,r);
  12.             Merge(array,p,q,r);
  13.         }
  14.        
  15.        
  16.         return array;
  17.     }
  18.    
  19.     public static void Merge(int[] array, int p, int q, int r) {
  20.         int n1 = q-p+1;
  21.         int n2 = r-q;
  22.        
  23.         int L[] = new int [n1+1];
  24.         int R[] = new int [n2+1];
  25.        
  26.        
  27.         for(int i = 0;i < n1;i++) {        
  28.             L[i] = array[p+i];
  29.         }  
  30.        
  31.         for(int j = 0;j < n2;j++) {
  32.             R[j] = array[q+j+1];
  33.         }                  
  34.        
  35.         L[n1] = Integer.MAX_VALUE;
  36.         R[n2] = Integer.MAX_VALUE;
  37.  
  38.         int i = 0;
  39.         int j = 0; 
  40.        
  41.         for(int k = p; k<=r; k++) {
  42.             if (L[i] <= R[j]) {
  43.                 array[k] = L[i];
  44.                 i++;           
  45.             }          
  46.             else { 
  47.                 array[k] = R[j];
  48.                 j++;
  49.             }
  50.  
  51.         }
  52.  
  53.     }
  54.                     // array = 8
  55.                     /*  p        q q+1       r
  56.                      *  1  2  3  4  5  6  7  8  
  57.                      * [ ][ ][ ][ ][ ][ ][ ][ ] >   n1 = 5 - 1 = 4  >   8 - 4 = 4
  58.                      *                                   q - p + 1      r - q                       // No index issue
  59.                     /*  p        q q+1       r  >   n2 = 4 - 0 = 4  >   7 - 3 = 4              
  60.                      *  0  1  2  3  4  5  6  7                 
  61.                      * [ ][ ][ ][ ][ ][ ][ ][ ]
  62.                      */
  63.        
  64.                     // 4-1+1 = 4    or  3-0+1 = 4
  65.                     //   8-4 = 4    or    7-3 = 4
  66.        
  67.        
  68.                     // need to copy in indexes 1-4+1(Sentinel value)  to a sub array
  69.                     // need to copy in indexes 0-3+1(Sentinel value)  to a sub array    // No index issue
  70.                     // n1 + 1 = 4 + 1 = 5          
  71.                     // n2 + 1 = 4 + 1 = 5
  72.        
  73.                     // L[].length = 5
  74.                     // R[].length = 5
  75.                     // L[].length + R[].length = 10
  76.                    
  77.        
  78.        
  79.                    
  80.                     // for each index in L array from first index to 1 to n1, L[index] = array[p + i - 1]
  81.                     //                                               1...4 = 4                 1 + 1 - 1 = 1
  82.                     //                                               0...3 = 4                 0 + 1 - 1 = 0
  83.                     //
  84.                     // for each index in R array from first index to 1 to n2, R[index] = array[q + j]
  85.                     //                                               1...4 = 4                 4 + 0 = 4
  86.                     //                                               0...3 = 4                 3 + 1 = 4
  87.                     //
  88.                     //  p = 1   q = 4   r = 8   n1 = 4  L.length = 5    i = 1   R.length = 5    j = 1
  89.                     //  p = 0   q = 3   r = 7   n2 = 4  L.length = 5    i = 0   R.length = 5    j = 0
  90.                    
  91.                                             // i = 1
  92.                                             // run 4 times 1...4
  93.                                             //             0...3       
  94.                                             // if 1 <= 4 = TRUE
  95.                                             //
  96.                                             // L[i-1] = array[p + i - 1]
  97.                                             // L[1-1] = array[0 + 1 - 1]
  98.                                             // L[0] = array[0]
  99.                                             // i++ = 2
  100.        
  101.        
  102.                                             // i = 2
  103.                                             // if 2 <= 4 = TRUE
  104.                                             // L[i-1] = array[p + i - 1]
  105.                                             // L[2-1] = array[0 + 2 - 1]
  106.                                             // L[1]   = array[1]
  107.                                             // i++ = 3
  108.  
  109.        
  110.                                             // i = 3
  111.                                             // if 3 <= 4 = TRUE
  112.                                             // L[3-1] = array[p + i - 1]
  113.                                             // L[3-1] = array[0 + 3 - 1]
  114.                                             // L[2]   = array[2]
  115.                                             // i++ = 4
  116.  
  117.        
  118.                                             // i = 4
  119.                                             // if 4 <= 4 = TRUE
  120.                                             // L[4-1] = array[p + i - 1]
  121.                                             // L[4-1] = array[0 + 4 - 1]
  122.                                             // L[3]   = array[3]
  123.                                             // i++ = 5
  124.        
  125.  
  126.                                             // i = 5
  127.                                             // if 5 <= 4 = FALSE
  128.                                             // END LOOP
  129.  
  130.                                             /*  p        q   q+1       r    >   n2 = 4 - 0 = 4  >   7 - 3 = 4
  131.                                              *  0  1  2  3    4  5  6  7               
  132.                                              * [ ][ ][ ][ ]  [ ][ ][ ][ ]
  133.                                              ** Left Array    Right Array              
  134.  
  135.                                              */
  136.                                             // j = 1
  137.  
  138.                                             // if 1 <= 4 = TRUE
  139.                                             // R[1-1] = array[q+j]
  140.                                             // R[1-1] = array[3+1]
  141.                                             // R[0]   = array[4]
  142.                                             // j+1 = 2
  143.                                            
  144.                                             /* j = 2
  145.                                              * if 2 <= 4 = TRUE
  146.                                              * R[2-1] = array[q+j]
  147.                                              * R[2-1] = array[3+2]
  148.                                              * R[1]   = array[5]
  149.                                              * j++ = 3
  150.                                              *
  151.                                              * if 3 <= 4 = TRUE
  152.                                              * R[3-1] = array[q+j]
  153.                                              * R[3-1] = array[3+3]
  154.                                              * R[2]   = array[6]
  155.                                              * j++ = 4
  156.                                              *
  157.                                              * if 4 <= 4 = TRUE
  158.                                              * R[4-1] = array[q+j]
  159.                                              * R[4-1] = array[3+4]
  160.                                              * R[3]   = array[7]
  161.                                              * j++ = 5
  162.                                              *
  163.                                              * j = 5
  164.                                              * if 5 <= 5 = FALSE
  165.                                              * END LOOP
  166.                                              */
  167.                                            
  168.                                             //         0        1        2        3      4          L.length = 5
  169.                                             // L = [ a[0] ] [ a[1] ] [ a[2] ] [ a[3] ] [ oo ]
  170.                                             //         4        5        6        7      8          R.length = 5
  171.                                             // R = [ a[4] ] [ a[5] ] [ a[6] ] [ a[7] ] [ oo ]
  172.        
  173.        
  174.                                             // Left index comparison with 0 index
  175.                                             // Right index comparison with 0 index
  176.  
  177.        
  178.        
  179.        
  180.                         //  p = 1   q = 4   r = 8   n1 = 4  L.length = 5    i = 1   R.length = 5    j = 1   k=1
  181.                         //  p = 0   q = 3   r = 7   n2 = 4  L.length = 5    i = 0   R.length = 5    j = 0   k=0
  182.        
  183.                                             /* for each index from p to r       r-p+1 = 7-0+1 = 8
  184.                                              *                     0    7       = 8 numbers
  185.                                              * if L[i] <= R[j]
  186.                                              *    A[k] = L[i]  
  187.                                              *
  188.                                              * if not
  189.                                              *    A[k] = R[j]
  190.                                              *
  191.                                              *
  192.                                              * L = [ 2 ] [ 4 ] [ 5 ] [ 7 ] [ oo ]
  193.                                              * R = [ 1 ] [ 2 ] [ 3 ] [ 6 ] [ oo ]
  194.                                              * A = [ 2 ] [ 4 ] [ 5 ] [ 7 ] [ 1 ] [ 2 ] [ 3 ] [ 6 ]
  195.                                              */
  196.  
  197.  
  198.                                             //  k = 0   j=0    i=0
  199.                                             //  if L[i] <= R[j]
  200.                                             //  if  2   <=  1      = FALSE
  201.                                             //  else    array[0] = R[0]
  202.                                             //  j++ = 1
  203.                                             //  k++ = 1
  204.  
  205.  
  206.  
  207.                                                 /*        0     1     2     3
  208.                                                  *  L = [ x ] [ 4 ] [ 5 ] [ 7 ] [ oo ]
  209.                                                  *        4     5     6     7
  210.                                                  *  R = [ x ] [ 2 ] [ 3 ] [ 6 ] [ oo ]
  211.                                                  *        0     1     2     3     4     5     6     7
  212.                                                  *  A = [ 1 ] [ 4 ] [ 5 ] [ 7 ] [ 1 ] [ 2 ] [ 3 ] [ 6 ]
  213.                                                  *  
  214.                                                  *  k = 1   i = 0   j = 1    
  215.                                                  *  if L[i] <= R[j]
  216.                                                  *  if  2   <=  2      =  TRUE
  217.                                                  *  array[1] = L[0]
  218.                                                  *  i++ = 1
  219.                                                  *  k++ = 2
  220.                                                  *  
  221.                                                  *  L = [ x ] [ 4 ] [ 5 ] [ 7 ] [ oo ]
  222.                                                  *  R = [ x ] [ 2 ] [ 3 ] [ 6 ] [ oo ]
  223.                                                  *  A = [ 1 ] [ 2 ] [ 5 ] [ 7 ] [ 1 ] [ 2 ] [ 3 ] [ 6 ]
  224.                                                  *  
  225.                                                  *  k = 2    i = 1   j = 1
  226.                                                  *  if L[i] <= R[j]
  227.                                                  *  if  4   <=  2       = FALSE
  228.                                                  *  else    array[2] = R[1]
  229.                                                  *  j++ = 2
  230.                                                  *  k++ = 3
  231.                                                  *  
  232.                                                  *  L = [ x ] [ 4 ] [ 5 ] [ 7 ] [ oo ]
  233.                                                  *  R = [ x ] [ x ] [ 3 ] [ 6 ] [ oo ]
  234.                                                  *  A = [ 1 ] [ 2 ] [ 2 ] [ 7 ] [ 1 ] [ 2 ] [ 3 ] [ 6 ]
  235.                                                  *                                                     
  236.                                                  *  k = 3    i = 1   j = 2
  237.                                                  *  if L[i] <= R[j]
  238.                                                  *  if   4  <=  3      =  FALSE
  239.                                                  *  else    array[3] = R[2]
  240.                                                  *  j++ = 3
  241.                                                  *  k++ = 4
  242.                                                  *  
  243.                                                  *  L = [ x ] [ x ] [ 5 ] [ 7 ] [ oo ]
  244.                                                  *  R = [ x ] [ x ] [ x ] [ 6 ] [ oo ]
  245.                                                  *  A = [ 1 ] [ 2 ] [ 2 ] [ 3 ] [ 4 ] [ 2 ] [ 3 ] [ 6 ]
  246.                                                  *  
  247.                                                  *                                                     
  248.                                                  *  k = 4    i = 1   j = 3
  249.                                                  *  if L[i] <= R[j]
  250.                                                  *  if  4   <=  6      =  TRUE
  251.                                                  *  array[4] = L[1]
  252.                                                  *  i++ = 2
  253.                                                  *  k++ = 5
  254.                                                  *  
  255.                                                  *  L = [ x ] [ x ] [ x ] [ 7 ] [ oo ]
  256.                                                  *  R = [ x ] [ x ] [ x ] [ 6 ] [ oo ]
  257.                                                  *  A = [ 1 ] [ 2 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 3 ] [ 6 ]
  258.                                                  *  
  259.                                                  *  k = 5    i = 2   j = 3
  260.                                                  *  if L[i] <= R[j]
  261.                                                  *  if  5   <=  6      =  TRUE
  262.                                                  *  array[5] = L[2]
  263.                                                  *  i++ = 3
  264.                                                  *  k++ = 6
  265.                                                  *  
  266.                                                  *  L = [ x ] [ x ] [ x ] [ x ] [ oo ]
  267.                                                  *  R = [ x ] [ x ] [ x ] [ 6 ] [ oo ]
  268.                                                  *  A = [ 1 ] [ 2 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 7 ] [ 6 ]
  269.                                                  *  
  270.                                                  *  k = 6    i = 3   j = 3
  271.                                                  *  if L[i] <= R[j]
  272.                                                  *  if  7   <=  6      =  FALSE
  273.                                                  *  else    array[6] = R[3]
  274.                                                  *  j++ = 4
  275.                                                  *  k++ = 7
  276.                                                  *  
  277.                                                  *  L = [ x ] [ x ] [ x ] [ 7 ] [ oo ]
  278.                                                  *  R = [ x ] [ x ] [ x ] [ x ] [ oo ]
  279.                                                  *  A = [ 1 ] [ 2 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 6 ]
  280.                                                  *  
  281.                                                  *  k = 7    i = 3   j = 4
  282.                                                  *  if L[i] <= R[j]
  283.                                                  *  if  7   <=  oo      =  TRUE
  284.                                                  *  array[7] = R[4]
  285.                                                  *  i++ = 4
  286.                                                  *  k++ = 8
  287.                                                  *  
  288.                                                  *  L = [ x ] [ x ] [ x ] [ x ] [ oo ]
  289.                                                  *  R = [ x ] [ x ] [ x ] [ x ] [ oo ]
  290.                                                  *  A = [ 1 ] [ 2 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ]
  291.                                                  *  
  292.                                                  *  k = 8    i = 4   j = 4
  293.                                                  *  if L[i] <= R[j]
  294.                                                  *  if  6   <=  oo      =  TRUE
  295.                                                  *  else    array[7] = R[3]
  296.                                                  *  i++ = 5
  297.                                                  *  k++ = 9
  298.                                                  *  
  299.                                                  *  k=9
  300.                                                  *  END LOOP
  301.                                                  */
  302.            
  303.            
  304.            
  305.            
  306.            
  307.  
  308.    
  309.     /*
  310.      * n: the size of the output array
  311.      * k: the maximum value in the array
  312.      */
  313.     @SuppressWarnings("deprecation")
  314.     public static int[] generate_random_array (int n, int k) {
  315.         List<Integer> list;
  316.         int[] array;
  317.         Random rnd;
  318.        
  319.         rnd = new Random(System.currentTimeMillis());
  320.        
  321.         list = new ArrayList<Integer> ();
  322.         for (int i = 1; i <= n; i++)
  323.             list.add(new Integer(rnd.nextInt(k+1)));
  324.        
  325.         Collections.shuffle(list, rnd);
  326.        
  327.         array = new int[n];
  328.         for (int i = 0; i < n; i++)
  329.             array[i] = list.get(i).intValue();
  330.        
  331.         return array;
  332.     }
  333.    
  334.     /*
  335.      * n: the size of the output array
  336.      */
  337.     @SuppressWarnings("deprecation")
  338.     public static int[] generate_random_array (int n) {
  339.         List<Integer> list;
  340.         int[] array;
  341.        
  342.         list = new ArrayList<Integer> ();
  343.         for (int i = 1; i <= n; i++)
  344.             list.add(new Integer(i));
  345.        
  346.         Collections.shuffle(list, new Random(System.currentTimeMillis()));
  347.        
  348.         array = new int[n];
  349.         for (int i = 0; i < n; i++)
  350.             array[i] = list.get(i).intValue();
  351.        
  352.         return array;
  353.     }
  354.    
  355.     /*
  356.      * Input: an integer array
  357.      * Output: true if the array is ascending sorted, otherwise return false
  358.      */
  359.     public static boolean check_sorted (int[] array) {
  360.         for (int i = 1; i < array.length; i++) {
  361.             if (array[i-1] > array[i])
  362.                 return false;
  363.         }
  364.         return true;
  365.     }
  366.    
  367.     public static void print_array (int[] array) {
  368.         for (int i = 0; i < array.length; i++)
  369.             System.out.print(array[i] + ", ");
  370.         System.out.println();
  371.     }
  372.    
  373.     public static void main(String[] args) {
  374.         // TODO Auto-generated method stub
  375.         System.out.println("Merge sort starts ------------------");
  376.         for (int n = 100000; n <= 1000000; n=n+100000) {
  377.             int[] array = Merge_Sort.generate_random_array(n);
  378.             //Sort.print_array(array);
  379.             long t1 = System.currentTimeMillis();
  380.             array = Merge_Sort.merge_sort(array, 0, n-1);
  381.             long t2 = System.currentTimeMillis();
  382.             long t = t2 - t1;
  383.             //Sort.print_array(array);
  384.             boolean flag = Merge_Sort.check_sorted(array);
  385.             System.out.println(n + "," + t + "," + flag);
  386.             //Merge_Sort.print_array(array);
  387.             //Merge_Sort.print_array(array);
  388.  
  389.         }
  390.         System.out.println("Merge sort ends ------------------");
  391.        
  392.     }
  393.  
  394. }
  395.  
  396. /*
  397.  *
  398.  */
  399.  
  400.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!