h2. Date de iesire

In fisierul $algsort.out$ veti tipari restul impartirii sumei <tex>S=\sum_{i=1}^N {i \cdot v[i]}</tex> la numarul $123457$, unde $v[]$ este vectorul celor $N$ numere sortate in ordine crescatoare (si indexate incepand cu pozitia $1$). Pentru detalii despre calculul acestei sume, consultati sectiunea $Observatii$.

In fisierul $algsort.out$ veti tipari restul impartirii sumei <tex>S=\sum_{i=1}^N {i \cdot v[i]}</tex> la numarul $23456789$, unde $v[]$ este vectorul celor $N$ numere sortate in ordine crescatoare (si indexate incepand cu pozitia $1$). Pentru detalii despre calculul acestei sume, consultati sectiunea $Observatii$.

h2. Restrictii

|_. i | 1 | 2 | 3 | 4 | 5 |
|_. v[i] | 1 | 3 | 4 | 5 | 7 |

Astfel, <tex>S=1 \cdot 1 + 2 \cdot 3 + 3 \cdot 4 + 4 \cdot 5 + 5 \cdot 7=74</tex>, iar restul impartirii acestui numar la $123457$ este tot $74$.

Astfel, <tex>S=1 \cdot 1 + 2 \cdot 3 + 3 \cdot 4 + 4 \cdot 5 + 5 \cdot 7=74</tex>, iar restul impartirii acestui numar la $23456789$ este tot $74$.

h2. Observatii

h3. Scrierea rezultatelor

Fisierul de iesire nu va contine toate numerele afisate in ordine crescatoare deoarece dimensiunea lui ar creste foarte mult si, odata cu aceasta, si timpul de executie al programului. Astfel, cea mai mare parte a timpului alocat pentru executie ar fi ocupat de scrierea informatiilor in fisier, si nu de algoritm in sine. Din acest motiv, dupa ce vectorul de numere (il vom nota cu $v$) va fi sortat, va trebui calculata si tiparita suma $S$ conform cerintei. Valoarea acestei sume poate fi foarte mare, iesind din tipurile standard de date, iar pentru calculul ei ne vom folosi de faptul ca nu avem nevoie decat de restul impartirii ei la numarul $123457$:

Fisierul de iesire nu va contine toate numerele afisate in ordine crescatoare deoarece dimensiunea lui ar creste foarte mult si, odata cu aceasta, si timpul de executie al programului. Astfel, cea mai mare parte a timpului alocat pentru executie ar fi ocupat de scrierea informatiilor in fisier, si nu de algoritm in sine. Din acest motiv, dupa ce vectorul de numere (il vom nota cu $v$) va fi sortat, va trebui calculata si tiparita suma $S$ conform cerintei. Valoarea acestei sume poate fi foarte mare, iesind din tipurile standard de date, iar pentru calculul ei ne vom folosi de faptul ca nu avem nevoie decat de restul impartirii ei la numarul $23456789$.
 
Acest numar este prim si mai mare decat valoarea maxima a lui $N$, in asa fel incat <tex>i \mod 23456789 \neq 0</tex>, pentru orice <tex>1 \leq i \leq N</tex>. De asemenea, niciun numar nenul din datele de test nu este divizibil cu $23456789$, asigurandu-ne astfel ca fost ales ca <tex>i \cdot v[i] \mod 23456789 \neq 0</tex>, pentru toate valorile <tex>\theta < i \leq N</tex>, unde <tex>\theta</tex> este numarul de elemente egale cu $0$ (care, dupa sortare, vor fi plasate la inceputul vectorului $v$). Daca, dimpotriva, ar fi existat astfel de produse divizibile la $23456789$, atunci elementele de pe pozitiile care le corespund ar fi putut fi schimbate oricum intre ele, fara sa modifice valoarea finala a rezultatului; in consecinta, un vector incorect sortat ar fi produs mai usor o valoare $S$ ce ar fi fost evaluata drept raspuns corect.
 
Calcularea valorii $S mod 23456789$ poate fi facuta pas cu pas (dupa soratea vectorului), folosind urmatoarea metoda, pe care o vom prezenta in pseudocod:

==code(c) |
S <- 0
pentru i <- 1, N

	S <- (S + i*v[i]) mod 123457

	S <- (S + i*v[i]) mod 23456789

sfarsit pentru
==

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

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/234849?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/234850?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/234851?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':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).

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.