Quicksort

          Principiu: se alege un element oarecare a[k] al tabloului (1<=k<=N) si vom nota cu x valoarea acestui element. Se parcurge tabloul de la stinga, pina cind se gaseste primul element a[i].cheie>x.cheie. Apoi se parcurge tabloul de la dreapta, pina cind se gaseste primul element a[j].cheie x.cheie.

          Procedura descrisa se aplica in continuare pe rind celor doua partitii obtinute, apoi celor patru partitii s.a.m.d., pina cind fiecare partitie ajunge sa fie formata dintr-un singur element.

          Implementarea algoritmului in Pascal: metoda Quicksort se poate implementa in doua moduri: recursiv si nerecursiv. In ambele cazuri s-a convenit ca elementul x sa fie ales la mijlocul tabloului (respectiv partitiei).

  // Quicksort

#include<iostream.h>

int a[100],n,k;

void poz (int li, int ls, int &k, int a[100])

{

int i=li, j=ls,c,i1=0,j1=-1;

  while (i<j)

     {

          if (a[i]>a[j])

             {c=a[j];

              a[j]=a[i];

              a[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, a);

     quick(li, k-1);

     quick(k+1, ls); }

}

main()

{ int i;

cout<<"n="; cin>>n;

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

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

quick(1,n);

for (i=1; i<=n; i++) cout<<a[i]<<endl;

}