Consiglio per quicksort

oleg.fresi
Ho implementato questa funzione quicksort ma quando la vado ad usare nel main il programma crasha:

La funzione:
void quickSort(int arr[], int inizio, int fine)
{
	int i = inizio, j = fine, tmp;

	int pivot = arr[(inizio + fine) / 2];

	while (i <= j) {

		while (arr[i] < pivot)

			i++;

		while (arr[j] > pivot)

			j--;

		if (i <= j) {

			tmp = arr[i];

			arr[i] = arr[j];

			arr[j] = tmp;

			i++;

			j--;

		}

	};

	if (inizio < j)

		quickSort(arr, inizio, j);

	if (i < fine)

		quickSort(arr, i, fine);
}   



Nel main:
int v[]{ 4, 7, 2, 9, 3, 12 };
	cout << "Ecco l'array disordinato: " << endl;
	stampaArray(v, 6);
	cout << "Ecco l'array ordinato con quick sort: " << endl;
	quickSort(v, 4, 12);
	stampaArray(v, 6);


Il problema lo genera nel main, ma non riesco a capire perchè. Potreste aiutarmi per favore?

Risposte
Super Squirrel
quickSort(v, 4, 12);

Sei sicuro?
Distrazione oppure non hai implementato tu la funzione e non sai cosa passargli?

int v[]{ 4, 7, 2, 9, 3, 12 };

Si può omettere l'=?

oleg.fresi
Giusto, una mia distrazione, ma il problema non si è risolto.

Super Squirrel
Mostra il codice completo.

oleg.fresi
Il codice l'ho gia messo tutto, inoltre si fa uso della funzione per copiare l'array:
void stampaArray(int arr[], int l)
{
	for (int i = 0; i < l; i++)
		cout << arr[i] << endl;
}

l è la lunghezza dell'array

Super Squirrel
Premesso che non ho controllato la funzione quickSort(), ho provato a compilare il codice e sembra funzionare...

A rischio di essere ripetitivo ti chiedo se puoi postare il codice intero, altrimenti l'unica cosa da fare è analizzare in modo accurato quickSort() alla ricerca di qualche bug, e sinceramente se possibile eviterei.

oleg.fresi
Ilfatto è che la stampaArray, il quicksort e il main sono separati nel mio file, o forse vuoi una cosa del genere :
void quickSort(int arr[], int inizio, int fine)
{
	int i = inizio, j = fine, tmp;

	int pivot = arr[(inizio + fine) / 2];

	while (i <= j) {

		while (arr[i] < pivot)
			i++;
             
		while (arr[j] > pivot)
			j--;

			if (i <= j) {

			tmp = arr[i];

			arr[i] = arr[j];

			arr[j] = tmp;

			i++;

			j--;

		}

	};

	if (inizio < j)

		quickSort(arr, inizio, j);

	if (i < fine)

		quickSort(arr, i, fine);
}

int main()
{
	int v[]={ 4, 7, 2, 9, 3, 12 };
	cout << "Ecco l'array disordinato: " << endl;
	stampaArray(v, 6);
	cout << "Ecco l'array ordinato con quick sort: " << endl;
	quickSort(v, 4, 12);
	stampaArray(v, 6);

	system("pause");
	return 0;
}


