Laborator 5

Tehnici avansate de sortare:

-Shell Sort

-Quick Sort

-Heap Sort

-Bin Sort

-Radix Sort

void QuickSort(int s,int d)

{

int i=s,j=d,x=a[(s+d)/2],aux;

do{

while(a[i]<x)

i++;

while(a[j]>x)

j--;

if(i<=j)

{

aux=a[i];

a[i]=a[j];

a[j]=temp;

i++;j--;

}

}while(i<=j);

if(s<j)

QuickSort(s,j);

if(d>i)

QuickSort(i,d);

}

void DownHeap(int v,int n)

{

int w = 2 * v + 1,aux;

while (w<n)

{

if(w+1<n)

if (a[w+1]>a[w])

w++;

if (a[v]>=a[w])

return;

aux = a[v];

a[v] = a[w];

a[w] = aux;

v = w;

w = 2 * v + 1;

}

}

void HeapSort(int n)

{

for (int v = n/2-1; v >= 0; v--)

DownHeap (a,v,n);

while (n>1)

{

n--;

int aux=a[0];

a[0]=a[n];

a[n]=aux;

DownHeap (a,0,n);

}

}

void BinSort()

{

int i,aux;

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

{

while (a[i]!=i)

{

aux=a[i];

a[i]=a[aux];

a[aux]=aux;

}

}

}

void ShellSort()

{

int i,j,pas,aux;

unsigned char m;

int h[4]={9,5,3,1};

/*exemplu de atribuire directă incremenţi pentru un tablou h de 4 elemente*/

for(m=0;m<4;++m)

{

pas= h[m];

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

{

aux=a[i];

for (j=i;j>=pas&&a[j-pas]>aux;j=j-pas)

a[j]=a[j-pas];

a[j]= aux;

}

}

}

unsigned biti(unsigned x, int k, int j)

{

return (x>>k)&~(~0<<j);

}

void RadixSort(int stanga,int dreapta,int b) //prin interschimbare

{

/*stanga, dreapta - limitele curente ale tabloului de sortat*/

/*b - lungimea în biţi a cheii de sortat*/

int i,j,aux

if((dreapta>stanga)&&(b>=0))

{

i=stanga;j=dreapta;

do{

while((biti(a[i],b,1)==0)&&(i<j))

i=i+1;

while((biti(a[j],b,1)==1)&&(i<j))

j=j-1;

aux=a[i];

a[i]=a[j];

a[j]=aux;

}while(!(j==i));

if(biti(a[dreapta],b,1)==0)

j=j+1;

/*dacă ultimul bit testat este 0 se reface lungimea partiţiei*/

RadixSort(stanga,j-1,b-1);

RadixSort(j,dreapta,b-1);

}

}

void Radix_direct(int b)

{

// b-numarul de biti pe care este reprezentata cheia

int m=2

int m1=m*m

int i,j,trecere;

int numar[m1]; /*m1:=2^m*/

int aux;

for(trecere=0;trecere<=(b/m)-1;trecere++)

{

for(j=0;j<=m1-1;j++)

numar[j]=0;

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

{

aux=biti(a[i],trecere*m,m);

numar[aux]= numar[aux]+1;

}

for(j=1;j<=m1-1;j++)

numar[j]= numar[j-1]+numar[j];

for(i=n-1;i>=0;i --)

{

aux=biti(a[i],trecere*m,m);

t[numar[aux]-1]= a[i];

numar[aux]= numar[aux]-1;

}

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

a[i]= t[i];

}

}