PDA

Visualizza la versione completa : [C] Quicksort


tr_gal
30-06-2015, 16:33
Sto modificando un quicksort in modo che utilizzi più pivot, sono quasi arrivata alla conclusione ma mi sono bloccata, penso ci sia un errore nella kpartition quando vado a restituire il vettore contenente gli indirizzi dei pivot ma non riesco a capire come risolverlo, qualcuno mi da una mano?? sono disperata devo assolutamente consegnarlo se no non potrò fare l'esame e sono ormai due settimane che provo a farlo... vi posto il codice:

#include <stdio.h>#include <stdlib.h>
#include <time.h>


int *Pivot (int A[],int p,int r, int k)
{
int i,tmp,j,z;
int *pivot=(int*)malloc((k)*sizeof(int));
srand(time(NULL));
for (i=0;i<k-1;i++)
{
pivot[i]=A[rand()%((r-p)+p+1)];
}
Insertionsort(pivot,0,k-2);
return pivot;
}


void Swap (int A[], int i, int j)
{
int tmp;
tmp=A[j];
A[j]=A[i];
A[i]=tmp;
return;
}
int Partition (int *A,int p,int r,int pivot)
{
int i, j,q;
i=p;
j=r;


while (i<j)
{
if (pivot==A[i])
{
q=i;
i++;
}
while (j>p && pivot<=A[j])
j=j-1;
while (i<r && pivot>A[i])
i=i+1;
if (i<j)
Swap(A,i,j);
}
Swap(A,q,j);
return j;
}


int Insertionsort(int *A,int p,int r)
{
int key,j,i;
if (p<r)
{
for(j=p; j<=r;j++)
{
key=A[j];
i=j-1;
while (i>=p && A[i]>key)
{
A[i+1]=A[i];
i--;
}
A[i+1]=key;
}
}


}
int *Kpartition (int *A,int *B,int p,int r,int k)
{
int *pivot;
int i, j, y, z, q,key;
pivot=Pivot(A,p,r,k);
if ((r-p)>k)
{
for(z=k-1;z>=1;z--)
{
j=Partition(A,p,r,pivot[z-1]);
B[z]=j;
}
}
else
{
Insertionsort(A,p,r);
}
return B;
}


int Kquicksort(int A[],int *B,int p,int r,int k)
{
int i;
int *q;
if(p<r)
{
q=Kpartition(A,B,p,r,k);
for(i=0; i<k-1; i++)
Kquicksort(A,B, q[i], q[i+1], k);
}

return 0;
}


void main ()
{
int A[]={96,845,25,74,12,10,1547,1,6,95,42,78,20,16,14,25 8,7}, n=16;
int i,k=2;
int *B=(int*)malloc((k)*sizeof(int));
Kquicksort(A,B,0,n,k);
for(i=0; i<=n; i++)
printf("%d ",A[i]);
free (B);
return;
}

Loading