Consiglio per quicksort
Ho implementato questa funzione quicksort ma quando la vado ad usare nel main il programma crasha:
La funzione:
Nel main:
Il problema lo genera nel main, ma non riesco a capire perchè. Potreste aiutarmi per favore?
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
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'=?
Giusto, una mia distrazione, ma il problema non si è risolto.
Mostra il codice completo.
Il codice l'ho gia messo tutto, inoltre si fa uso della funzione per copiare l'array:
l è la lunghezza dell'array
void stampaArray(int arr[], int l) { for (int i = 0; i < l; i++) cout << arr[i] << endl; }
l è la lunghezza dell'array
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.
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.
Ilfatto è che la stampaArray, il quicksort e il main sono separati nel mio file, o forse vuoi una cosa del genere :
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.
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.
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
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.
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.
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è?
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.
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?
"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?
Perfetto, non ci sono altri problemi oltre questo, grazie mille per l'aiuto!
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); }
Ma ti riferisci ai valori di pivot oppure alla funzione stampa_array() che richiami alla fine nel main?
si è la funzione stampaArray che me li stampa disordinati dopo aver chiamato la mergeSort
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.
Si, prima di mettere il cout funzionava bene, poi no.
"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.
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; }
Non compila il codice che hai postato.