fork(1) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4. import java.util.Arrays;
  5. import java.util.Random;
  6.  
  7. class ThanosMeanArrays 
  8. {   // Сортирует на месте (перезаписывает исходный массив)
  9.     public static void thanosSortInPlace(int[] a) 
  10.     { if (a == null || a.length < 2) return;
  11.         int[] sorted = sortCopy(a);
  12.         System.arraycopy(sorted, 0, a, 0, a.length);
  13.     }
  14.  
  15.     // Сортирует Double на месте (перезаписывает исходный массив)
  16.     public static void thanosDSortInPlace(double[] a) 
  17.     { if (a == null || a.length < 2) return;
  18.         double[] sorted = sortDoubleCopy(a);
  19.         System.arraycopy(sorted, 0, a, 0, a.length);
  20.     }
  21.  
  22.     // Рекурсия на подмассивах: 
  23.     // сегмент -> (left,right) -> sort(left), sort(right) -> concat
  24.     private static int[] sortCopy(int[] seg)  
  25.     {   int n = seg.length;
  26.         if (n < 2) return Arrays.copyOf(seg, n);
  27.  
  28.         // Быстрый выход: все элементы равны
  29.         int mn = seg[0], mx = seg[0];
  30.         long sum = seg[0];
  31.  
  32.         for (int i = 1; i < n; i++) 
  33.         { int v = seg[i];
  34.             if (v < mn) mn = v;
  35.             if (v > mx) mx = v;
  36.             sum += v;
  37.         }
  38.  
  39.         if (mn == mx) return Arrays.copyOf(seg, n);
  40.  
  41.         // Среднее текущего сегмента
  42.         double c = sum / (double) n;
  43.  
  44.         // Подсчёт размеров левой и правой частей
  45.         int cntL = 0, cntR = 0;
  46.         for (int v : seg) if (v <= c) cntL++; else cntR++;
  47.  
  48.         // Заполняем подмассивы
  49.         int[] left = new int[cntL];
  50.         int[] right = new int[cntR];
  51.         int iL = 0, iR = 0;
  52.  
  53.         for (int v : seg) 
  54.         { if (v <= c) left[iL++] = v;
  55.             else        right[iR++] = v;
  56.         }
  57.  
  58.         // Рекурсия на подмассивах
  59.         left  = sortCopy(left);
  60.         right = sortCopy(right);
  61.  
  62.         // Склейка
  63.         int[] out = new int[n];
  64.         System.arraycopy(left,  0, out, 0, left.length);
  65.         System.arraycopy(right, 0, out, left.length, right.length);
  66.         return out;
  67.     }
  68.  
  69.     // Рекурсия на подмассивах: 
  70.     // сегмент -> (left,right) -> sort(left), sort(right) -> concat
  71.     private static double[] sortDoubleCopy(double[] seg) 
  72.     { int n = seg.length;
  73.         if (n < 2) return Arrays.copyOf(seg, n);
  74.  
  75.         // Быстрый выход: все элементы равны
  76.         double mn = seg[0], mx = seg[0];
  77.         double sum = seg[0];
  78.  
  79.         for (int i = 1; i < n; i++) 
  80.         { double v = seg[i];
  81.             if (v < mn) mn = v;
  82.             if (v > mx) mx = v;
  83.             sum += v;
  84.         }
  85.  
  86.         if (mn == mx) return Arrays.copyOf(seg, n);
  87.  
  88.         // Среднее текущего сегмента
  89.         double c = sum / (double) n;
  90.  
  91.         // Подсчёт размеров левой и правой частей
  92.         int cntL = 0, cntR = 0;
  93.         for (double v : seg) if (v <= c) cntL++; else cntR++;
  94.  
  95.         // Заполняем подмассивы
  96.         double[] left = new double[cntL];
  97.         double[] right = new double[cntR];
  98.         int iL = 0, iR = 0;
  99.  
  100.         for (double v : seg) 
  101.         { if (v <= c) left[iL++] = v;
  102.             else        right[iR++] = v;
  103.         }
  104.  
  105.         // Рекурсия на подмассивах
  106.         left  = sortDoubleCopy(left);
  107.         right = sortDoubleCopy(right);
  108.  
  109.         // Склейка
  110.         double[] out = new double[n];
  111.         System.arraycopy(left,  0, out, 0, left.length);
  112.         System.arraycopy(right, 0, out, left.length, right.length);
  113.         return out;
  114.     }
  115.  
  116.     //********** Универсальный random метод
  117.     public static double[] generateDoubleRandomArray(int n, double min, double max) 
  118.     {   Random rnd = new Random();
  119.         double[] arr = new double[n];
  120.  
  121.         for (int i = 0; i < n; i++) 
  122.         { arr[i] = min + rnd.nextDouble() * (max - min); // [min..max)
  123.         }
  124.         return arr;
  125.     }
  126.  
  127.     public static int[] generateRandomArray(int n, int min, int max) 
  128.     {   Random rnd = new Random();
  129.         int[] arr = new int[n];
  130.  
  131.         for (int i = 0; i < n; i++) 
  132.         {  arr[i] = rnd.nextInt(max - min + 1) + min; // [min..max]
  133.         }
  134.         return arr;
  135.     }
  136.  
  137.     public static void main(String[] args) 
  138.     {   int[] x = {5, 1, 9, 3, 7, 2, 2, 8, 4, 6};
  139.         thanosSortInPlace(x);
  140.         System.out.println(Arrays.toString(x));
  141.  
  142.         int[] arr = generateRandomArray(15, -100, 100);
  143.         System.out.println("arr  before : " + Arrays.toString(arr));
  144.         int[] t1 = arr.clone();
  145.         System.out.println("start Main int test code watch.");
  146.         long t0 = System.nanoTime();
  147.         thanosSortInPlace(t1);
  148.          long t1n = System.nanoTime();
  149.          System.out.println("stop watch.");
  150.         System.out.printf("Thanos main int test code : %.2f ms%n", (t1n - t0) / 1e6);
  151.         System.out.println("arr  sorted : " + Arrays.toString(t1));
  152.  
  153.         double[] arrD = generateDoubleRandomArray(15, -1, 1);
  154.         System.out.println("arrD before : " + Arrays.toString(arrD));
  155.         double[] t2 = arrD.clone();
  156.         System.out.println("start Double test code watch.");
  157.         long t02 = System.nanoTime();
  158.         thanosDSortInPlace(t2);
  159.         long t2n = System.nanoTime();
  160.          System.out.println("stop watch.");
  161.         System.out.printf("Thanos Double test code : %.2f ms%n", (t2n - t02) / 1e6);
  162.         System.out.println("arrD sorted : " + Arrays.toString(t2));
  163.     }
  164. }
  165.  
