daily pastebin goal
2%
SHARE
TWEET

Untitled

chavit Jun 6th, 2011 715 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.IOException;
  2. import java.util.Arrays;
  3. import java.util.Random;
  4.  
  5. public class Main {
  6.  
  7.  
  8.     // сляние двух групп елементов одинокового размера
  9.     void mergegroup(int a[], int n, int st1, int st2, int st3) {
  10.       swapgroup(a, n, st1, st3);
  11.                 int take1 = 0;
  12.                 int take2 = 0;
  13.                 for (int i = 0; i < 2 * n; i++) {
  14.                         if ((take2 == n) || ((take1 < n) && (a[take1 + st3] < a[take2 + st2]))) {
  15.                                 int t = a[st1 + i];
  16.                                 a[st1 + i] = a[take1 + st3];
  17.                                 a[take1 + st3] = t;
  18.                                 take1++;
  19.                         } else {
  20.                                 int t = a[st1 + i];
  21.                                 a[st1 + i] = a[take2 + st2];
  22.                                 a[take2 + st2] = t;
  23.                                 take2++;
  24.                         }
  25.                 }
  26.         }
  27.  
  28.  
  29.         // сортировка выбором
  30.         void slowsort(int a[], int st, int en) {
  31.                 for (int i = st; i < en; i++)
  32.                         for (int j = i + 1; j < en; j++) {
  33.                                 if (a[i] > a[j]) {
  34.                                         int k = a[i];
  35.                                         a[i] = a[j];
  36.                                         a[j] = k;
  37.                                 }
  38.                         }
  39.         }
  40.  
  41.  
  42.         // обмен местами двух групп елементов одинакового размера    
  43.         void swapgroup(int a[], int n, int st1, int st2) {
  44.                 for (int i = 0; i < n; i++) {
  45.                         int k = a[st1 + i];
  46.                         a[st1 + i] = a[st2 + i];
  47.                         a[st2 + i] = k;
  48.                 }
  49.         }
  50.  
  51.  
  52.         //слияние
  53.         void merge(int[] a, int n) {
  54.                 if (n <= 16) {
  55.                         slowsort(a, 0, n);
  56.                         return;
  57.                 }
  58.                
  59.                 // разрез на группы длиной корень из n
  60.                 int sizegroup = (int) Math.sqrt(n);
  61.                 int remainder = n % sizegroup;
  62.                 int numofgrp = n / sizegroup - 1;
  63.                
  64.                 // поиск конца первого массива
  65.                 int posgap = 0;
  66.                 while ((posgap < sizegroup * numofgrp) && (a[posgap] <= a[posgap + 1]))
  67.                         posgap++;
  68.                        
  69.                 // обмен группы содержащей конец первого массива  с последней и обьединение с остатком
  70.                 swapgroup(a, sizegroup, numofgrp * sizegroup, posgap - posgap
  71.                                 % sizegroup);
  72.                 remainder += sizegroup;
  73.                
  74.                 // сортировка групп по первому елементу(в случае равенства по последнему)
  75.                 for (int i = 0; i < numofgrp - 1; i++) {
  76.                         int minnum = i;
  77.                         for (int j = i + 1; j < numofgrp; j++)
  78.                                 if ((a[j * sizegroup] < a[minnum * sizegroup])
  79.                                         || ((a[j * sizegroup] == a[minnum * sizegroup])
  80.                                         && (a[(j + 1) * sizegroup - 1] < a[(minnum + 1) *sizegroup-1])))
  81.                                       minnum = j;
  82.                         swapgroup(a, sizegroup, i * sizegroup, minnum * sizegroup);
  83.                 }
  84.                
  85.                 // поочередное слияние групп
  86.                 for (int i = 0; i < numofgrp - 1; i++) {
  87.                         mergegroup(a, sizegroup, i * sizegroup, (i + 1) * sizegroup,
  88.                                         numofgrp * sizegroup);
  89.                 }
  90.                
  91.                 // сортировка конца массива
  92.                 slowsort(a, n - 2 * remainder, n);
  93.                
  94.                 // поочередное слияние групп в обратную сторону
  95.                 for (int i = n - 2 * remainder; i >= remainder; i -= remainder)
  96.                         mergegroup(a, remainder, i - remainder, i, n - remainder);
  97.                        
  98.                 // сортировка начала и конца массива
  99.                 slowsort(a, 0, 2 * remainder);
  100.                 slowsort(a, n - remainder, n);
  101.         }
  102.  
  103.         // сортировка
  104.         void sort(int[] a) {
  105.                 int n = a.length;
  106.                 for (int stp2 = 1; stp2 <= n; stp2 *= 2)
  107.                         for (int i = 0; i < n; i += stp2) {
  108.                                 int size = Math.min(n, i + stp2) - i;  
  109.                                 swapgroup(a, size, 0, i);      // для удобства реализации перемещаем  
  110.                                 merge(a, size);                // требуемый кусок масcива в начало
  111.                                 swapgroup(a, size, 0, i);      // там его сортируем и возвращаем обратно
  112.                         }
  113.                 if (n > 16)
  114.                         merge(a, n);
  115.  
  116.         }
  117.  
  118.  
  119.         void testsort() throws IOException {
  120.                 int n = 100000;
  121.                 int[] a = new int[n];
  122.                 Random st = new Random();
  123.                 for (int i = 0; i < n; i++)
  124.                         a[i] = st.nextInt();
  125.                 int[] b = a.clone();
  126.                 Arrays.sort(b);
  127.                 sort(a);
  128.                 for (int i = 0; i < n; i++)
  129.                         if (a[i] != b[i])
  130.                                 throw new AssertionError();
  131.         };
  132.  
  133.  
  134.         void run() throws IOException {
  135.                 for (int i = 0; i < 10; i++) {
  136.                         testsort();
  137.                 }
  138.         }
  139.  
  140.  
  141.         public static void main(String[] args) throws IOException {
  142.                 new Main().run();
  143.         }
  144. }
RAW Paste Data
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
 
Top