Algoritmi di ordinamento -> Selection sort
Il Selection sort è un algoritmo di ordinamento che opera in-place (o in loco, cioè l'ordinamento viene operato direttamente sull'array in input). Presenta una complessità di O(n[SUP]2[/SUP]) e ciò lo rende piuttosto inefficiente con array di grandi dimensioni (il tempo di esecuzione dipende unicamente dalla dimensione dell'array da ordinare).
L'algoritmo divide l'array in due porzioni: una parte già ordinata e una parte non ordinata. Chiaramente all'inizio la porzione ordinata è vuota, mentre la parte non ordinata coincide con l'array in input.
L'algoritmo procede trovando il minore (o il maggiore a seconda dell'ordinamento che si vuole ottenere) elemento nella parte degli elementi non ordinati e scambiandolo con l'elemento che si trova all'inizio di questa lista. Successivamente si modificano i "confini" della porzione degli elementi già ordinati spostando il limite destro di una posizione (vedi figura)
In giallo la porzione ordinata, in bianco quella da ordinare,
in rosso il minimo elemento corrente, in blu l'elemento valutato attualmente
Codice
Vediamo ora il codice per costruire il comportamento desiderato. Trovate alcuni commenti per capire il significato dato ad alcune variabili e operazioni.
Formattato
N.B. 1: sono di facile costruzione anche varianti che operano non in place
N.B. 2: il ragionamento alla base dell'algoritmo è stato condotto solamente su array, ma può essere esteso ad altre strutture dati
Il Selection sort è un algoritmo di ordinamento che opera in-place (o in loco, cioè l'ordinamento viene operato direttamente sull'array in input). Presenta una complessità di O(n[SUP]2[/SUP]) e ciò lo rende piuttosto inefficiente con array di grandi dimensioni (il tempo di esecuzione dipende unicamente dalla dimensione dell'array da ordinare).
L'algoritmo divide l'array in due porzioni: una parte già ordinata e una parte non ordinata. Chiaramente all'inizio la porzione ordinata è vuota, mentre la parte non ordinata coincide con l'array in input.
L'algoritmo procede trovando il minore (o il maggiore a seconda dell'ordinamento che si vuole ottenere) elemento nella parte degli elementi non ordinati e scambiandolo con l'elemento che si trova all'inizio di questa lista. Successivamente si modificano i "confini" della porzione degli elementi già ordinati spostando il limite destro di una posizione (vedi figura)
In giallo la porzione ordinata, in bianco quella da ordinare,
in rosso il minimo elemento corrente, in blu l'elemento valutato attualmente
Codice
Vediamo ora il codice per costruire il comportamento desiderato. Trovate alcuni commenti per capire il significato dato ad alcune variabili e operazioni.
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Formattato
N.B. 1: sono di facile costruzione anche varianti che operano non in place
N.B. 2: il ragionamento alla base dell'algoritmo è stato condotto solamente su array, ma può essere esteso ad altre strutture dati
Ultima modifica:
