1. Начало
  2. Архив
  3. C# Programming
  4. Структури данни и алгоритми
  5. [DSA] Алгоритъм за сортиране с линейна сложност

[DSA] Алгоритъм за сортиране с линейна сложност

2

Намерих този алгоритъм случайно и много ме впечатли.
Нарича се Radix sort и научих за него от тази статия: http://forums.bgdev.org/index.php?showtopic=22740

Каква е идеята:
Алгоритъма подрежда елементите по битовете на някакви прости стойности (букви, интове и тн). Сложен е за имплементиране, но е ужасно бърз.

Сложността му е О(n*length) където length е дължината на битовете на това което сортирате. Съответно ако сортирате по интове сложността ще е n*32 докато ако сортирате по long ще е n*64.

Уловката е че алгоритъма всъщност не сравнява обекти, а битове. На него не му пука дали класа ви има IComparable. Ако не му дадете прост вид стойност по която да подрежда, той е неприложим.

За повече информация прочетете статията.

Споделете други интересни алгоритми на които сте попадали.

в Структури данни и алгоритми от lokiko91 (790 точки)
dsa radix sort алгоритъм побитов сорт съвети

Отговори


2

Здравей, 

всъщност има и по-бърз алгоритъм за сортиране.

Нека имаме 100 000 000 студенти, искаме да ги сортираме по години. Кое е най-бързото, ефективно и заемащо най-малко памет решение? 

Сложността му е O(N), а заемащата памет е приблизително O(N * Y), където Y e 32 или 64 бита Pointer за адресация при използване на клас (ако е структура, паметта е повече), може да работи без сравнение на елементите и имплементацията му е значително проста, това е Bucket Sort (кофите). 

Как може да се използва в случая - имаме критерии години, ако кажем че долната и горната граница са в интервала [0; 100], това означава, че ще имаме 1 масив от тип T с дължина 100 и с едно обхождане ще ги имаме сортирани по години.

от martin.nikolov (4535 точки)

0
средния случай би-могъл да е по-бърз, но най-лошия е многократно по-бавен. Ситуация в която е по-бърз ще е ситуация в която сравняваш числа в малки граници (примерно всички да са е[0;100]). В такива ситуации обаче (ако имаш гаранция че наистина ще имаш числа в тази граница) можеш да прочетеш само част от битовете с Radix sort (само битовете които формират числата в тази граница) и той отново ще е по-бързия.
Освен това сложността която написах за Radix sort беше най-бавния случай. Най добрия случай е О(n+length).
от lokiko91 (790 точки)
0
Bucket sort е алгоритъм, който е бърз само когато редицата ни се състои от малък брой многократно повтарящи се елементи.
от stambeto09 (425 точки)
Зареди още коментари


2

"Съответно ако сортирате по интове сложността ще е n*32 докато ако сортирате по long ще е n*64."
Виждаш ли уловката? Сметни кога N*32 < N*log(N), и картинката ще ти се изясни :)
Аз като го смятам ... ще е ефективен при над 1 млрд елемента. Аре ... 1 млн да са, щото тук и коефициентите ще имат значение (а те при мърдж и куик сорта не са много малки).
Но пък идва момента ... ако ще сравняваш само по 16 бита... това в сравнение с counting sort с 65536 брояча пак ще е по-бавно.
А да правиш сметки така, че да натикаш 32 бита (да не говорим за нещо по-сложно като структура) в 16 - там пък си вдигаш коефициента.
Така че ... може да има някакъв специфичен сегмент, в който да е приложим този начин, но не е нищо особено и най-вероятно ще се намери алгоритъм, който да е бърз поне колкото него.

от JulianG (5316 точки)