Ciao a tutti, da giorni sto provando a modificare un quicksort per far in modo che utilizzi più pivot invece che uno solo, ma mi sono bloccata subito sulla partition vi posto il codice:
codice:
int Max (int A[],int k){
int max=0,i,tmp;
for(i=0;i<k-1;i++)
{
if (max<A[i])
{
max=A[i];
}
}
printf("max=%d ",max);
printf("\n");
return max;
}
int Kpartition (int A[],int p,int n, int k)
{
int i, j, z, x, B[2];
int tmp=0, max, pivot=0;
j=n;
for (z=0;z<k-1;z++)
{
x=j;
max=Max(A,k);
for (i=p;i<=x;i++)
{
if (A[i]==max)
pivot=i;
if (A[i]>max && i<j)
{
tmp=A[j];
A[j]=A[i];
A[i]=tmp;
j--;
}
}
tmp=A[j];
A[j]=A[pivot];
A[pivot]=tmp;
j--;
}
return j;
}
Nel codice per scegliere i pivot prendo il massimo tra i primi k-1 valori del vettore.
Vi posto anche il codice del quicksort funzionante con un solo pivot dal quale sono partita.
codice:
#include <stdio.h>
#include <stdlib.h>
int Partition (int A[],int p,int n){
int i, j;
int tmp, max;
i=p;
j=n;
tmp=A[i];
A[i]=A[j];
A[j]=tmp;
while (i<j)
{
while (j>p && pivot<=A[j])
j=j-1;
while (i<n && pivot>A[i])
i=i+1;
if (i<j)
{
tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}
}
tmp=A[p];
A[p]=A[j];
A[j]=tmp;
return j;
}
void Quicksort (int A[], int p,int n)
{
int q;
if (p<n)
{
q=Kpartition(A,p,n);
Quicksort(A,p,q);
Quicksort(A,q+1,n);
}
}
int main ()
{
int A[]={2,4,1,6,5,0}, n=5;
int i;
Quicksort(A,0,n,k);
for(i=0; i<=n; i++)
printf("%d ",A[i]);
}
Qualcuno può darmi un idea su cosa sto sbagliando? sono disperata