QUICK SORT

Sa se ordoneze crescator un vector v, folosind metoda de sortare rapida (quick sort).

Etapele de rezolvare ale algoritmului QUICK SORT:

-se apeleaza functia quick cu limita inferioara li=1 si limita superioara ls=n
-functia poz realizeaza mutarea elementului de pe prima pozitie exact pe pozitia k ce o va ocupa acesta in vectorul final ordonat: toate elementele aflate in stanga vor fi mai mici si toate elementele din dreapta lui vor fi mai mari ; parametrul k este transmis prin referinta (adresa) fiind astfel vizibil si in afara functiei poz
-vectorul V se imparte in doua parti : li,(k-1) si (k+1),ls
-pentru fiecare din aceste parti se reapeleaza functia quick
-fiecare din cele doua parti va fi impartita in alte doua parti ;procesul continua pana cand li depaseste ls ,in acest moment toate elementele vectorului au fost mutate exact pe pozitiile ce le vor ocupa in vectorul final ;deci vectorul este ordonat

#include<iostream.h>

int v[100],n,k;

void poz(int li,int ls,int & k,int v[100])
{
int i=li,j=ls,c,i1=0,j1=-1;
while(i<j)
{
if(v[i]>v[j])
{
c=v[j];v[j]=v[i];v[i]=c;
c=i1;i1=-j1;j1=-c;
}
i=i+i1;
j=j+j1;
}
k=i;
}

void quick(int li,int ls)
{
if(li<ls)
{
poz(li,ls,k,v);
quick(li,k-1);
quick(k+1,ls);
}
}

void main()
{
int i;
cout<<“n=”;cin>>n;
for(i=1;i<=n;i++)
{
cout<<“v[“<<i<<“]=”;
cin>>v[i];
}
quick(1,n);
for(i=1;i<=n;i++) cout<<v[i]<<” “;
}