Sortare prin comparare directa

Sortare prin comparare

table(example).
|_. algsort.in |_. algsort.out |

| 5

| 6

4 1 7 5 1 3 | 1 1 3 4 5 7 |
h2. Observatii

Structura problemei cere implementarea unui 'algoritm de sortare pe baza de comparatii':http://en.wikipedia.org/wiki/Comparison_sort. Exista, de asemenea, algoritmi de sortare care nu compara explicit elementele si care au performante mai bune pentru anumite cazuri particulare ale structurii datelor de intrare; acestia nu se preteaza insa cerintelor impuse in cazul de fata.

Orice algoritm de sortare bazat pe comparatii trebuie sa efectueze, pentru a putea distinge corect toate cele <tex>N!</tex> permutari posibile ale sirului de valori, <tex>\Omega \left( N \cdot \log N \right)</tex> comparatii (o justificare a acestui rezultat se afla 'aici':http://www.cs.utexas.edu/~vlr/s07.357/notes/lb-apr5.pdf). Din aceasta perspectiva, algoritmi precum 'Merge Sort':http://en.wikipedia.org/wiki/Merge_sort, 'Heapsort':http://en.wikipedia.org/wiki/Heapsort sau 'Introsort':http://en.wikipedia.org/wiki/Introsort sunt optimi, executand <tex>\Theta \left( N \cdot \log N \right)</tex> operatii in cazul cel mai defavorabil. Dintre acestia, Merge Sort foloseste <tex>\mathit{O}\left( N \right)</tex> memorie suplimentara in implementarea clasica, deci nu se va incadra in restrictiile problemei.

Orice algoritm de sortare bazat pe comparatii trebuie sa efectueze, pentru a putea distinge corect toate cele <tex>N!</tex> permutari posibile ale sirului de valori, <tex>\Omega \left( N \cdot \log N \right)</tex> comparatii (o justificare a acestui rezultat se afla 'aici':http://www.cs.utexas.edu/~vlr/s07.357/notes/lb-apr5.pdf). Din aceasta perspectiva, algoritmi precum 'Merge Sort':http://en.wikipedia.org/wiki/Merge_sort, 'Heapsort':http://en.wikipedia.org/wiki/Heapsort sau 'Introsort':http://en.wikipedia.org/wiki/Introsort sunt optimi, executand <tex>\Theta \left( N \cdot \log N \right)</tex> operatii in cazul cel mai defavorabil. Dintre acestia, Merge Sort foloseste <tex>\mathit{O}\left( N \right)</tex> memorie suplimentara in implementarea clasica.

Un alt algoritm de sortare foarte popular este 'Quicksort':http://en.wikipedia.org/wiki/Quicksort. Desi complexitatea sa pentru cazul cel mai defavorabil este <tex>\mathit{O}\left( N^2 \right)</tex>, in practica se comporta foarte bine si cunoaste multe imbunatatiri (detalii in prezentarea profesorului Robert Sedgewick 'aici':http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf si a profesorului Jon Bentley 'aici':blog/three-beautiful-quicksorts).

h2. Aplicatii

Sortarea datelor apare ca subproblema sau etapa intermediara intr-o larga varietate de probleme si algoritmi, fiind considerata astfel una dintre temele principale de studiu in informatica teoretica. Diverse strategii greedy cu aplicatii in planificarea activitatilor, determinarea arborilor partiali de cost minim ('algoritmul lui Kruskal':http://en.wikipedia.org/wiki/Kruskal's_algorithm) sau constructia 'codurilor Huffman':http://en.wikipedia.org/wiki/Huffman_coding, implica o prima etapa de sortare a datelor. De asemenea, in geometria computationala intalnim sortarea punctelor dupa unghiul polar pentru determinarea 'infasuratorii convexe':problema/infasuratoare, sau metoda 'dreptei de baleiere':http://en.wikipedia.org/wiki/Sweep_line, care presupune sortarea punctelor-eveniment dupa anumite criterii.

Sortarea datelor apare ca subproblema sau etapa intermediara intr-o larga varietate de probleme si algoritmi, fiind considerata astfel una dintre temele principale de studiu in informatica teoretica. Diverse strategii greedy cu aplicatii in planificarea activitatilor, determinarea 'arborilor partiali de cost minim':problema/apm ({'algoritmul lui Kruskal':http://en.wikipedia.org/wiki/Kruskal's_algorithm}) sau constructia 'codurilor Huffman':http://en.wikipedia.org/wiki/Huffman_coding, implica o prima etapa de sortare a datelor. De asemenea, in geometria computationala intalnim sortarea punctelor dupa unghiul polar pentru determinarea 'infasuratorii convexe':problema/infasuratoare sau metoda 'dreptei de baleiere':http://en.wikipedia.org/wiki/Sweep_line, care presupune sortarea punctelor-eveniment dupa anumite criterii.

Alte probleme in care este folosita (intr-o forma sau alta) sortarea datelor:

* 'loto':problema/loto
* 'cutii':problema/cutii
* 'cai':problema/cai

* 'Loto':problema/loto
* 'Reactivi':problema/reactivi
* "Akbardin’s Roads":http://acm.timus.ru/problem.aspx?space=1&num=1178
* 'Granita':problema/granita
* 'Lungimi de interval':problema/linterv
* 'Sport':problema/sport
* "Rooks":http://acm.sgu.ru/problem.php?contest=0&problem=269
* 'Cai':problema/cai
* "Inversions":http://acm.sgu.ru/problem.php?contest=0&problem=180
* 'Cutii':problema/cutii
* 'Invsort':problema/invsort
* 'Mexc':problema/mexc
* 'Demolish':problema/demolish
* "Wolves and Sheep":http://acm.sgu.ru/problem.php?contest=0&problem=349
* "Antenna":http://www.hsin.hr/ceoi2006/tasks/day1/antenna.pdf, _CEOI 2006_
* "Sails":http://hsin.hr/ioi2007/tasks/day1/sails.pdf, _IOI 2007_

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

3513

3547