Cazul de baza a unei recursivitati sunt listele de dimensiune $0$ sau $1$. Putem implementa in pseudocod acest algoritm astfel:

==code(c)|functie qsort(sir[])

==code(pas)|function qsort(sir[])

   var stanga[], dreapta[], pivot

   daca lungimea(sir) <= 1
       returneaza sir

   if lungime(sir) <= 1
       return 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))

   foreach x in sir
       if x < pivot then insereaza x in stanga
       if x > pivot then insereaza x in dreapta
   return concatenaeza(qsort(stanga), pivot, qsort(dreapta))

==
Fumeanu a implementat acest algoritm si considera ca implementarea lui este foarte eficienta. Nargy este mai intelept si isi da seama ca performanta intregului algoritm depinde de modul in care se selecteaza pivotul. Metoda folosita de Fumeanu este urmatoarea: pentru un sir de lungime $i$ el alege mediana elementelor de pe pozitiile $A{~i~}, B{~i~}$ si $C{~i~}$ (mediana reprezinta elementul mijlociu ca marime dintre cele $3$).

h2. Date de intrare

Fisierul de intrare $sortare.in$ contine pe prima linie numarul $N$. Pe urmatoarele $N-1$ linii se vor gasi cate 3 numere naturale $A{~i~} B{~i~} C{~i~}$ separate prin spatii ({$2≤i≤N$}).

Fisierul de intrare $sortare.in$ contine pe prima linie numarul $N$. Pe urmatoarele $N-1$ linii se vor gasi cate 3 numere natural $A{~i~} B{~i~} C{~i~}$ separate prin spatii ({$2≤i≤N$}).

h2. Date de iesire

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

2917