Selection sort in C++, algoritmo di ordinamento per selezione

In questa lezione affronteremo il selection sort in C++, cioè un algoritmo di ordinamento che consiste nel selezionare volta per volta un elemento, quello minore o quello maggiore, all’interno dell’array per poi posizionarlo nella sequenza ordinata.

L’algoritmo selection sort è anche conosciuto come algoritmo per minimi successivi.

L’algoritmo ha una complessità esponenziale θ (n²) sia nel caso peggiore sia nel caso migliore, quindi risulta essere poco efficiente.

Come il bubble sort ordina l’array in più passate.

Facciamo un esempio pratico di come funziona l’algoritmo selection sort. Ho messo in nero i numeri disordinati, in rosso quelli ordinati e in verde quelli cambiati di posto.

Scatena il tuo potenziale con ’50 Algoritmi per imparare C++’, il libro appena lanciato su Amazon che ti guiderà nel mondo della programmazione con passione e precisione!

Acquistalo su Amazon

Array iniziale:

20 – 13 – 40 – 7 – 1 – 37

Primo passaggio: trovo il minimo che è 1, quindi lo sposto in prima posizione:

1 – 13 – 40 – 7 – 20 – 37

Secondo passaggio: trovo il minimo che è 7, quindi:

1 – 7 – 40 – 13 – 20 – 37

Terzo passaggio: trovo il minimo che è 13, quindi:

1 – 7 – 13 – 40 – 20 – 37

Quarto passaggio: trovo il minimo che è 20, quindi:

1 – 7 – 13 – 20 – 40 – 37

Quinto passaggio: trovo il minimo che è 37, quindi:

1 – 7 – 13 – 20 – 37 – 40

Procedimento selection sort in C++

Per realizzare l’algoritmo di ordinamento utilizziamo allora un ciclo esterno con un indice i che va da 0 ad n-2.

Dopo utilizziamo la variabile min che memorizza l’indice a cui punta il valore minimo. Questa variabile è inizializzata al primo elemento: min=i.

Poi realizziamo un ciclo interno utilizzando un indice j che va da i+1 (posizione successiva ad i) fino ad n.

Infine controlliamo se il numero puntato dall’indice j è più piccolo del min e se è vero lo scambiamo. Per effettuare lo scambio utilizzo una variabile temporanea temp.

Ecco quindi il listato completo dell’algoritmo selection sort in C++.

#include<iostream>
using namespace std;

#define N 6

int main() {
    int i, j, min, temp;
    int a[N];

    cout << "Inserisci gli elementi:\n"; 
    for(i = 0; i < N; i++)
        cin >> a[i];

    for(i = 0; i < N - 1; i++) {
        min = i;
        for(j = i + 1; j < N; j++)
            if (a[j] < a[min])
                min = j;

        temp = a[min];
        a[min] = a[i];
        a[i] = temp;
    }
    
    cout << "Array ordinato con selection sort:";
    for(i = 0; i < N; i++)
        cout << " " << a[i];
        
    return 0;
}

Questo è un esempio di possibile implementazione del selection sort in C++.