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?

[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.