[c] Quicksort ricorsivo

[federossoblu]

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

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

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.

[linoma]

Intanto in temp non ce nulla o valori casuali. Normalmente l'indice i va incluso tra parentesi quando si cerca di leggere un vettore in questo modo array[i] e non *(array+i)

[federossoblu]

Originariamente inviato da linoma
Intanto in temp non ce nulla o valori casuali. Normalmente l'indice i va incluso tra parentesi quando si cerca di leggere un vettore in questo modo array[i] e non *(array+i)

Grazie per l'aiuto (e scusa per il ritardo della risposta), però temp è di proposito vuoto perchè deve svolgere la stessa funzione che nel main ha l'array res. Poi la scrittura array[i] coincide con la scrittura che ho inserito io, visto che "array" è un puntatore al primo elemento dell'array e posso utilizzare l'aritmetica dei puntatori con questo, potendo accedere al suo valore con l'asterisco.

Può darsi che forse sia meglio modificare la funzione in modo da utilizzare puntatori a puntatori. Oppure modifico proprio l'algoritmo di procedimento con la classica procedura di utilizzo di 2 array.

[federossoblu]

int 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

	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;
	for(i=0;i<size;i++)
		array[i]=res[i];
	
	if (c2>1)
		QuickSort(array, c2, res);
	if (c1>1)
		QuickSort(array+k+1, c1, res);

	return 0;

}

Ho modificato la funzione in questo modo