radixsort

Radix Sort

== include(page="template/taskheader" task_id="radixsort") ==

Poveste şi cerinţă...

Se dau $N$ numere naturale, intr-o ordine oarecare, si se cere sortarea lor in ordine crescatoare.

h2. Date de intrare

Fişierul de intrare $radixsort.in$ ...

Fişierul de intrare $radixsort.in$ va avea pe prima linie numerele $N$, $A$, $B$ si $C$ separate prin cate un spatiu.
Cele N numere se vor genera dupa urmatoarea formula:
$v[i] = B$, pentru i = 1
$v[i] = (A * v[i-1] + B) % C$, pentru $2 ≤ i ≤ N$

h2. Date de ieşire

În fişierul de ieşire $radixsort.out$ ...

În fişierul de ieşire $radixsort.out$ se vor tipari pe prima linie numerele generate de pe pozitiile $1, 11, 21, 31, ...$ (din 10 in 10) in ordine crescatoare, separate printr-un singur spatiu.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 10 000 000$
* Toate cele $N$ numere vor fi cuprinse intre $0$ si $2^31^-1$ inclusiv.

h2. Exemplu
table(example). |_. radixsort.in |_. radixsort.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 100 12 38 123
| 2 14 23 38 50 59 71 80 98 110

|

h3. Explicaţie

h3. Indicatii de rezolvare

...

Structura problemei cere implementarea algoritmului de sortare 'Radix Sort':http://en.wikipedia.org/wiki/Radix_sort, fiindca numerele sunt naturale.
 
Complexitatea lui este <tex>\mathit{O} \left( kN \right)</tex>, unde k este lungimea medie a numerelor sau <tex>\mathit{O} \left( N \cdot W/\log N \right)</tex>, unde $W$ este marimea in biti a word-ului calculatorului (32 pentru int; explicatia 'aici':http://rgrig.blogspot.ro/2008/08/sorting-out-stuff.html).
 
Acest algoritm nu se bazeaza pe comparatii deci nu este restrictionat de limita <tex>\Omega \left( N \cdot \log N \right)</tex> precum 'Merge Sort':http://en.wikipedia.org/wiki/Merge_sort sau 'Quick Sort':http://en.wikipedia.org/wiki/Quicksort
 
O solutie bazata pe comparatii, folosind functia std::sort() obtine aproximativ 30 de puncte.
 
O sursa de 100 de puncte se gaseste 'aici':job_detail/1091503?action=view-source. Aceasta solutie se bazeaza pe 'Counting Sort':en.wikipedia.org/wiki/Counting_sort, care are complexitatea <tex>\mathit{O} \left( N \right)</tex> dar este limitat de faptul ca foloseste memorie suplimentara egala cu maximul dintre numere, care poate ajunge la $2^31^-1$ in acest caz. Astfel impartim numerele in $4$ bucket-uri de cate un byte (pe care le numim "cifre") si le sortam incepand cu cea mai putin semnificativa.
 
Pentru mai multe detalii si un studiu comparativ al algoritmilor de sortare vizitati 'pagina Wikipedia dedicata acestui subiect':http://en.wikipedia.org/wiki/Sorting_algorithm.
 
h3. Aplicatii
 
* 'Practical Applications of Radix Sort':http://cs.stackexchange.com/a/12228
* Vezi aplicatiile de 'aici':/problema/algsort

== include(page="template/taskfooter" task_id="radixsort") ==

9572