Curiosità su codice selection sort
Ho implementato un codice per lo selection sort, è stato facile, ma provando a giocare col codice ho notato una cosa:
Se commento la riga in cui scrivo min_ind = i, quando chiamo la stamap dopo aver ordinato l'array, uesto mi viene stampato in disordine anzichè in ordine. Come mai quell'inizializzazione è così importante, anche se viene usata dopo e quindi si potrebbe inizializzare dopo?
void selectionSort(int arr[], int num_ele)
{
int min, min_ind, tmp, j, i;
for (i = 0; i < num_ele - 1; i++)
{
min = arr[i];
min_ind = i;
for (j = i + 1; j < num_ele; j++)
if (arr[j] < min)
{
min = arr[j];
min_ind = j;
}
tmp = arr[i];
arr[i] = arr[min_ind];
arr[min_ind] = tmp;
}
}
Se commento la riga in cui scrivo min_ind = i, quando chiamo la stamap dopo aver ordinato l'array, uesto mi viene stampato in disordine anzichè in ordine. Come mai quell'inizializzazione è così importante, anche se viene usata dopo e quindi si potrebbe inizializzare dopo?
Risposte
Come mai quell'inizializzazione è così importante, anche se viene usata dopo e quindi si potrebbe inizializzare dopo?
min_ind = j; si trova all'interno di un if, non è detto che la condizione dell'if sia rispettata.
Non so bene cosa intendi con "ho implementato", ma se sei arrivato a quell'algoritmo attraverso un ragionamento, trovo strano che tu abbia questo genere di dubbi.
Ho letto l'algoritmo su internet e poi ho provato ad implementarlo. L'ho anche provato su carta con questo array: 5 3 7 8 2 9 e non dovrebbe dare problemi perchè la prima condizione dell'if viene rispettata.
Secondo me può andare bene anche così il codice:
void selectionSort(int arr[], int num_ele)
{
int/* min, min_ind,*/ tmp, j, i;
for (i = 0; i < num_ele - 1; i++)
{
//min = arr[i];
//min_ind = i;
for (j = i + 1; j < num_ele; j++)
if (arr[i] > arr[j])
{
//min = arr[j];
//min_ind = j;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/*tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;*/
}
}
Una cosa alla volta però...
1)
Non sto capendo, a quale codice ti riferisci? A quello del primo post con la riga min_ind = i; commentata?
Se così fosse dando il pasto al programma l'array 5 3 7 8 2 9, il risultato è sbagliato... peraltro sei stato tu stesso che nel primo post hai chiesto:
2)
A funzionare funziona, ma non credo possa essere classificato come selection sort... si avvicina di più ad un bubble sort mal congegnato.
1)
L'ho anche provato su carta con questo array: 5 3 7 8 2 9 e non dovrebbe dare problemi perchè la prima condizione dell'if viene rispettata.
Non sto capendo, a quale codice ti riferisci? A quello del primo post con la riga min_ind = i; commentata?
Se così fosse dando il pasto al programma l'array 5 3 7 8 2 9, il risultato è sbagliato... peraltro sei stato tu stesso che nel primo post hai chiesto:
Come mai quell'inizializzazione è così importante, anche se viene usata dopo e quindi si potrebbe inizializzare dopo?
2)
Secondo me può andare bene anche così il codice: ...
A funzionare funziona, ma non credo possa essere classificato come selection sort... si avvicina di più ad un bubble sort mal congegnato.
A parte il secondo metodo, il fatto è che io la prima volta che ho scritto l'insertion sort quella inizializzazione non l'avevo messa li ma dentro, poi non funzionava e l'ho provata e mettere fuori ed ha funzionato, ma non ho capito il perchè di ciò.
Come implementeresti la funzione che trova l'indice del minimo negli ultimi n elementi di un array di dimensione m? Quella riga che non capisci, non è altro che l'inizializzazione della ricerca del minimo nel sottoarray.
Spiego il codice, poi vediamo dov'è l'errore nel mio ragionamento che feci all'inizio: nel ciclo esterno si prende come minimo valore il primo elemento dell'array, poi si controlla se più avanti ci sono elementi più piccoli di quello, se si trova allora lo si segna come minimo e si segna la posizione di quel nuovo valore minimo, poi si continua a cercare fino a finire l'array, poi si scambia il primo valore dell'array con il minimo trovato. Mi chiedo a cosa serva l'inizializzazione dell'indice dell'elemnto minore dell'rray se tanto poi viene sovrascritto. Se l'if non venisse rispettata vuol dire che il primo elemento è il minimo e quindi non bisogna scambiare nulla, quindi davvero non capisco il senso di quell'inizializzazione. Poi riguardando il codice mi sono chiesto: nella parte dello scambio al posto di scrivere arr[min_ind] non posso scrivere arr[j] visto che sia j che min_ind contengolo lo stesso valore alla fine del ciclo for interno?
Forse ho capito perhè: memorizzare il min_ind prima del ciclo interno serve perchè lo scambio poi viene effettuato comunque sulla stessa posizione, anche se tutti gli if del for interno vengono valutati false. Giusto o no? Se è così allora si può non inizializzare fuori dal for quel min_ind ma fare un controllo dopo il for e prima dello scambio per vedere se non ci sono stati aggiornamenti sul minor elemento. Ma questo penso che non convenga in termini di prestazioni. Dico bene o sbaglio?
Il punto è che parti il ciclo supponendo che il primo elemento sia il più piccolo. Questo "supponendo che" è tradotto in quella inizializzazione.
Infatti ho detto che se, la mia supposizione fosse vera, tutti i for non verrebbero eseguiti ed il primo elemento verrebbe scambiato con se stesso, anche se questo potrebbe essere evitato, ma con un calo di prestazioni, credo.
Potreste confermare le mie ipotesi o no?
Prima di cominciare a rispondere alla tua domanda apro una piccola parentesi. Vari professori insegnano a definire le variabili all'inizio di una funzione, ma ritengo che dovrebbero smetterla. Viene insegnato perché nello standard del 1989 del C, il primo, era richiesto qualcosa di simile. D'altra parte:
[list=1][*:sismuz00] Nei successivi due standard questa limitazione è stata rimossa e, seppur lo standard del 1999 sia stato sostanzialmente ignorato, quello del 2011 è stato apprezzato ed è attualmente supportato da tutti i compilatori,[/*:m:sismuz00]
[*:sismuz00] Questa specifica limitazione era legata a limitazioni dei compilatori dell'epoca. Nel C++ non è mai stato necessario e molti compilatori permettevano di ignorare la cosa già 15 anni fa,[/*:m:sismuz00]
[*:sismuz00] Il C89 non richiedeva di dichiarare le variabili all'inizio della funzione, ma del blocco di codice in cui sono valide. Questo vuol dire che se una variabile viene usata solo dentro un ciclo, la puoi definire dentro il ciclo.[/*:m:sismuz00][/list:o:sismuz00]
Per esempio, il codice che hai scritto nel primo messagio poteva essere scritto così
già nel 1989. Attualmente puoi spostare la definizione di [inline]i[/inline] e [inline]j[/inline] all'interno del for:
Limitare la validità di una variabile rende i codici più leggibili e gestibili. Certo, a meno che non si abbia a che fare con casi di shadowing[nota]Per esempio, questo codice
Ovviamente, dopo le mie modifiche, il commentare quella riga non è più possibile. Quindi concentriamoci sulla tua versione (ho solo aggiunto le parentesi al for e formattato):
Quindi avevi inizializzato [inline]min_ind[/inline] a zero fuori dal primo for? Se non lo hai fatto e hai commentato [inline]min_ind = i;[/inline] allora nello scambio potresti usare una variabile non inizializzata/casuale e quindi è sbagliato a prescindere. Ricorda: il C non inizializza a zero le variabili intere se non in pochi casi particolari.
Prima di tutto, il ciclo interno potrebbe non cambiare affatto il suo valore. Nota che [inline]min[/inline] è una variabile inutile: si potrebbe usare [inline]arr[min_ind][/inline] al suo posto (al contrario non puoi fare a meno di [inline]min_ind[/inline] a meno di riscrivere il codice con i puntatori). Quindi in sostanza, riinizzializzi [inline]min_ind[/inline] perché [inline]min == arr[min_ind][/inline] deve essere una invariante del ciclo (lo scambio rompe questa invariante ma è poco importante).
Ora, supponiamo che la variabile sia inizializzata a 0 fuori dal ciclo grande. Quindi la prima ripetizione è 100% corretta. Alla fine della prima ripetizione [inline]arr[0][/inline] è il minimo dell'array, [inline]min[/inline] ha lo stesso valore di [inline]arr[0][/inline] e [inline]min_ind[/inline] è l'indice in cui [inline]arr[0][/inline] è stato spostato. A questo punto divido in due casi: [inline]min_ind == 0[/inline] e [inline]min_ind != 0[/inline].
Nel primo caso, se l'array è ordinato, allora scambi [inline]arr[0][/inline] con [inline]arr[1][/inline]. E' interessante notare che finirai per scambiare [inline]arr[0][/inline] con [inline]arr[2][/inline] e così via. Il risultato finale sarà che avrai "ruotato" l'array.
Il secondo caso è simile, ma [inline]j[/inline] assumerà il valore [inline]min_ind[/inline] durante il ciclo. Pertanto si potrebbe "risolvere" controllando che [inline]arr[1][/inline] sia effettivamente maggiore di [inline]arr[min_ind][/inline], ma questo trucco non funziona nel primo caso.
Non è vero che contengono lo stesso valore. Alla fine del ciclo [inline]j[/inline] è sempre uguale a [inline]num_ele[/inline] mentre, nel caso corretto,
[list=1][*:sismuz00] Nei successivi due standard questa limitazione è stata rimossa e, seppur lo standard del 1999 sia stato sostanzialmente ignorato, quello del 2011 è stato apprezzato ed è attualmente supportato da tutti i compilatori,[/*:m:sismuz00]
[*:sismuz00] Questa specifica limitazione era legata a limitazioni dei compilatori dell'epoca. Nel C++ non è mai stato necessario e molti compilatori permettevano di ignorare la cosa già 15 anni fa,[/*:m:sismuz00]
[*:sismuz00] Il C89 non richiedeva di dichiarare le variabili all'inizio della funzione, ma del blocco di codice in cui sono valide. Questo vuol dire che se una variabile viene usata solo dentro un ciclo, la puoi definire dentro il ciclo.[/*:m:sismuz00][/list:o:sismuz00]
Per esempio, il codice che hai scritto nel primo messagio poteva essere scritto così
void selectionSort(int arr[], int num_ele)
{
int i = 0;
for (; i < num_ele - 1; i++)
{
int min = arr[i];
int min_ind = i;
int j = i +1;
for (; j < num_ele; j++)
{
if (arr[j] < min)
{
min = arr[j];
min_ind = j;
}
}
// swap function
{
int const tmp = arr[i];
arr[i] = arr[min_ind];
arr[min_ind] = tmp;
}
}
}già nel 1989. Attualmente puoi spostare la definizione di [inline]i[/inline] e [inline]j[/inline] all'interno del for:
for (int i = 0; i < num_ele - 1; i++)
Limitare la validità di una variabile rende i codici più leggibili e gestibili. Certo, a meno che non si abbia a che fare con casi di shadowing[nota]Per esempio, questo codice
#include <stdio.h>
int main()
{
int i = 0;
{
int i = 2;
}
printf("%d", i);
} è valido e stampa a schermo 0.[/nota]Ovviamente, dopo le mie modifiche, il commentare quella riga non è più possibile. Quindi concentriamoci sulla tua versione (ho solo aggiunto le parentesi al for e formattato):
void selectionSort(int arr[], int num_ele)
{
int min, min_ind, tmp, j, i;
for (i = 0; i < num_ele - 1; i++)
{
min = arr[i];
min_ind = i;
for (j = i + 1; j < num_ele; j++)
{
if (arr[j] < min)
{
min = arr[j];
min_ind = j;
}
}
tmp = arr[i];
arr[i] = arr[min_ind];
arr[min_ind] = tmp;
}
}"olegfresi":
Spiego il codice, poi vediamo dov'è l'errore nel mio ragionamento che feci all'inizio: nel ciclo esterno si prende come minimo valore il primo elemento dell'array, poi si controlla se più avanti ci sono elementi più piccoli di quello, se si trova allora lo si segna come minimo e si segna la posizione di quel nuovo valore minimo, poi si continua a cercare fino a finire l'array, poi si scambia il primo valore dell'array con il minimo trovato.
Quindi avevi inizializzato [inline]min_ind[/inline] a zero fuori dal primo for? Se non lo hai fatto e hai commentato [inline]min_ind = i;[/inline] allora nello scambio potresti usare una variabile non inizializzata/casuale e quindi è sbagliato a prescindere. Ricorda: il C non inizializza a zero le variabili intere se non in pochi casi particolari.
"olegfresi":
Mi chiedo a cosa serva l'inizializzazione dell'indice dell'elemnto minore dell'rray se tanto poi viene sovrascritto. Se l'if non venisse rispettata vuol dire che il primo elemento è il minimo e quindi non bisogna scambiare nulla, quindi davvero non capisco il senso di quell'inizializzazione.
Prima di tutto, il ciclo interno potrebbe non cambiare affatto il suo valore. Nota che [inline]min[/inline] è una variabile inutile: si potrebbe usare [inline]arr[min_ind][/inline] al suo posto (al contrario non puoi fare a meno di [inline]min_ind[/inline] a meno di riscrivere il codice con i puntatori). Quindi in sostanza, riinizzializzi [inline]min_ind[/inline] perché [inline]min == arr[min_ind][/inline] deve essere una invariante del ciclo (lo scambio rompe questa invariante ma è poco importante).
Ora, supponiamo che la variabile sia inizializzata a 0 fuori dal ciclo grande. Quindi la prima ripetizione è 100% corretta. Alla fine della prima ripetizione [inline]arr[0][/inline] è il minimo dell'array, [inline]min[/inline] ha lo stesso valore di [inline]arr[0][/inline] e [inline]min_ind[/inline] è l'indice in cui [inline]arr[0][/inline] è stato spostato. A questo punto divido in due casi: [inline]min_ind == 0[/inline] e [inline]min_ind != 0[/inline].
Nel primo caso, se l'array è ordinato, allora scambi [inline]arr[0][/inline] con [inline]arr[1][/inline]. E' interessante notare che finirai per scambiare [inline]arr[0][/inline] con [inline]arr[2][/inline] e così via. Il risultato finale sarà che avrai "ruotato" l'array.
Il secondo caso è simile, ma [inline]j[/inline] assumerà il valore [inline]min_ind[/inline] durante il ciclo. Pertanto si potrebbe "risolvere" controllando che [inline]arr[1][/inline] sia effettivamente maggiore di [inline]arr[min_ind][/inline], ma questo trucco non funziona nel primo caso.
"olegfresi":
Poi riguardando il codice mi sono chiesto: nella parte dello scambio al posto di scrivere arr[min_ind] non posso scrivere arr[j] visto che sia j che min_ind contengolo lo stesso valore alla fine del ciclo for interno?
Non è vero che contengono lo stesso valore. Alla fine del ciclo [inline]j[/inline] è sempre uguale a [inline]num_ele[/inline] mentre, nel caso corretto,
min_indha un valore imprecisato tra [inline]i[/inline] e [inline]num_ele-1[/inline] (valori compresi). Ho l'impressione che tu stia ignorando completamente quell'[inline]if[/inline].
Quindi avevi inizializzato min_ind a zero fuori dal primo for? Se non lo hai fatto e hai commentato min_ind = i; allora nello scambio potresti usare una variabile non inizializzata/casuale e quindi è sbagliato a prescindere. Ricorda: il C non inizializza a zero le variabili intere se non in pochi casi particolari.
Fuori dal primo for l'ho solo dichiarata senza inizializzarla,, poi quando ho corretto il codice l'ho inizializzata all'indice del valore minimo ovvero ad aar dove i=0, invece prima di correggere il codice, avevo inizializzato min_ind dentro l'if del secondo for.
Non è vero che contengono lo stesso valore. Alla fine del ciclo j è sempre uguale a num_ele mentre, nel caso corretto, ha un valore imprecisato tra i e num_ele-1 (valori compresi). Ho l'impressione che tu stia ignorando completamente quell'if.
Non capisco perchè la j ha un valore impecisato. Cosa sto ignorando dell'if? Se l'if non venisse eseguito min rimarrebbe arr e min_ind rimarrebbe i. In pratica sia min che min_ind "puntano" alla prima cella dell'array(se il primo elementoè effettivamente il più piccolo) o sbglio?
E' interessante notare che finirai per scambiare arr[0] con arr[2]
Come mai accadrebbe questo?
"olegfresi":
Quindi avevi inizializzato min_ind a zero fuori dal primo for? Se non lo hai fatto e hai commentato min_ind = i; allora nello scambio potresti usare una variabile non inizializzata/casuale e quindi è sbagliato a prescindere. Ricorda: il C non inizializza a zero le variabili intere se non in pochi casi particolari.
Fuori dal primo for l'ho solo dichiarata senza inizializzarla,, poi quando ho corretto il codice l'ho inizializzata all'indice del valore minimo ovvero ad aar dove i=0, invece prima di correggere il codice, avevo inizializzato min_ind dentro l'if del secondo for.
Inizializzare qualcosa dentro un [inline]if[/inline] ha senso solo se quell'[inline]if[/inline] è sempre vero, in caso contrario ci sono casi in cui la variabile assume valori imprecisati.
"olegfresi":
Non è vero che contengono lo stesso valore. Alla fine del ciclo j è sempre uguale a num_ele mentre, nel caso corretto, ha un valore imprecisato tra i e num_ele-1 (valori compresi). Ho l'impressione che tu stia ignorando completamente quell'if.
Non capisco perchè la j ha un valore impecisato. Cosa sto ignorando dell'if? Se l'if non venisse eseguito min rimarrebbe arr e min_ind rimarrebbe i. In pratica sia min che min_ind "puntano" alla prima cella dell'array(se il primo elementoè effettivamente il più piccolo) o sbglio?
Ho usato il tag sbagliato. E' [inline]min_ind[/inline] ad avere un valore imprecisato tra [inline]i[/inline] e [inline]num_ele-1[/inline] (valori compresi). Dove con imprecisato intendo che dipende dal particolare input. [inline]j[/inline], alla fine del ciclo interno, è sempre uguale a [inline]num_ele[/inline].
"olegfresi":
E' interessante notare che finirai per scambiare arr[0] con arr[2]
Come mai accadrebbe questo?
Ho eseguito l'algoritmo a mente nel caso in cui l'array sia ordinato. Ma ti invito a seguire l'esecuzione con un debugger e cercare di capire il perché delle varie cose.
In poche parole min_ind và inizializzato fuori dal secondo for perhè il primo elemento potrebbe effettivamente essere il minimo, giusto?
Si, esatto.
Perfetto, allora tutto chiaro, grazie mille per l'assistenza, anche a SuperSquirrel, buona giornata!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo