Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-03-11 20:24:30.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sortare.in, sortare.out | Sursă | preONI 2008, Runda finala |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Sortare
Sortarea rapida (sau quicksort) este un bine cunoscut algoritm de sortare. Algortimul opereaza astfel:
- Se alege un element din sir, care se va numit pivot
- Se reordoneaza sirul astfel incat toate elementele care detin o valoare mai mica decat valoarea elementului pivot se vor pozitiona inaintea elementului pivot, si elementele care au o valoare mai mare decat valoarea elementului pivot se vor pozitiona dupa elementul pivot
- Se sorteaza recursiv cele doua bucati din sir
Cazul de baza a unei recursivitati sunt listele de dimensiune 0 sau 1. Putem descrie in pseudocod acest algoritm astfel:
functie qsort(sir[])
var stanga, dreapta, pivot
daca lungimea(sir) <= 1
returneaza sir
pivot = un element din sir
pentru fiecare x din sir
daca x < pivot atunci insereaza x in stanga
daca x > pivot atunci insereaza x in dreapta
returneaza concatenaeza(qsort(stanga), pivot, qsort(dreapta))Date de intrare
Fisierul de intrare sortare.in ...
Date de iesire
In fisierul de iesire sortare.out ...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| sortare.in | sortare.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
Trebuie sa te autentifici pentru a trimite solutii. Click aici
