Sortare rapida

Algoritmul de la Sortare rapida se bazeaza pe metoda Divide et impera.

Imparte: Sirul de pe pozitiile p...u este impartit (rearanjat) in doua siruri nevide de elemente. Elementele celor 2 subsiruri se gasesc pe pozitiile p...m si respectiv m+1...u. Primul sir are proprietatea ca fiecare element din primul sir este mai mic decat  orice element din al doilea sir.

Stapaneste: Cele doua siruri sunt ordonate prin apeluri succesive ale algoritmului de sortare rapida (quickSort)

Combina: Deoarece cele doua siruri sunt sortate pe loc, nu este nevoie de nicio ordonare.

#include <iostream.h>

int a[50],n,i;

void quickSort(int a[], int p, int u) {

   int i = p, j = u;

   int m;

   int pivot = a[(p + u) / 2];

   while (i <= j) {  

while (a[i] < pivot)

   i++;  

while (a[j] > pivot)

   j--;  

  if (i <= j)

  {

m=a[i];

a[i] =a[j];

a[j] = m;

   i++;  

   j--;  

  }  

  } 

  if (p < j)

quickSort(a, p, j);

  if (i < u)

quickSort(a, i, u);

  }  

void main()

{

 int n,i;

 cout<<endl<<endl;

 cout<<"n=";

 cin>>n;

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

 {

  cout<<"a["<<i<<"]=";cin>>a[i] ;

 }

 quickSort(a,1,n);

 cout<<endl;

 cout<<"Sirul sortat"<<endl;

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

cout<<a[i]<<" ";

}