Ciao a tutti,
quest'oggi a lezione ci è stato chiesto di implementare vari algoritmi di ordinamento in un programma C, tra cui il quicksort come si capisce dal titolo penso di essere riuscito a trovare la strada giusta, solo che l'iterazione della funzione si ferma dopo il primo stadio, dando quindi un ordinamento non corretto: vi posto il codice.
il main
codice:
int main()
{
int *array=NULL;
int *res=NULL;
int temp, size, i;
do
{
printf("Inserire il numero di elementi da inserire nell'array\n");
scanf("%d", &temp);
} while(temp<=0);
size=temp;
array=malloc(size*sizeof(int));
res=malloc(size*sizeof(int));
//altro codice non strettamente attinente
case 3: QuickSort(array, size, res);
printf("L'array ordinato:\n");
for(i=0;i<size;i++)
printf("%d\t", res[i]);
printf("\n");
break;
}
la funzione Quicksort
codice:
void QuickSort(int *array, int size, int *res)
{
int pivot=array[0];
int i, j=size-1, k=0;
int c1=0;
int c2=0;
//Implementazione array d'appoggio
int *temp=NULL;
temp=malloc(size*sizeof(int));
for(i=1;i<size;i++)
{
if(*(array+i)>=pivot)
{
res[j--]=array[i];
++c1;
}
else if(*(array+i)<pivot)
{
res[k++]=array[i];
++c2;
}
}
res[k]=pivot;
if (c2>1)
QuickSort(res, c2, temp);
if (c1>1)
QuickSort(res+k+1, c1, temp);
}
Se in input do 2, 4, 1, 5, 9 (e quindi un array di 5 elementi) ho come output: 1 2 9 5 4, cioè quello che risulterebbe dopo una sola iterazione. Il problema dovrebbe essere nel momento in cui la funzione chiama se stessa: al momento della chiamata, le istruzioni avvengono in un'altra zona di memoria? Così che alla prima chiamata di se stessa starei considerando un array di dimensione c2 insieme a un nuovo array di appoggio. Sbaglio? Perchè, con ogni probabilità, non riesco a capire bene il funzionamento della ricorsività con le funzioni.
Ringrazio tutti per le risposte.