ulvis.paste.net

Paste Search Dynamic
Recent pastes
Array
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.         public static void main (string[] args) throws java.lang.exception
  11.         {
  12.  
  13.         int test[] = {2, 5, 6, 2, 6, 8, 10, 1, 1, 3};
  14.         int[][] max = maxsplit(maxsort(test));
  15.         system.out.println(arrays.deepToString(max));
  16.  
  17.  
  18.     }
  19.     /*
  20.         T(n) = 2T(n/2) + n
  21.         T(n/2) = 2T(n/4) + n/2
  22.         T(n)= 2{2T(n/4) + n/2} + n
  23.         T(n)=2^k T(n/2^k) + k * n
  24.         n = 2^k => n/2^k = 1
  25.         2^k = lg(n) = k
  26.         = 2lg(n)T(1)+lg(n) * n
  27.         = n + nlog(n)
  28.         = O(nlog(n))
  29.      */
  30.     public static int[] maxsort(int[] input) {
  31.         int N = input.length;                 // Array size = n
  32.         if (N <= 1) return input;
  33.         int[] a = new int[N / 2];
  34.         int[] b = new int[N - N / 2];
  35.         for (int i = 0; i < a.length; i++)    // Array split = n/2
  36.             a[i] = input[i];
  37.         for (int i = 0; i < b.length; i++)    // Array split = n/2
  38.             b[i] = input[i + N / 2];
  39.         return maxmerge(maxsort(a), maxsort(b));
  40.     }
  41.  
  42.     private static int[] maxmerge(int[] a, int[] b) {
  43.         int[] c = new int[a.length + b.length];
  44.         int i = 0, j = 0;
  45.         for (int k = 0; k < c.length; k++) {
  46.             if (i >= a.length) c[k] = b[j++];
  47.             else if (j >= b.length) c[k] = a[i++];
  48.             else if (a[i] >= b[j]) c[k] = a[i++];
  49.             else c[k] = b[j++];
  50.         }
  51.         return c;
  52.     }
  53.  
  54.     private static int[][] maxsplit(int[] input) {
  55.         int N = input.length;
  56.         int k = 0;                              // C == O(1)
  57.         int[][] max = new int[2][N / 2];
  58.         for (int i = 0; i < 2; i++) {           // C == O(1)
  59.             for (int j = 0; j < N / 2; j++) {   // C == O(n)
  60.                 max[i][j] = input[k++];
  61.             }
  62.         }
  63.         return max;
  64.     }
  65.  
  66.  
Parsed in 0.113 seconds