Problema Saptamanii - Interclasare (solutie)

[•Cosmin]

Aici puteti comenta la http://infoarena.ro/blog/problema-saptamanii-interclasare-solutie

[•mpatrascu]

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.

[•Cosmin]

Iti promovezi articolul . 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.