Curiosità su codice selection sort

[ZfreS]

Ho implementato un codice per lo selection sort, è stato facile, ma provando a giocare col codice ho notato una cosa:

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;
   }
   
}


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?

[Super Squirrel]

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.

[ZfreS]

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.

[ZfreS]

Secondo me può andare bene anche così il codice:

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;*/
   }
   
}


[Super Squirrel]

Una cosa alla volta però...

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.

[ZfreS]

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

[vict85]

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.

[ZfreS]

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?

[ZfreS]

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?

[vict85]

Il punto è che parti il ciclo supponendo che il primo elemento sia il più piccolo. Questo "supponendo che" è tradotto in quella inizializzazione.