Отправляет email-рассылки с помощью сервиса Sendsay

Разбор классических алгоритмов и олимпиадных задач.

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 977 RSS
←   Июль 2005   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Открыта: 01-08-2004

Автор
ferrik

Статистика

977 подписчиков
0 за неделю
←   Все выпуски   →

Разбор классических алгоритмов и олимпиадных задач. Сортировка слияниям.


Информационный Канал Subscribe.Ru

Здравствуйте.
Я предлагаю Вам решить задачу, расположенную по адресу http://acm.timus.ru/problem.aspx?space=1&num=1207.


Сортировка слияниям.

Сортировка слияниям принадлежит к классу алгоритмов O(N logN) и не имеет худших случаев. Она более наглядна, чем быстрая сортировка. При сортировке используется алгоритм двухпутевого слияния, который мы сейчас рассмотрим. Допустим, у нас есть два отсортированных массива, а нам надо создать массив, содержащий все элементы первого и второго массива в отсортированном виде. Можно скопировать элементы обоих массивов в новый и применить алгоритм сортировки, но при таком подходе мы не используем то, что массивы отсортированы. Есть решение за линейное время, и оно достаточно простое. Надо сравнивать элементы в вершинах массивов и больший (если Вы сортируете по невозростанию) перемещать в результирующий массив пока один из массивов не опустеет. После этого все элементы из непустого массива надо добавить к результирующему. Повторюсь, алгоритм достаточно прост и наверняка Вы встречались с ним в жизни.

Сортировка слиянием делит исходный массив на две части. Затем они рекурсивно сортируются и сливаются. Как и в случае с быстрой сортировкой большинство рекурсивных вызовов приходится на маленькие списки. Гораздо эффективнее сортировать их вставками. 

procedure MergeSort(_L,_R:integer); 
var 
  m,i,j,k,c:integer; 
begin 
  if _R-_L<16 then // для маленьких массивов 
  begin 
    InsertionSort(_L,_R); // сортировка вставками 
    exit; 
  end;   m:=(_L+_R) div 2; 
  if _L<m then 
    MergeSort(_L,m); 
  if _R>m+1 then 
    MergeSort(m+1,_R); 
  //Слияние двух отсортированных массивов 
  i:=_L; 
  j:=m+1; 
  c:=_L; 
  while (i<=m)and(j<=_R) do 
  begin 
    if a[i]>a[j] then 
    begin 
      b[c]:=a[j]; 
      inc(j); 
    end else 
    begin 
      b[c]:=a[i]; 
      inc(i); 
    end; 
    inc(c); 
  end; 
  if m>=i then 
    System.Move(a[i],b[c],SizeOf(a[0])*(m-i+1)) 
  else   System.Move(a[j],b[c],SizeOf(a[0])*(_R-j+1)); 
  //Перемещаем получившийся массив 
  System.Move(b[_L],a[_L],SizeOf(a[0])*(_R-_L+1)); 
end;
Если необходимо, то копировать массивы можно и поэлементно.

В общем случае сортировка слияниям медленнее быстрой сортировки и чуть быстрее пирамидальной. При этом ей требуется дополнительная память пропорциональная N. Конечно, можно реализовать этот алгоритм так, что он будет требовать в 2 раза меньше памяти, но я это делать не стану.

Сортировка слияниям используется для сортировки больших массивов не помищающихся в память.

Замеры, мс
Кол-во 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536
Bubble 0.0025 0.0085 0.0323 0.1293 0.5214 2.0936 8.3018 32.793 130.88 532.87 2151.6 8685.4 47761
Shaker 0.0025 0.0080 0.0282 0.1092 0.4288 1.6955 6.7565 26.718 106.15 426.11 1716.6 6896.2 30936
Selection 0.0024 0.0070 0.0222 0.0772 0.2831 1.0826 4.1964 16.536 65.508 263.50 1054.2 4213.4 19436
Insertion 0.0012 0.0034 0.0114 0.0416 0.1588 0.6169 2.4413 9.7193 38.740 154.76 618.77 2474.2 13597
InsertionO 0.0013 0.0033 0.0099 0.0338 0.1238 0.4723 1.8481 7.3261 29.112 116.23 463.99 1855.5 11466
QuickSort 0.0027 0.0062 0.0137 0.0300 0.0650 0.1400 0.3000 0.6400 1.3600 2.9000 6.1400 13.000 28.100
QuickSortO 0.0016 0.0040 0.0092 0.0210 0.0468 0.1000 0.2250 0.4910 1.0600 2.2800 4.8700 10.410 23.270
HeapSort 0.0027 0.0061 0.0136 0.0305 0.0678 0.1493 0.3261 0.7000 1.5400 3.3800 7.4100 15.930 37.570
MergeSort 0.0015 0.0042 0.0104 0.0251 0.0571 0.1290 0.2871 0.6339 1.3996 3.0379 6.9225 15.633 35.464

Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора 		Подписан адрес:
Код этой рассылки: comp.soft.prog.fprogram 		Отписаться
Вспомнить пароль
В избранное