Quando mando in esecuzione il programma nella parte dove deve stampare l'array ordinato stampa alcuni valori dell'array ma disordinati e poi gli ultimi due valori a caso pure negativi. Quando chiudo la shell mi dice variable v (l'array) was corrupted. Ogni volta che rieseguo il programma gli ultimi due valori casuali sono diversi. In pratica si genera un'eccezione.

Super Squirrel
Si intendo metti tutto in un solo file compilabile, testalo e se crasha riportalo pari pari qui sul forum.

In ogni caso vedo ancora quella riga di codice
quickSort(v, 4, 12);

non avevi detto che si trattava di una distrazione e che avevi aggiustato?!
Hai capito perchè è sbagliata quella chiamata a funzione?

A questo punto mi viene da pensare che tu stia solo copiando delle funzioni da internet, ma non sappia come richiamarle nel main da te scritto.

oleg.fresi
No, la mia distrazione consisteva nell'aver omesso l'=, ma a quello non ci ho badato. Perchè è sbagliato? La funzione prende il primo elemento e l'ultimo elemento dell'array, e in questo caso sono proprio il 4 e il 12. O forse dovrei passare gli indici che si riferisco a quei numeri, quindi lo 0 e il 7. In tal caso perchè?

Super Squirrel
La funzione prende il primo elemento e l'ultimo elemento dell'array, e in questo caso sono proprio il 4 e il 12.

Al di là del caso specifico non ha nessun senso ragionare in termini di valori... ti faccio un esempio, sia
mostra_array(int v[], unsigned int inizio, unsigned int fine)
una funzione che mostra una sottosequenza di un array.
Ipotizziamo di avere il seguente array:
v = 1 1 1 1 1
e di chiamare la funzione mostra_array(v, 1, 1) passandogli come dici tu il valore del primo e dell'ultimo elemento. A questo punto quale dovrebbe essere l'output?
Ti renderai conto che a differenza degli indici, i valori non rappresentano un'informazione univoca.
O forse dovrei passare gli indici che si riferisco a quei numeri, quindi lo 0 e il 7.

In realtà essendo 6 elementi, gli indici sono 0 e 5.

oleg.fresi
Ah ok, adesso ho capito perchè, m si può implementare un sistema in modo che l'utente inserisca proprio il primo e l'ultimo valore dell'array ma questi vengano poi associati agli indici e l'algoritmo lavora solo con gli indici?

vict85
"olegfresi":
Ah ok, adesso ho capito perchè, m si può implementare un sistema in modo che l'utente inserisca proprio il primo e l'ultimo valore dell'array ma questi vengano poi associati agli indici e l'algoritmo lavora solo con gli indici?


Come ti ha scritto Super Squirrel, i valori non sono necessariamente univoci, quindi la funzione in sé ha poco senso. L'implementazione di una cosa del genere è piuttosto semplice, ma non te lo mostro perché ritengo che sia una pratica poco sicura (se l'elemento non è presente nell'array cominci a leggere memoria a caso finché il tuo programma non crasha, o peggio). Detto questo, che problema stai cercando di risolvere?

oleg.fresi
Perfetto, non ci sono altri problemi oltre questo, grazie mille per l'aiuto!

oleg.fresi
Riprendo un attimo questo thread per un altro dubbio: se chiedo di stampare il pivot dopo averlo calcolato, mi tampa l'array in disordine e non in ordine.Come mai? Il codice è così:
void quickSort(int arr[], int inizio, int fine)
{
	int i = inizio, j = fine, tmp;
	int pivot = arr[(inizio + fine) / 2];
       cout << pivot << endl;

	while (i <= j) 
	{
		while (arr[i] < pivot)
			i++;            
		while (arr[j] > pivot)
			j--;

			if (i <= j) 
			{
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			i++;
			j--;
		}
	};

	if (inizio < j)
		quickSort(arr, inizio, j);
	if (i < fine)
		quickSort(arr, i, fine);
}   


Super Squirrel
Ma ti riferisci ai valori di pivot oppure alla funzione stampa_array() che richiami alla fine nel main?

oleg.fresi
si è la funzione stampaArray che me li stampa disordinati dopo aver chiamato la mergeSort

Super Squirrel
si è la funzione stampaArray che me li stampa disordinati dopo aver chiamato la mergeSort

:?:

Sarò sincero, non capisco cosa intendi... cioè prima di aggiungere quel cout << pivot << endl; nella funzione quickSort() il programma funzionava bene?

In ogni caso a scanso di equivoci, metti tutto in un solo file compilabile e riporta il codice qui sul forum insieme a quello che è l'output del programma e l'output che invece ti aspetteresti.

oleg.fresi
Si, prima di mettere il cout funzionava bene, poi no.

Super Squirrel
"Super Squirrel":
In ogni caso a scanso di equivoci, metti tutto in un solo file compilabile e riporta il codice qui sul forum insieme a quello che è l'output del programma e l'output che invece ti aspetteresti.

oleg.fresi
void quickSort(int arr[], int inizio, int fine)
{
	int i = inizio, j = fine, tmp;
	int pivot = arr[(inizio + fine) / 2];
	//cout << pivot << endl;

	while (i <= j) 
	{
		while (arr[i] < pivot)
			i++;            
		while (arr[j] > pivot)
			j--;

			if (i <= j) 
			{
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			i++;
			j--;
		}
	};

	if (inizio < j)
		quickSort(arr, inizio, j);
	if (i < fine)
		quickSort(arr, i, fine);
}  

int main()
{
	int v[]={ 4, 7, 2, 9, 3, 12 };
	cout << "Ecco l'array disordinato: " << endl;
	stampaArray(v, 6);
	cout << "Ecco l'array ordinato con quick sort: " << endl;
	quickSort(v, 0, 5);
	stampaArray(v, 6); 

	system("pause");
	return 0;
}
 

Super Squirrel
Non compila il codice che hai postato.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.