DOMANDA Selection sort C++

[MPG]

Scusate ho appena iniziato velocemente a studiare il selection sort in C++.
Online ho trovato queste dui due esempi, mi potete dire quali dei due seguire?
Diciamo per distinguerli quello che ha data[i ] o l'altro e perchè?
Grazie.

 

[_Achille]

Dovresti scrivertene uno da solo senza guardare esempi degli altri.

 

[DispatchCode]

Scusate ho appena iniziato velocemente a studiare il selection sort in C++.
Online ho trovato queste dui due esempi, mi potete dire quali dei due seguire?
Diciamo per distinguerli quello che ha data[i ] o l'altro e perchè?
Grazie.

La differenza è minima, praticamente non c'è. Nel primo caso mi è sembrato solo di notare l'assegnamento del valore data a min, così da evitare continui accessi all'array ed usare direttamente il valore.
Ad ogni modo non c'è differenza, la complessità rimane la medesima.

Come ti è stato suggerito faresti bene ad implementarlo partendo dalla sua definizione o dallo pseudocodice.

 

[MPG]

La differenza è minima, praticamente non c'è. Nel primo caso mi è sembrato solo di notare l'assegnamento del valore data a min, così da evitare continui accessi all'array ed usare direttamente il valore.
Ad ogni modo non c'è differenza, la complessità rimane la medesima.

Come ti è stato suggerito faresti bene ad implementarlo partendo dalla sua definizione o dallo pseudocodice.

Si ma sto cercando di capirlo per quello chiedo a voi molto piu' esperti di me cosa usereste. Quei due esempi non li ho presi da studenti di superiore come me , ma da esperti che spiegano questo selection sort per cercare perchè si usano due metodi diversi e in cosa consiste questa diversità . Non caspisco bene cosa intendi quando dici "assegnamento del valore data a min, così da evitare continui accessi all'array ed usare direttamente il valore."

 

[DispatchCode]

Nel primo screen che hai mostrato viene fatto:

min = data[i];

e successivamente, nel loop interno e precisamente nell'if, la condizione è:

if(data[j] < min)
{
.....
}

Nel secondo caso:

jmin = i;

e la condizione dell'if è:

if(v[j] < v[jmin])
{
....
}

La differenza è quella che vedi: nel primo caso viene letto il valore in posizione data[i ] e viene memorizzato in min; nel secondo caso non viene utilizzata una variabile di appoggio ma si utilizza direttamente l'array specificando v[jmin].
Sempre nel primo caso, quando si entra nel corpo dell'if, viene letto il nuovo valore ed assegnato a min. Nell'altro si continua ad utilizzare solo l'indice dell'array.
Diciamo quindi che nel primo caso si evita il continuo accesso alla locazione i dell'array.

Nella pratica il discorso è in sè poco utile in quanto vi sono un sacco di altri fattori che andrebbero considerati (compilatore (=> ottimizzazioni), cache, ....) e che renderebbero tutto ciò molto bello in teoria, ma che penso sia meglio evitarti per evitare ulteriore confusione e mettere troppa carne al fuoco.
Se hai però domande specifiche, dettate da conoscenze di base, approfondisco volentieri. ;)

 

[DispatchCode]

Per l'ordinamento dell'array dall 0 al penultimo (l'ultimo va a posto da se') sarebbe cosi'?

selectSort(int arr[], int n)
{
int pos_min,temp;

for (int i=0; i < n-1; i++)
{
    pos_min = i;

for (int j=i+1; j < n; j++)
{

if (arr[j] < arr[pos_min])
                   pos_min=j;

}

              {
                 temp = arr[i];
                 arr[i] = arr[pos_min];
                 arr[pos_min] = temp;
            }
}

A occhio mi sembra corretto.

 

[MPG]

Quindi questo per l'ordinamento dell'array dall 0 al penultimo (l'ultimo va a posto da se') sarebbe meno valido?

selectSort(int arr[], int n)
{
int pos_min,temp;

for (int i=0; i < n-1; i++)
{
    pos_min = i;

for (int j=i+1; j < n; j++)
{

if (arr[j] < arr[pos_min])
                   pos_min=j;

}

              {
                 temp = arr;
                 arr = arr[pos_min];
                 arr[pos_min] = temp;
            }
}

 

[MPG]

SCusa ho ripostato di nuovo perchè mi avevi risposto ma non mi ero accorto.

 

[DispatchCode]

Sono validi e corretti entrambi, la differenza è irrilevante proprio per gli altri fattori che andrebbero considerati.
Il discorso che ho fatto è valido in teoria; supponendo che non ci siano fattori esterni (dalle cache al compilatore), quando accedi ad un array la posizione viene calcolata.
Quindi in pratica l'accesso a questa posizione dell'array arr[pos_min] avviene in questo modo:

arr + (pos_min * sizeof(int))

dove "sizeof(int)" è la dimensione del tipo di dato (in questo caso 4, molto probabilmente).
La cosa furba del primo codice è quindi che viene fatto solo 1 volta quell'accesso all'array, ottenendo direttamente il valore memorizzato in quella posizione così da poterlo utilizzare per le comparazioni successive.

Ma ripeto: è bene saperlo, ma non mi porrei il problema.

 

[MPG]

Se volessi fare un ordine al contrario dal piu' grande al piu' piccolo?

 

[DispatchCode]

Devi invertire la condizione.

 

[MPG]

OK, grazie!