Как да сортираме

    Тук няма да разглеждаме и доказваме алгоритми за сортиране. Целта на статията е да ви покаже какво да правите, ако трябва да сортирате. Самата тя е нещо като алгоритъм за програмисти, които трябва да сортират някакъв масив.

Сортиране по честоти
Първото което трябва да проверите е дали условията ви позволяват да сортирате нещото по честоти. Този метод е чудесен, защото е с линейна скорост. За съжаление използва много памет. Въпреки това ако скоростта е важна и можете да си го позволите, не се колебайте. Изпълнението на програмата скача с пъти!

Смисълът на този метод е да индексираме със стойностите. Получаваме нещо като хеш-таблица, само че не хешираме нищо. За да можем да си позволим сортиране по части, трябва масива да е от цели числа, за които имаме горна и долна граница. Например ако имаме масив от цели числа, в който знаем, че всяко е от 0 до 10000. Ето един пример, който всички С, С++, С# и Java програмисти би трябвало да разберат.

Сортираме масив ar[N]:

  1. int* arHelper = new int[10000]; //помощен масив
  2. memset(arHelper, 0, 10000*sizeof(int)); //нулираме стойностите в помощния масив
  3. for(i=0; i<N; ++i)
  4.     ++arHelper[ar[i]];
  5.  
  6. //в този момент arHelper[j] съдържа
  7. //броя елементи със стойност j от масива ar
  8.  
  9. int k=0;
  10. for(i=0; i<10000; ++i)
  11.     for(int j=0; j<arHelper[i]; ++j)
  12.         ar[k++]=i; //запълваме масива с подходящи стойности.

Както виждате скоростта е линейна. Функцията е 2*N+MAX-MIN, където N e размера на сортирания масив, MAX е максималната възможна стойност а MIN е минималната (в гореописания случай 10000 и 0). Освен това метода е стабилен.

Естествено, при малък размер на входния масив опрацията няма особен смисъл. Ако сортираме масив от 10 елемента със максимум 10000, скоростта на сортирането по честоти, ще е най-бавната възможна. За това зравнявайте горната формула с N*log(N), преди да го ползвате.


Стабилно сортиране
По нагоре споменахме че сортирането по честоти е стабилно. Това означава че запазва първоначалната подредба на елементите. Например, ако имаме структура от буква и число, която е сортирана по числото:
1а 2г 2а 2х 3х 3г 4д 4а 8а 8х 8г
ако я сортираме със стабилно сортиране по буква, ще получим:
1а 2а 4а 8а 2г 3г 8г 4д 2х 3х 8х

Забележете, че първоначалния ред (1 2 4 8) в елементите, които съдържат `а` се е запазил. Както и в при другите елементи от масива. При нестабилното сортиране, нищо не ни гарантира, че това ще е така.

За това, ако решите, че не можете да си позволите сортиране по честоти, се замислете дали ви трябва стабилно сортиране. Ако - да, ще сте принудени да използвате бавен алгоритъм за сортиране.

Стабилни методи, освен сортирането по честоти са: метод на мехурчето, сортиране чрез клатене и сортиране чрез пряка селекция. Те са изключително близки и не случайно са от семейство Мехурче. Може би най-добри резултати от тях дава клатенето. Ето една негова реализация.

отново сортираме ar[N]:

  1. int left=0, right=N-1, i;
  2. while(left<right)
  3. {
  4.     int k=0;
  5.     for(i=left; i<right; ++i)
  6.         if(ar[i+1] < ar[i])
  7.             {
  8.                 swap(ar[i], ar[i+1]);
  9.                 k=i;
  10.             }
  11.     right = k;
  12.     k = n-1;
  13.     for(i=right; i>left; --i)
  14.         if(ar[i-1] > ar[i])
  15.         {
  16.             swap(ar[i], ar[i+1]);
  17.             k=i;
  18.         }
  19.  
  20.     left = k;
  21. }

В методът на мехурчето, елементите се разделят условно на мехурчета (големи стойности на малки позиции) и камъчета (малки стойности на големи позиции). Мехурчетата вървят нагоре а камъчетата надолу. Методът на мехурчето е неефективен в масив с много камъчета като този:
200 212 2445 3217 3939 2 2737 8533 3 8288

Сортирането чрез клатене нормализира разместванията и работи добре за всякакви масиви.

Сега, ако отговорът на въпроса, дали търсим стабилно сортиране е "не", време е да пристъпим към един много красив метод.


Бързо сортиране

Бързото сортиране на английския математик Хоор (още известно като quick sort, qsort, Hoar sort), е метод, който статистически дава отлични резултати. Естествено, не е идеален и понякога работи бавно, но ако нямате точна представа за входа е най-добрият избор.

Аз няма да опиша реализация на този алгоритъм. Хиляди книги предлагат такава. Ще кажа нещо друго. Ако опрете до бързото сортиране ползвайте библиотечни функции. Всеки език предлага такава.

    * C: qsort - <stdlib.h>
    * C++: std::sort - <algorithm>
    * Java: Arrays.sort - java.util
    * С#: Array.sort - System.Collections

Няма защо да си играете да пишете функция. Хората, писали библиотеката си знаят работата и вашето творение може да е само по-лошо.

Други нестабилни методи са: сортировка на Шел, пирамидално сортиране, сортиране чрез вмъкване.

В крайна сметка, когато ви трябва сортиране ползвайте Честоти, ако можете, ако не и не ви трябва стабилен метод ползвайте библиотечна функция за бързо сортиране, ако ви трябва стабилно със сълзи на очи си напишете нещо от семейство мехурчеви. И това е.

Автор: Борислав Станимиров