Sortare

[•ILDottore]

Care este cel mai bun algoritm de sortare ? Quicksort,bubble sort etc..?

[•SpiderMan]

Cel mai usor si unul dintre cele mai eficiente este sortul din STL. Mai sunt radixsort, countingsort, mai multe detalii http://infoarena.ro/problema/algsort.

[•ILDottore]

Multumesc pentru raspunsul prompt

[•S7012MY]

Un algoritm destul de bun pentru sortare e quicksort-ul aleator. Uite aici o sursa: http://infoarena.ro/job_detail/450035?action=view-source

Gasesti in cormen explicatii

[•scipianus]

In libraria standard a limbajului C este implementata o varianta naiva de Quicksort (poate fi apelata prin qsort(...) - o sursa demonstrativa gasiti aici), iar STL-ul ofera programatorilor C++ atat functia sort, o implementare a algoritmului Introsort (o sursa demonstrativa aici), cat si functiile make_heap si sort_heap, pentru a putea implementa usor Heapsort (sursa demonstrativa aici). De asemenea, o varianta scurta de implementare a algoritmului Merge Sort (inspirata din acest articol) puteti gasi aici.

Eu pana acum foloseam ca metoda de sortare functia sort din STL pentru orice tip de sortare de genul sort(a,a+n,Ordonare()),unde la functia Ordonare fac ordonare dupa ce criterii doresc.
Din ce scrie sus aflu deci ca mai exista qsort si cele 2 functii pentru heapsort.Pana la urma care dintre sort,qsort si heapsort prin STL,este mai rapida ?  

[•nparfene2004]

Din cate stiu eu, dintre sortarile bazate pe comparatii:
locul 1 : RadixSort
locul 2 : Heap-sort - O(n log n) pe toate cazurile
locul 3 : QuickSort (sau poate Shell Sort ??)

[•SpiderMan]

Aici sunt prezentati timpii pentru fiecare algoritm in parte .

[•robert.badea]

Îmi spune și mie de ce toată lumea crede că QuickSort este un algoritm foarte rapid? Doar după nume? Are worst case n² și best n log n ceea ce mie mi se pare incredibil de mult.

PS: Nu zic de voi, dar cer* o explicație, poate am înțeles eu greșit.

[•pauldb]

E important la quicksort ca are complexitatea timp medie O(NlogN), constanta mica, memorie suplimentara doar O(log(N)) si e simplu de implementat. Iar la varianta cu pivotul random, nu se poate construi a priori un test pe care complexitatea timp sa fie O(N^2), desi posibilitatea ca algoritmul sa ruleze in aceasta complexitate exista.

[•robert.badea]

Ar fi o posibilitate și mai mică (aproape imposibilă) dacă înainte de quickSort s-ar amesteca elementele din vector, cred, dar asta 99,99% distruge best-case-ul (dacă există).

De mergeSort cu listă înlănțuită ce părere ai(aveți)?

Și nu în ultimu rând, mă ajută și pe mine cineva cu radixSortul? La implementare, algoritmu de a sorta după cifra unităților, zecilor, etc poate fi care vreau eu?

[•pauldb]

Mergesort cu lista inlantuita e util doar in cazul in care sortezi structuri mai complexe. Daca sortezi doar intregi, pointerii pe care ii tii la lista ocupa la fel de multa memorie ca un vector suplimentar. Din ce am testat eu cand eram in liceu, quicksort-ul randomizat merge putin mai bine ca mergesort-ul.

La RadixSort e eficient sa folosesti sortare prin numarare deoarece cifrele sunt pana in 10.

[•wefgef]

@nparfene: Radix nu e sortare prin comparare pentru ca nu compara elementele vectorului intre ele.

@robert.badea: Lumea considera quicksort rapid pentru ca in practica s-a dovedit a fi foarte bun. Sunt sanse muuult mai mari sa castigi la loto decat sa mearga quicksort prost. Poti gasi pe net demonstratiile matematice.

Problema cu mergesort e ca are prea multa memorie suplimentara.