== include(page="template/taskheader" task_id="sortare") ==

Poveste si cerinta...

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:
 
==code(c)|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))
==

h2. Date de intrare