Success #stdin #stdout 0.19s 56044KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[1, 2, 2, 3, 4, 5, 6, 7, 8, 9]
arr  before : [93, 89, 6, 13, 74, -88, -11, 31, 74, -83, 95, -21, -53, 52, -20]
start Main int test code watch.
stop watch.
Thanos main int test code : 0.03 ms
arr  sorted : [-88, -83, -53, -21, -20, -11, 6, 13, 31, 52, 74, 74, 89, 93, 95]
arrD before : [0.6800104072533404, 0.07291683325767684, 0.21628499708186855, -0.15596442837652402, -0.5165938189068717, -0.316702929056216, 0.20921295721284183, -0.6644994418387442, 0.5453002798606512, 0.0783697656815876, -0.7820284653553933, -0.6024217303397832, -0.923865478976482, -0.2960337952357992, -0.23349649685742202]
start Double test code watch.
stop watch.
Thanos Double test code : 0.05 ms
arrD sorted : [-0.923865478976482, -0.7820284653553933, -0.6644994418387442, -0.6024217303397832, -0.5165938189068717, -0.316702929056216, -0.2960337952357992, -0.23349649685742202, -0.15596442837652402, 0.07291683325767684, 0.0783697656815876, 0.20921295721284183, 0.21628499708186855, 0.5453002798606512, 0.6800104072533404]
https://ideone.com/Zqo70c
RuSortPol java
language:
Java (12.0.1)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!