|
Titlul: Sortare Scris de: Bogdan Stoian din Ianuarie 31, 2011, 17:28:30 Care este cel mai bun algoritm de sortare ? Quicksort,bubble sort etc..?
Titlul: Răspuns: Sortare Scris de: Simoiu Robert din Ianuarie 31, 2011, 17:48:23 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.
Titlul: Răspuns: Sortare Scris de: Bogdan Stoian din Ianuarie 31, 2011, 17:54:53 Multumesc pentru raspunsul prompt :)
Titlul: Răspuns: Sortare Scris de: Petru Trimbitas din Ianuarie 31, 2011, 18:22:51 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 Titlul: Răspuns: Sortare Scris de: FMI Ciprian Olariu din Ianuarie 31, 2011, 19:31:50 Citat 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 ? :) Titlul: Răspuns: Sortare Scris de: Parfene Narcis din Ianuarie 31, 2011, 22:08:21 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 ??) Titlul: Răspuns: Sortare Scris de: Simoiu Robert din Ianuarie 31, 2011, 22:39:45 Aici (http://en.wikipedia.org/wiki/Sorting_algorithm) sunt prezentati timpii pentru fiecare algoritm in parte ;).
Titlul: Răspuns: Sortare Scris de: Robert Badea din Februarie 04, 2011, 19:42:55 Îmi spune și mie de ce toată lumea crede că QuickSort este un algoritm foarte rapid? Doar după nume? Are worst case n2 ș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. Titlul: Răspuns: Sortare Scris de: Paul-Dan Baltescu din Februarie 04, 2011, 20:46:49 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.
Titlul: Răspuns: Sortare Scris de: Robert Badea din Februarie 04, 2011, 21:17:49 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? Titlul: Răspuns: Sortare Scris de: Paul-Dan Baltescu din Februarie 05, 2011, 00:33:39 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. Titlul: Răspuns: Sortare Scris de: Andrei Grigorean din Februarie 20, 2011, 01:33:10 @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. |