Ако съществуват алгоритми за линейно сортиране по време като Radix Sort, кога трябва да използваме сортиране за сравнение?

Тъй като всички алгоритми за сортиране при сравнение отнемат поне n lg n време, защо изобщо ще трябва да използваме нещо като бързо сортиране, когато можем да изразим елементите в списъка за бързо сортиране като битове и използвайки нещо като радикално сортиране, което е линейно?


sorting algorithm comparison
person Alkorizm    schedule 01.10.2014    source източник
comment
Защото не всичко може да бъде правилно сравнено само чрез сравняване на неговите части. Например моята логика за foo1 < foo2 прави някаква сложна логика.   -  person AndyG    schedule 01.10.2014
comment
Но плаващата запетая е просто 32 бита, така че казвате ли, че за по-ниски числа бързото сортиране е по-добро, въпреки че, разбира се, асимптотично не е?   -  person Alkorizm    schedule 01.10.2014
comment
Разбирам, но не можахте да направите някакъв целочислен ключ за вашата логика? Това няма ли да свърши работа?   -  person Alkorizm    schedule 01.10.2014
comment
Би било излишно, ако трябва да преизчислите ключа предвид контекста на ситуацията, което много добре може да се случи. Въпросът е, че побитовото сортиране не може да се приложи към всяка ситуация.   -  person AndyG    schedule 01.10.2014
comment
дубликат на дубликат на дубликат на дубликат на....   -  person Karoly Horvath    schedule 01.10.2014
comment
Вашият въпрос показва фундаментална липса на разбиране за това как работи радикалното сортиране и как се различава от сортирането при сравнение. Трябва да прочетете съответните статии в Уикипедия и да следвате препратките. Започнете тук: en.wikipedia.org/wiki/Radix_sort   -  person Jim Mischel    schedule 01.10.2014
comment
Трябва да отбележа, че linear е правилно, но подвеждащо. Radix сортирането може да използва невероятно количество памет, ако обработвате всеки обект само с неговите битове; друга често цитирана причина да се използват сортирания за сравнение, дори когато елементите могат да бъдат сортирани със сортиране без сравнение.   -  person AndyG    schedule 01.10.2014

Отговори (2)


arrow_upward
2
arrow_downward

Radix сортирането има тенденция да показва лоша локалност на кеша, вижте например този документ за анализ на различни алгоритми за сортиране под влиянието на кеша (преминете към заключението за обсъждане на лошото местоположение на кеша на радикалното сортиране в сравнение с бързото сортиране и сортирането чрез сливане). Quicksort и mergesort разделят данните така, че след няколко итерации дялът ще се побере на няколко реда на кеша, докато радикалното сортиране продължава да разбърква данните. В допълнение, радикалното сортиране или трябва да използва свързани структури от данни за своите кофи (които показват лоша производителност на кеша), или в противен случай трябва да използва прекалено големи масиви (които губят памет).

Също така, в зависимост от размера на радикса на сортирането по принцип, неговият постоянен коефициент може да бъде по-голям от коефициента на журнал на бързото сортиране/сливането. В краен случай, използвайки радикс от 2 на 64-битови цели числа, радикалното сортиране има постоянен коефициент 64 (едно преминаване на бит), докато е много малко вероятно коефициентът на дневника на бързото сортиране / сливането да е толкова голям (тъй като това би означавало, че вие сортирате 2^64 елемента)

person Zim-Zam O'Pootertoot    schedule 01.10.2014
comment
Втората ви точка е особено ясна, когато елементите не са скаларни стойности. Представете си, че се опитвате да използвате радикално сортиране върху масив от низове от 100 знака. - person Jim Mischel; 01.10.2014
comment
Тук обсъждате само скапани имплементации на LSD радикален сорт. Доброто внедряване на MSD радикално сортиране няма нито един от проблемите, които предлагате за равномерно разпределени входове. - person tmyklebu; 01.10.2014
comment
@JimMischel: Както се случва, радикалното сортиране е това, което хората използват, за да сортират големи масиви от низове от 100 знака. (Или поне да го разделите на куп масиви, достатъчно кратки, че сортирането в кеша да е подходящо.) - person tmyklebu; 01.10.2014

arrow_upward
1
arrow_downward

Съвременните реализации на mergesort, използващи SIMD ядро ​​за сортиране на кратки масиви, могат да бъдат много, много бързи. Тази статия от някои хора от Intel описва едно такова изпълнение. Основното предимство тук е, че SIMD ядрото може да прави няколко сравнения и суапове на тактов цикъл, като получава и се възползва от няколко бита информация за масива, който трябва да се сортира за тактов цикъл.

Бързото сортиране изисква тест, магазин и увеличение на един от два указателя при всяка итерация, което образува една единствена огромна верига на зависимости. Това не е страхотно, тъй като означава, че получавате един бит информация за масива на всеки няколко такта.

Radix сортирането има същия проблем като Quicksort (всяко преминаване е една огромна верига на зависимост с достъп и увеличение на един указател от голям, равномерно разпределен набор). Въпреки това, при равномерно разпределени входове, правилно внедрено MSD радикално сортиране, използващо пет- или шест-битови ключове, може да направи с едно преминаване през входа това, за което Quicksort ще отнеме пет или шест преминавания. Не съм измервал времето на тези неща наскоро, но доброто сортиране по радикс на MSD все още може да бъде най-добрият начин за сортиране на големи масиви от ints или long longs.

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

person tmyklebu    schedule 01.10.2014