C.A.R. Hoare, pornind de la acelasi principiu, a conceput o metoda cu performante spectaculare pe care a denumit-o quicksort (sortare rapida).
Aceasta se bazeaza pe aceeasi idee de a creste eficienta interschimbarilor prin marirea distantei dintre elementele implicate.
Sortarea prin partitionare porneste de la urmatorul algoritm.
Fie x un element oarecare al tabloului de sortat a1 , , an .
Se parcurge tabloul de la stanga spre dreapta pana se gaseste primul element ai > x .
In continuare se parcurge tabloul de la dreapta spre stanga pana se gaseste primul element aj < x .
Se interschimba intre ele elementele ai si aj ,
Se continua parcurgerea tabloului de la stanga respectiv de la dreapta (din punctele in care s-a ajuns anterior), pana se gasesc alte doua elemente care se interschimba, s.a.m.d.
Procesul se termina cand cele doua parcurgeri se 'intalnesc' undeva in interiorul tabloului.
Efectul final este ca acum sirul initial este partitionat intr-o partitie stanga cu chei mai mici decat x si o partitie dreapta cu chei mai mari decat x.
//Sortarea prin partitionare - quicksort - varianta C
quicksort(int s,int d)
}while(i<=j);
if(s<j)quicksort(s,j);
if(d>i)quicksort(i,d);
Analiza metodei quicksort
Pentru a analiza performanta acestei metode, se analizeaza mai intai partitionarea.
Se presupune pentru simplificare,
(1) Ca setul ce va fi partitionat consta din n chei distincte si unice cu valorile
(2) Ca dintre cele n chei a fost selectata cheia cu valoarea x in vederea partitionarii.
In consecinta aceasta cheie ocupa a x-a pozitie in multimea ordonata a cheilor si ea poarta denumirea de pivot.
Numarul mediu M de interschimbari pentru partitionarea unei secvente de n chei se obtine insumand toate numerele de interschimbari pentru toate valorile lui x cuprinse intre 1 si n si impartind la numarul total de chei n [3.2.6.h].
|
