[C++] QuickSort

[shelu]

Salut!

Postez acest algoritm, foarte folositor pentru cei care se duc la diverse concursuri sau la olimpiade (judetene, natioanale etc.). In general, "elevul roman" foloseste Sortarea prin interschimbare, sau algoritmul Bubble Sort, deoarce sunt mult mai usor de scris, mai scurte. E OK (pt problemele din manual..), insa QuickSort este mult mai rapid decat cele spuse anterior.

Mai jos este algortimul scris in c++:

#include <iostream.h>

int n,a[1000];

void sort(int l,int r)

{int i, j, x, y;

i=l; j=r; x=a[(l+r)/2];

while (i<=j)

{ while (a<x) {i=i+1;}

while (x<a[j]) {j=j-1;}

if (i<=j)

{y=a; a=a[j]; a[j]=y;

i=i+1; j=j-1;}

}

if (l<j) sort(l,j);

if (i<r) sort(i,r);

}

void main()

{int i;

cin>>n;

for (i=1;i<=n;i++)

cin>>a;

sort(1,n);

for (i=1;i<=n;i++)

cout<<a<<" ";

}

//Nu explic cum functioneaza acest algoritm, deoarece puteti gasit foarte usor pe google.

Important: In cazul in care uitati algoritmul, puteti intra in BP (pascal), Examples, si dati un search "QSORT" (nu mai stiu exact unde este, nu am pascal'ul in pc). Acolo gasiti algoritmul scris in Pascal, si trebuie doar sa faceti traducerea in C++; desigur acest 'trick' poate fi facut in conditii de concurs, pe calculatoarele de acolo fiind instalat si C++ si BP, iar supraveghetorii nu pot sa zica nimic!

De exemplu, problema "Fish", de la BOI2000; pt rezolvare trebuiau mai intai sortate n numere (n pana in 500.000). Pt a nu depasii timpul trebuia folosit QuickSort; orice alta metoda folosita, ducea la depasirea timpului de executie!

Sper ca acest mic tutorial ii vor ajuta pe programatorii pasionati de algoritmica!

[&amp;#208;&amp;#210;&amp;]

n are pivot randomizat - caca

[muriel]

algoritmul asta era prin mai toate cartile de informatica cand eram la liceu

[darkking]

cel mai rapid algoritm de sortare (mai putin numere double si long) este radix. o sa editez aici sa-l pun cum il gasesc.

[moubik]

radix e specializat pentru stringuri, dar merge foarte bine si pe numere.

[quote=

[shelu]

Nu am spus ca e cel mai rapid algoritm de sortare; o sa ma interesez in legatura cu radix, sa vad daca care este diferenta (daca e mult mai rapid.. ceea ce nu cred). Revin cu un post.

Edit:Nu este o metoda prea folosita deoarece:

-in cazul in care numerele pot avea un numar diferit de cifre, trebuie sa verificam pt fiecare numar cate cifre are;

-ocupa mai mult spatiu de memorie decat Quick;

Astfel sunt situatii in care este mai lent decat Quick.

Am aflat ca sunt algoritmi mai rapizi decat Quick sau radix. Daca gasesc, o sa postez algoritmii respectivi.

Edit: Am vorbit cu proful de info, si chiar exista algoritmi mai rapizi, insa nu se merita folosirea acestora deoarece sunt mult mai complicati decat QuickSort, iar diferenta este prea mica.

[&amp;#208;&amp;#210;&amp;]

cu pivot randomizat merge mai repede...nu stiu exact si ce stiu nu am timp sa o explic.

[moubik]

in caz ca ti se da de sortat cazul cel mai nefavorabil, pivotul random te ajuta.

ideea este, pur si simplu in loc sa pornesti cu pivotul ca fiind primul element din subsirul tau (sau ultimul, depinde cum vrei sa implementezi), iti alegi un pivot random in intervalul acesta, faci interschimbarea si pe urma continui cu pozitionarea lui pe pozitia corecta.

exemplu:

quickRand (min, max)
{
	//pivotul se alege random in intervalul pe care trebuie sa-l sortez
   pivot = rand (min, max);

   //dupa ce mi-am ales pivotul, fac interschimbare ca sa pot sa sortez tot intervalul specificat
   temp = vector[pivot];
   vector[pivot] = vector[min];
   vector[min] = temp;

   //salvez limita minima si maxima pentru divide et impera ce va urma
   q_min = min;
   q_max = max;

   //variabila ce ma ajuta sa navighez cu pivotul
   change = 1;

	//se face exact la ca quicksort normal aici, pozitionez pivotul corect (toti din stanga pivotului sunt mai mici decat el, tot din dreapta sunt mai mari)
   while (min < max)
   {
      if (vector[min] > vector[max])
		{
			//daca 2 elemente nu sunt pozitionate corect le interschimb si am grija sa urmaresc pivotul in continuare
			temp = vector[min];
			vector[min] = vector[max];
			vector[max] = temp;
			//modific variabila pentru a putea urmari pivotul pana la pozitionare corecta
			change = 1 - change;  // daca este 1 devine 0 si invers
		}

		if(change == 1)
		{
			max--;
		}
		else
		{
			min++;
		}
   }

   //divide et impera pe cele 2 substringuri create
   quickRand(q_min, min - 1);
   quickRand(min + 1, q_max);
}

nu am testat codul, l-am scris in notepad.

sper ca ati inteles cum e cu pivot randomizat.

208210, daca nu are pivot randomizat nu e caca.