Selection sort in C++

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 θ (n2) 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.

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:

17 – 40 – 13 – 20 – 37

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

171340 – 20 – 37

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

17132040 – 37

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

1713203740


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

Alcuni link utili

Esercizi con gli array in C++

Esercitazione sugli array in C++

Array in C++

Passaggio di parametri per valore o per riferimento

Equazioni di secondo grado in C++

Le variabili globali e loali in C++

Uso delle funzioni in C++

Funzioni in C++

Definizione di funzioni in C++

Libreria cmath

Come usare il for in C++

Massimo tra n numeri in C++

Iterazioni in C++

Ciclo while in C++

Ciclo do while

Operatori logici in C++

Esercizi con switch case in C++

If else in C++

Casting in C++

Tutorial C++

Successione di Fibonacci in C++

Autore dell'articolo: Cristina

Avatar per Coding Creativo

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *