Curiosità su codice selection sort

[ZfreS]

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.

[ZfreS]

Potreste confermare le mie ipotesi o no?

[vict85]

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:

1. 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,
2. 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,
3. 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.

Per esempio, il codice che hai scritto nel primo messagio poteva essere scritto così

Codice:

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 i e j all'interno del for:

Codice:

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¹

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):

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[j] < min)
            {
                min = arr[j];
                min_ind = j;
            }
        }

        tmp = arr[i];
        arr[i] = arr[min_ind];
        arr[min_ind] = tmp;
    }
}

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

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 min è una variabile inutile: si potrebbe usare arr[min_ind] al suo posto (al contrario non puoi fare a meno di min_ind a meno di riscrivere il codice con i puntatori). Quindi in sostanza, riinizzializzi min_ind perché min == arr[min_ind] 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 arr[0] è il minimo dell'array, min ha lo stesso valore di arr[0] e min_ind è l'indice in cui arr[0] è stato spostato. A questo punto divido in due casi: min_ind == 0 e min_ind != 0.
Nel primo caso, se l'array è ordinato, allora scambi arr[0] con arr[1]. E' interessante notare che finirai per scambiare arr[0] con arr[2] e così via. Il risultato finale sarà che avrai "ruotato" l'array.
Il secondo caso è simile, ma j assumerà il valore min_ind durante il ciclo. Pertanto si potrebbe "risolvere" controllando che arr[1] sia effettivamente maggiore di arr[min_ind], ma questo trucco non funziona nel primo caso.

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 j è sempre uguale a num_ele mentre, nel caso corretto,

Codice:

min_ind

ha un valore imprecisato tra i e num_ele-1 (valori compresi). Ho l'impressione che tu stia ignorando completamente quell'if.

---

Note

1. Per esempio, questo codice

   Codice:

   #include <stdio.h>

int main()
{
    int i = 0;
    {
        int i = 2;
    }
    printf("%d", i);
}

   è valido e stampa a schermo 0. ↑

[ZfreS]

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[i] 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[i] 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?

[vict85]

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[i] dove i=0, invece prima di correggere il codice, avevo inizializzato min_ind dentro l'if del secondo for.

Inizializzare qualcosa dentro un if ha senso solo se quell'if è sempre vero, in caso contrario ci sono casi in cui la variabile assume valori imprecisati.

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[i] 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' min_ind ad avere un valore imprecisato tra i e num_ele-1 (valori compresi). Dove con imprecisato intendo che dipende dal particolare input. j, alla fine del ciclo interno, è sempre uguale a num_ele.

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.

[ZfreS]

In poche parole min_ind và inizializzato fuori dal secondo for perhè il primo elemento potrebbe effettivamente essere il minimo, giusto?

[vict85]

Si, esatto.

[ZfreS]

Perfetto, allora tutto chiaro, grazie mille per l'assistenza, anche a SuperSquirrel, buona giornata!