Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-21 18:27:15.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	algsort.in, algsort.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	Lucian Boca •amadaeus
Timp execuţie pe test	0.45 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	N/A

Sortare prin comparare

Se dau N numere naturale, intr-o ordine oarecare. Se pune problema sortarii lor in ordine crescatoare.

Date de intrare

Fisierul de intrare algsort.in va avea pe prima linie numarul N, iar pe a doua linie N numere naturale, separate prin cate un spatiu.

Date de iesire

In fisierul algsort.out veti tipari restul impartirii sumei $S=\sum_{i=1}^N {i \cdot v[i]}$ 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.

Restrictii

1 ≤ N ≤ 500 000
Toate cele N numere se vor fi cuprinse intre 0 si 2³¹-1 inclusiv.

Exemplu

algsort.in	algsort.out
5 4 7 5 1 3	74

Explicatie

Dupa sortare, vectorul v devine:

i	1	2	3	4	5
v[i]	1	3	4	5	7

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

Observatii

Problema sortarii eficiente a datelor impune, in conditiile de fata, cateva particularitati de evaluare pe care le vom descrie in continuare si care au fost pe care le vom descrie in continuare:

Citirea datelor

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

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:

S <- 0
pentru i <- 1, N
	S <- (S + i*v[i]) mod 123457
sfarsit pentru

Singurul detaliu la care trebuie sa mai avem grija este faptul ca rezultatul inmultirii i*v[i] poate depasi tipul de date in care se incadreaza factorii ei (intreg cu semn pe 32 de biti). De aceea, fie va trebui sa facem o conversie explicita catre un tip intreg pe 64 de biti ( long long sau int64), fie ne vom folosi de particularitatile de limbaj sau de compilator, declarand unul dintre factorii produsului ca intreg pe 64 de biti.

Structura testelor

Datorita largii varietati de algoritmi de sortare si comportarii lor diferite in functie de anumite particularitati structurale ale datelor de intrare, pentru evaluarea problemei se folosesc 5 grupe de cate 4 teste. Toate testele aflate in aceeasi grupa vor avea aceeasi valoare pentru N si acelasi domeniu de valori pentru cele N numere: $0 \le v[i] \le \lfloor N \cdot \gamma \rfloor$ , unde $\gamma = \frac{2^{31}-1}{500000}$ . Testele din cadrul fiecarei grupe se vor diferentia astfel:

primul test va contine numere generate aleator
al doilea test va contine numere "aproape sortate" (numarul de inversiuni din lista de numere este mic)
al treilea test va contine numerele sortate in ordine descrescatoare
al patrulea test va contine numerele in ordine aleatoare, insa vor exista putine perechi de numere distincte (foarte multe dintre numere vor aparea de mai multe ori in fisierul de intrare)

Limite de timp si memorie

Limitele de timp si memorie au fost alese in asa fel incat punctajul maxim sa poata fi obtinut doar de implementari bune ale unor algoritmi de sortare eficienti atat din punct de vedere al timpului de executie (complexitatea ceruta este $\mathit{O}\left( N \cdot \log N \right)$ ), cat si din punct de vedere al memoriei suplimentare folosite ( $\mathit{O}\left( \log N \right)$ memorie suplimentara admisa).

Solutie

Structura problemei cere implementarea unui algoritm de sortare pe baza de comparatii. 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 $N!$ permutari posibile ale sirului de valori, $\Omega \left( N \cdot \log N \right)$ comparatii (o justificare a acestui rezultat se afla aici). Din aceasta perspectiva, algoritmi precum Merge Sort, Heapsort sau Introsort sunt optimi, executand $\Theta \left( N \cdot \log N \right)$ operatii in cazul cel mai defavorabil. Dintre acestia, Merge Sort foloseste $\mathit{O}\left( N \right)$ memorie suplimentara in implementarea clasica, deci nu se va incadra in restrictiile problemei.

Un alt algoritm de sortare foarte popular este Quicksort. Desi complexitatea sa pentru cazul cel mai defavorabil este $\mathit{O}\left( N^2 \right)$ , in practica se comporta foarte bine si cunoaste multe imbunatatiri (detalii in prezentarea profesorului Robert Sedgewick aici si a profesorului Jon Bentley aici).

In libraria standard a limbajului C este implementata o varianta Quicksort (poate fi apelata prin qsort(...) - o sursa demonstrativa gasiti aici), iar STL-ul ofera programatorilor C++ functia sort, o implementare a algoritmului Introsort (o sursa demonstrativa aici).

Pentru mai multe detalii si un studiu comparativ al algoritmilor de sortare vizitati pagina Wikipedia dedicata acestui subiect.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta