Metode de sortare – sortare rapida (Quick Sort)

Principiul acestei metode este următorul: Se alege un element pivot din tabloul ce trebuie sortat. Tabloul este astfel partiţionat în 2 subtablouri, alcătuite de o parte şi de alta a acestui pivot, astfel: elementele mai mari decât pivotul sunt mutate în dreapta pivotului iar elementele mai mici în stânga pivotului. Cele 2 subtablouri sunt sortate în mod independent prin apeluri recursive ale algoritmului.


#include "stdio.h"
#include "conio.h"
#include "values.h"
//procedura recursivă de sortare a secvenţei a[l]...a[r]
void qs(int a[], int l, int r)
{
  int v,i,j,elem;
  if(r > l)
  {
    v=a[r];

    //v este elementul pivot ales ca cel mai din dreapta element
    i=l-i;
    //indicele i porneşte din stânga (-1 pentru că în ciclul while de mai jos
    //se face întâi incrementarea şi apoi testul)
    j=r;
    //indicele j porneşte din dreapta (va fi întâi decrementat în ciclul
    //while pornind de la r-i deoarece a[r] este pivotul)
    for(i=0;i < r-1;i++)     {       while(a[++i] < v);       //ieşim din ciclu la primul element a[i] mai mare sau egal cu pivotul       while(a[—j] > v);
      //ieşim din ciclu la primul element a[j] mai mic sau egal cu pivotul
      if (i >= j) break;
      //dacă i >= j părăsim ciclul for
      elem=a[i];
      a[i]=a[j];
      a[j]=elem;
      //în cazul în care i < j inversăm a[i] cu a[j] pentru a duce în stânga       //pivotului un element mai mic şi în dreapta lui un element mai mare       //decât pivotul     }     elem=a[i];     a[i]=a[r];     a[r]=elem;     //la ieşirea din ciclul for (când i >= j) inversăm a[i] cu pivotul
    qs(a,l,i-1);
    //apelările recursive ale funcţiei de sortare conform tehnicii
    qs(a,i+1,r);
    //de programare "Divide et Impera"
  }
}

void main(void)
{
  int n,a[100],i;
  printf("Introdu dim şirului:");
  scanf("%d",&n);
  printf("Introdu elem şirului:\n");
  //elementele şirului încep de la indicele 1
  for(i=1;i <= n;i++)   {     printf("a[%d]=",i);     scanf("%d",a+i);   }   a[0]=-MAXINT;   //apelul funcţiei de sortare rapidă   qs(a,1,n);   printf("Şirul sortat este: ");   for(i=1;i <= n;i++)   printf("%d ",a[i]);   putchar("\n");   getch(); }

Leave a Reply

Your email address will not be published. Required fields are marked *

3 × 3 =

Time limit is exhausted. Please reload CAPTCHA.