|
Titlul: Problema Saptamanii - Interclasare (solutie) Scris de: Cosmin Negruseri din August 14, 2010, 10:52:19 Aici puteti comenta la http://infoarena.ro/blog/problema-saptamanii-interclasare-solutie
Titlul: Răspuns: Problema Saptamanii - Interclasare (solutie) Scris de: Mihai Patrascu din August 14, 2010, 17:54:01 O abordare generală pentru a sorta fără spaţiu suplimentar se găseşte la: http://people.csail.mit.edu/mip/papers/radix/arxiv.pdf
Vezi paginile 2-5 (sunt vreo 3 algoritmi separaţi). Până la urmă nu e aşa greu, dar nici nu e complet trivial. Ideea e că poţi să economiseşti Θ(n lg n) biţi de spaţiu dacă ai n numere sortate. Spaţiu ăsta e aproape suficient ca să stochezi o permutare, care e fix tot ce-ţi trebuie. Chiar am implementat algoritmul cam într-o oră (cu ceva concentrare :). Dar nu e algoritm de concurs. Titlul: Răspuns: Problema Saptamanii - Interclasare (solutie) Scris de: Cosmin Negruseri din August 15, 2010, 15:00:01 Iti promovezi articolul :P. Destul de misto ca se lucreaza asa recent(2007) la probleme fundamentale si se fac progrese cu idei jmechere dar nu super complicate.
Eu cand eram curios de problema asta citisem ceva din paperul Optimal Stable Merging ce poate fi gasit aici http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.862 Cred ca cheile din algoritmul respectiv nu au nevoie sa fie intregi, si unul din trucurile folosite este acela de a inversa doua secvente AB -> BA folosind memorie suplimentara constanta. |