h2. Observatii

Limita de timp impusa este de $500 ms$, din care, pentru testele maxime, intre $150$ si $300 ms$ vor fi ocupate de citirea datelor. *Nu* este necesara folosirea functiilor specializate de citire a blocurilor de caractere (parsarea citirii) pentru a obtine punctajul maxim, insa recomandam folosirea stream-urilor C++, care se comporta mai bine in mediul de evaluare decat functiile de citire din libraria standard C.

In analiza comportamentului surselor evaluate trebuie sa tineti cont de faptul ca cea mai mare parte a timpului de executie va fi ocupata de citirea si scrierea datelor in fisier (pentru testele maxime, intre $400$ si $600 ms$ vor fi ocupate de operatiile de intrare/iesire). *Nu* este necesara folosirea functiilor specializate de citire a blocurilor de caractere (parsarea citirii) pentru a obtine punctajul maxim, insa recomandam folosirea stream-urilor C++, care se comporta mai bine in mediul de evaluare decat functiile de citire din libraria standard C.

h3. Structura testelor

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.

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':http://infoarena.ro/blog/three-beautiful-quicksorts).

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).

In libraria standard a limbajului C este implementata o varianta naiva de Quicksort (poate fi apelata prin $qsort(...)$ - o sursa demonstrativa gasiti 'aici':http://infoarena.ro/job_detail/235029?action=view-source), iar STL-ul ofera programatorilor C++ atat functia $sort$, o implementare a algoritmului Introsort (o sursa demonstrativa 'aici':http://infoarena.ro/job_detail/235027?action=view-source), cat si functiile $make_heap$ si $sort_heap$, pentru a putea implementa usor Heapsort (sursa demonstrativa 'aici':http://infoarena.ro/job_detail/235030?action=view-source).

In libraria standard a limbajului C este implementata o varianta naiva de Quicksort (poate fi apelata prin $qsort(...)$ - o sursa demonstrativa gasiti 'aici':job_detail/239877?action=view-source), iar STL-ul ofera programatorilor C++ atat functia $sort$, o implementare a algoritmului Introsort (o sursa demonstrativa 'aici':job_detail/239875?action=view-source), cat si functiile $make_heap$ si $sort_heap$, pentru a putea implementa usor Heapsort (sursa demonstrativa 'aici':job_detail/239880?action=view-source). De asemenea, o varianta scurta de implementare a algoritmului Merge Sort (inspirata din acest 'articol':multe-smenuri-de-programare-in-cc-si-nu-numai) puteti gasi 'aici':job_detail/239878?action=view-source.

Alti algoritmi neoptimi, ce ruleaza in cazul mediu in complexitate <tex>\mathit{O}\left( N^2 \right)</tex>, dar elementari si foarte usor de inteles sunt: "Bubblesort":http://en.wikipedia.org/wiki/Bubble_sort, "Selection Sort":http://en.wikipedia.org/wiki/Selection_sort si "Insertion Sort":http://en.wikipedia.org/wiki/Insertion_sort.