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

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

      var

      i,j : integer;

      x : DataItem;

      begin

      for i := 2 to count do

       begin

       for j := count downto i do

       if item[j-1]>item[j] then

       begin

       x := item[j-1];

       item[j-1] := item[j];

       item[j] := x;

        end;

        end;

      end; {кінець сортування бульбашковим  методом}

      У цьому випадку дане "item" є  масивом елементів "DataItem", що сортується, а дане "count" містить число  елементів у масиві.

      Сортування  бульбашковим методом мають два  цикли. Оскільки число елементів масиву задається перемінної "count", зовнішній цикл викликає перегляд масиву count - 1 раз. Це забезпечує перебування кожного елемента у своєї позицій після завершення процедури. Внутрішній цикл призначений для фактичного виконання операцій порівняння й обміну.

      Для ілюстрації роботи сортування бульбашковим методом нижче подані результати кожного етапу сортування масиву "dcab":

      вихідне положення:   d c a b;

      перший  прохід:        a d c b;

      другий  прохід:        a b d c;

      третій  прохід:        a b c d.

      При аналізі всякого сортування визначається число операцій порівняння й обміну, виконаних у кращому, середньому і гіршому випадках. Для сортування бульбашковим методом число порівнянь  залишається незмінним, оскільки два  цикли завжди виконуються задане число раз поза залежністю від упорядкованості вихідного масиву. Це означає, що при сортуванні бульбашковим методом завжди виконується 1/2 (n²-n) операцій порівняння, де "n" задає число сортируемых елементів масиву. Ця формула виводиться на тій підставі, що зовнішній цикл сортування бульбашковим методом виконується n-1 раз, а внутрішній цикл виконується n/2 разів. Їхнє перемножування дасть зазначену формулу. Число операцій обміну буде нульовим для найкращого випадку, коли вихідний масив уже є відсортованим. Число операцій обміну для середнього випадку буде дорівнює 3/4 (n²-n), а для найгіршого випадку буде дорівнює 3/2 (n²-n) раз. Можна помітити, що в міру погіршення упорядкованості вихідного масиву число неупорядкованих елементів наближається до числа порівнянь (кожен неупорядкований елемент вимагає три операції обміну). Сортування бульбашковим методом називають квадратичним алгоритмом, оскільки час його виконання пропорційно квадратові числа сортуємих елементів. Сортування великого числа елементів бульбашковим методом вимогає дуже багато часу, тому що час виконання сортування знаходиться в квадратичній залежності від числа елементів масиву. Наприклад, якщо не враховувати час операцій обміну, виконуваних для перестановки неупорядкованих елементів, то тоді при виконанні однієї операції порівняння протягом 0,001 секунд сортування десяти елементів займе 0,05 секунд, сортування ста елементів займе 5 секунд, а сортування 1000 елементів займе 500 секунд. Сортування 100 000 елементів (такий розмір має невеликий телефонний довідник) вимогала б 5 000 000 секунд або близько 1400 годин (тобто два місяці безперервної роботи)!   Сортування бульбашковим методом можна до деякої міри поліпшити і тим самим небагато поліпшити її тимчасові характеристики. Можна, наприклад, помітити, що сортування бульбашковим методом володіє одною особливістю: розташований не на своєму місці (наприкінці) масиву елемент (наприклад, елемент "а" у масиві "dcab") досягає свого місця за один прохід, а елемент, розташований на початку масиву (наприклад, елемент "d"), дуже повільно досягає свого місця. Необов'язково всі перегляди робити в одному напрямку. Замість цього всякий наступний перегляд можна робити в протилежному напрямку. В цьому випадку сильно віддалені від свого місця елементи швидко переміщатимуться у відповідне місце. Нижче показана поліпшена версія сортування бульбашковим методом, що одержав назву "човникового сортування" через відповідний характер рухів по масиву.

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

      {човникове  сортування є поліпшеною версією  сортування бульбашковим методом}

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

      var

      j, k, l, r: integer;

      x: DataItem;

      begin

      l := 2; r := count; k := count;

      repeat

      for j := r downto l do

      if item[j-1] then

      begin    { обмін }

      x := item[j-1];

      item[j-1] := item[j];

      item[j] := x;

      k := j;

      end;

      l := k+1;

      for j := l to r do

      if item[j-1]>item[j] then

      begin   { обмін }

      x := item[j-1];

      item[j-1] := item[j];

      item[j] := x;

      k := j;

      end;

      r := k-1;

      until l>r

      end; {кінець човникового сортування} 

      1.6 Сортування вибором елемента 

      При сортуванні вибором вибирається  елемент із найменшим значенням  і робиться його обмін з першим елементом масиву. Потім знаходиться  елемент із найменшим значенням  із що залишилися n-1 елементів і робиться його обмін із другим елементом і  т.д. до обміну двох останніх елементів. Наприклад, якщо сортування вибором застосувати для масиву "bdac", те будуть отримані наступні проходи:

      вихідне положення:   b d a c;

      перший  прохід:        a d b c;

      другий  прохід:        a b b c;

      третій  прохід:        a b c d.

        На жаль як і в сортуванні бульбашковим методом зовнішній цикл виконується n-1 раз, а внутрішній цикл виконується n/2 разів. Це значить, що число порівнянь для сортування вибором дорівнює 1/2 (n²-n) і це сортування буде виконуватися занадто повільно для великого числа елементів. Число операцій обміну в найкращому випадку дорівнює 3(n-1), а в гіршому випадку дорівнює n²/4+3(n-1). У кращому випадку (коли вихідний масив вже упорядкований) буде потрібно поміняти місцями тільки n-1 елементів, а кожна операція обміну вимагає три операції пересилання.

      {сортування  вибором}

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

      var

      i, j, k: integer;

      x: DataItem;

      begin

      for i := i to count-1 do

      begin

      k := i;

      x := item[i];

      for j := і+1 to count do {знайти елемент із  найменшим значенням}

      if item[j]<x then

      begin

      k := j;

      x := item[j];

      end;

      item[k] := item[і];  {обмін}

      item[і] := x;

      end;

      end; {кінець сортування вибором}

      У середньому число операцій обміну дорівнює n(ln+y), де "y" є константою Эйлера, приблизно рівної 0,577216. Це значить, що незважаючи на однакове число операцій порівнянь для сортувань бульбашковим методом і сортувань вибором, число операцій обміну для середнього випадку буде значно меншим для сортування вибором.  

      1.7 Сортування включенням 

      Сортування  включенням є останньою з класу простих алгоритмів сортування.  При сортуванні включенням спочатку упорядковуються два елементи масиву. Потім робиться включення третього елемента у відповідне місце стосовно перших двох елементів.

      Цей процес повторюється доти, поки всі елементи не будуть упорядковані. Наприклад, для масиву "dcab" сортування включенням буде проходити в такий спосіб:

      вихідне положення:   d c a b;

      перший  прохід:        c d a b;

      другий  прохід:        a c d b; 

      третій  прохід:        a b c d.

      Нижче приводиться алгоритм сортування включенням:

      { сортування включенням }

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

      var

      i, l: integer;

      x: DataItem;

      begin

      for i := 2 to count do

      begin

      x := item[i];

      j := i-1;

      while (x<item[j]) and (j>0) do

      begin

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

      j := j-1;

      end;

      item[j+1] := x;

      end;

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

      На  відміну від сортування бульбашковим методом і сортування вибором  число операцій порівняння для сортування включенням залежить від вихідної упорядкованості  масиву елементів. Якщо вихідний масив вже упорядкований, то число операцій порівняння дорівнює n-1.

      Якщо  масив упорядкований у зворотному порядку, то число операцій порівняння дорівнює 1/2 (n² +n)-1, даючи в середньому значення 1/4 (n²+n-2).

      Число операцій обміну буде наступним:

      для кращого випадку: 2 (n-1);

      у середньому: 1/4 (n²+9n-10);

      для гіршого випадку: 1/2 (n²+3n-4).

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

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

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

      1.8 Сортування злиттям

      В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву.

      Злиття  двох упорядкованих послідовностей можна порівняти з перебудовою  двох колон солдатів, вишикуваних  за зростом, в одну, де вони також  розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається – тоді решта іншої колони додається до нової.

      Нехай у масиві Y з елемента Y[m] починається  впорядкована ділянка довжиною s, а  з елемента Y[m+s] – впорядкована ділянка  довжини r. Наприклад,

      Результатом злиття повинна бути ділянка довжини r+s у масиві X:

      Таке  злиття двох ділянок у масиві Y у  ділянку масиву X задає процедура

      procedure mrg( var Y : ArT; m, s, r : Indx; var X : ArT);

      var mr, k : Indx; i, j : Extind;

      begin

      mr := m + s; { mr – початок правої частини  }

      i := m; j := mr; { i та j пробігають ліву й  праву ділянки масиву Y}

      for k := m to m + s + r - 1 do{заповнення X[m], … , X[m+s+r-1]}

      if i > m + s - 1 then

      begin X[k] := Y[j]; j := j + 1 end else

      if j > mr + r - 1 then

      begin X[k] := Y[i]; i := i + 1 end else

      if Y[i] < Y[j] then

      begin X[k] := Y[i]; i := i + 1 end else

      begin X[k] := Y[j]; j := j + 1 end

      end

      Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], … , A[n] копіюються в допоміжний масив B[1], … , B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1.