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];
}
}