Анализ методов сортировки одномерного массива

      На  наступному кроці після копіювання в масив B зливаються пари упорядкованих  ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки  довжиною 4. Нехай t=nmod4 – довжина  залишку масиву після останньої  повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t.

      Кроки повторюються з подвоєнням довжин упорядкованих  ділянок lp, поки lp < n.

      Розглянемо  сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n=11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";":

      < <11><10> ; <9><8> ; <7><6> ; <5><4> ; <3><2> ; <1> >, lp=1

      < <10, 11><8, 9> ; <6, 7><4, 5> ; <2, 3><1> >, lp=2

      < <8, 9, 10, 11><4, 5, 6, 7>;<1, 2, 3> >, lp=4

      < <4, 5, 6, 7, 8, 9, 10, 11><1, 2, 3> >, lp=8

      <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp=16, lp³ n.

      Як  бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив.

      Такий спосіб сортування описується процедурою Mrgsort:

      procedure Mrgsort (var A : ArT; n : Indx);

      var B : ArT; lp, npp, cpp, bpp, tl : integer;

      begin

      lp := 1;

      while lp < n do

      begin

      B := A; { копіювання }

      npp := n div (2*lp); { кількість пар ділянок  }

      tl := n mod (2*lp); { довжина залишку }

      for cpp := 1 to npp do { cpp – номер пари }

      begin

      bpp := (cpp - 1)*2*lp + 1;

      { індекс першого елемента лівої  ділянки пари}

      mrg ( B, bpp, lp, lp, A );

      end;

      { обробка залишку }

      if tl > lp then

      mrg ( B, n - tl + 1, lp, tl - lp, A );

      { за tl <= lp залишок був упорядкований  }

      { на попередньому кроці }

      lp := lp*2

      end

      { lp >= n : масив упорядковано на  останньому кроці }

      end

      Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1<n, то при виконанні останнього кроку мають місце співвідношення

      lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp,

      і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.

      Оцінимо складність наведеного алгоритму. При  кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад  по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+ë log2nû =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn).

      Запишемо  в таблицю значення виразів n, n(n-1)/2, n(1+log₂n ) та округлене відношення r двох останніх:

      Як  бачимо, кожне зростання n у 10 разів  веде до зростання n(n-1)/2 та n(1+log₂n) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове!

      Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … – злиття в протилежному напрямку. Переробка алгоритму залишається вправою.

      Сортування  злиттям можна задати рекурсивно: масив поділяється на дві приблизно  рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини  масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний:

      procedure Mrgrec(var A, B : ArT; l, r : integer);

      var m, k : integer;

      begin

      if l>=r then exit;

      m:=(l+r) div 2;

      Mrgrec(A, B, l, m); Mrgrec(A, B, m+1,r);

      mrg(A, l, m-l+1, r-m, B);

      for k:=l to r do A[k]:=B[k];

      end;

      Ця  процедура набагато коротше нерекурсивної  процедури Merges, але виконання її довше. Власне сортування починається  лише після повернення з викликів, у яких l=r, а це практично "середина дистанції".

      Завершуючи  описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.

      Серйозним недоліком цього алгоритму є  необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два – ні. 
 

      1.9 Удосконалені алгоритми сортування. Сортування Шелла 

      Усі розглянуті дотепер алгоритми сортування мають дуже серйозний недолік, а саме, час їхнього виконання пропорційно квадратові числа елементів.

        Для великих обсягів даних  ці сортування будуть повільними, а починаючи з деякої величини, вони будуть занадто повільними, щоб їх можна було використовувати  на практиці. Кожен програміст чув або розповідав "страшні" історії про "сортування, що виконувалася три дні". На жаль, ці історії часто не були вигадкою.

      Якщо  сортування виконується занадто  довго, то причиною цього може бути використовуваний алгоритм. Розглянемо два дуже гарні сортування. Перше зветься сортування Шелла, а друге називається швидким сортуванням, алгоритм якого визнаний найкращим. Ці сортування виконуються дуже швидко.

      Сортування  Шелла одержав свою назву по імені  його творця Д.Л.Шелла. Однак, цю назву можна вважати вдалою, тому що виконувані при сортуванні дії нагадують укладення морських черепашок одну на одну.

      Загальний метод, що використовує сортування включенням, застосовує принцип зменшення відстані між порівнюваними елементами. Нижче  показана схема виконання сортування Шелла для масиву "f d a c b e". Спочатку сортуються всі елементи, що зміщені друг від друга на три позиції. Потім сортуються всі елементи, що зміщені на двох позицій. І, нарешті, упорядковуються всі сусідні елементи:

      прохід 1                        f   d   a   c   b   e

      прохід 2           c   b   a   f   d   e

      прохід 3          a   b   c   e   d   f

      отриманий результат   a   b   c   d   e   f

      Алгоритм:

      { сортування Шелла }

      procedure Shell(var item: DataArray; count:integer);

      const

        t = 5;

      var

        i, j, k, s, m: integer;

        h: array[1..t] of integer;

        x: DataItem;

      begin

      h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;

      for m := 1 to t do

      begin

      k:=h[m];

      s:=-k;

      for i := k+1 to count do

      begin

      x := item[i];

      j := i-k;

      if s=0 then

      begin

      s := -k;

      s := s+1;

      item[s] := x;

      end;

      while (x<item[j]) and (j<count) do

      begin

      item[j+k] := item[j];

       j := j-k;

      end;

      item[j+k] := x;

      end;

      end;

      end; { кінець сортування Шелла }

      При поверхневому погляді на алгоритм не можна сказати, що він дає гарний результат і навіть те, що в результаті вийде відсортований масив. Однак, він дає і те й інше. Ефективність цього алгоритму пояснюється  тим, що при кожному проході використовується відносно невелике число елементів або елементи масиву вже знаходяться у відносному порядку, а упорядкованість збільшується при кожному новому перегляді даних.

      Відстані  між порівнюваними елементами можуть змінюватися по-різному. Обов'язковим є лише те, що останній крок повинний дорівнювати одиниці. Наприклад, гарні результати дає послідовність кроків 9, 5, 3, 2, 1, що використана в показаному вище прикладі. Варто уникати послідовностей ступеня двійки, що, як показують складні математичні викладення, знижують ефективність алгоритму сортування. (Однак, при використанні таких послідовностей кроків між порівнюваними елементами це сортування буде як і раніше працювати правильно).

      Внутрішній  цикл має дві умови перевірки. Умова "х<item[j]" необхідна для упорядкування елементів. Умови "j>0" і "j<=count" необхідні для того, щоб запобігти вихід за межі масиву "item". Ця додаткова перевірка до деякої міри погіршує сортування Шелла. Злегка змінені версії сортування Шелла використовують спеціальні керуючі елементи, що не є в дійсності частиною тієї інформації, що повинна сортуватися. Елементи, що управляють, мають граничні для масиву даних значення, тобто найменше і найбільше значення. У цьому випадку не обов'язково виконувати перевірку на граничні значення. Однак, застосування таких керуючих елементів вимагає спеціальних знань про ту інформацію, що сортується, і це знижує універсальність процедури сортування.

      Аналіз  сортування Шелла вимагає рішення  деяких складних математичних задач. Час  виконання сортування Шелла пропорційно n. Ця залежність значно краще квадратичної залежності, який підкоряються розглянуті раніше алгоритми сортування. Однак, перш ніж ви вирішите використовувати сортування Шелла, варто мати на увазі, що швидке сортування дає навіть ще кращі результати.  

      1.10 Метод поділу (алгоритм "швидкого" сортування, метод Хоара) 

      Метод швидкого сортування був розроблений  Ч. Ф. Р. Хоаром і він же дав йому цю назву. В даний час цей метод  сортування вважається найкращим. Він  заснований на використанні обмінного методу сортування. Це тим більше дивно, якщо врахувати дуже низьку швидкодію сортування бульбашковим методом, що являє собою найпростішу версію обмінного сортування.

      В основі швидкого сортування лежить принцип  розбивки. Спочатку вибирається деяке значення в якості "основи" і потім весь масив розбивається на дві частини. Одну частину складають всі елементи, рівні або більше "основи", а іншу частину складають всі елементи меншого значення, по якому робиться розбивка. Цей процес продовжується для частин, що залишилися, доти, поки весь масив не буде відсортований. Наприклад, для масиву "fedacb" при використанні як значення розбивки "d" будуть отримані наступні проходи при виконанні швидкого сортування: