L’algoritmo di selection sort è un semplice algoritmo di ordinamento che seleziona ripetutamente l’elemento più piccolo (o più grande, a seconda dell’implementazione) dall’array non ordinato e lo posiziona nella giusta posizione nell’array ordinato. Il funzionamento dell’algoritmo si può desumere da questo semplice video, che mostra anche il “suono” emesso dall’algoritmo: una strana sinfonia che ricorda un pianoforte jazz o un brano sperimentale, in cui si mette progressivamente ordine al caos fino ad arrivare all’ordinamento finale. Il risultato è spettacolare e merita certamente di essere ascoltato!
Teoria
Il Selection Sort di fatto è un algoritmo di ordinamento che funziona trovando il valore massimo (o minimo) e posizionandolo nella giusta posizione, iterando attraverso la lista di elementi. Le due fasi che hai menzionato, “max(A)” e “swap(max(A), A[j])”, rappresentano due passaggi fondamentali all’interno del Selection Sort:
- max(A): In questa fase, l’algoritmo cerca il valore massimo all’interno dell’array non ordinato A. Scansiona tutti gli elementi dalla posizione 0 fino a una posizione specifica j (inizialmente, j è l’ultima posizione dell’array, quindi decrementa ad ogni iterazione). Durante questa scansione, tiene traccia del valore massimo trovato finora.
- swap(max(A), A[j]): Una volta trovato il valore massimo all’interno dell’array non ordinato A, l’algoritmo esegue uno scambio tra il valore massimo e l’elemento corrispondente alla posizione j. Questo posiziona il valore massimo nella sua posizione corretta all’interno della lista ordinata, ponendo l’elemento più grande (o più piccolo, a seconda dell’implementazione) nell’ultima posizione dell’array ordinato.
Il processo continua con la riduzione di j (il “cursore a ritroso”) per analizzare l’elemento precedente nella lista non ordinata e posizionare il valore massimo successivo (o minimo) nella posizione corretta. Questo procedimento viene ripetuto finché l’intera lista non è ordinata.
Funzionamento del selection sort nel dettaglio
Il Selection Sort è un algoritmo di ordinamento che opera selezionando ripetutamente l’elemento più piccolo (o più grande, a seconda dell’implementazione) e posizionandolo nella sua posizione corretta all’interno dell’array ordinato.
Funzionamento del Selection Sort
In altri termini la fase “max(A)” individua il valore massimo nell’array non ordinato fino a una posizione specifica, mentre la fase “swap(max(A), A[j])” sposta il valore massimo trovato nella sua corretta posizione nell’array ordinato. Iterando attraverso questa procedura per ogni elemento, l’array viene ordinato dall’alto verso il basso (o dal basso verso l’alto, a seconda dell’implementazione). L ‘algoritmo – vedi anche video successivo – segue due fasi principali:
- Individuazione del massimo (o minimo) nell’array non ordinato
- Si scansiona la porzione non ordinata dell’array per trovare il valore massimo (o minimo).
- Questo valore viene identificato confrontando tutti gli elementi dalla posizione 0 fino a una posizione specifica j.
- All’inizio, j è l’ultima posizione dell’array e viene decrementata a ogni iterazione.
- Scambio del massimo (o minimo) con l’elemento in posizione j
- Dopo aver trovato l’elemento massimo (o minimo), viene scambiato con l’elemento che si trova in j.
- Questo posiziona il valore trovato nella sua posizione corretta all’interno dell’array ordinato.
Iterazioni successive
- Dopo ogni scambio, j viene decrementato per restringere la porzione dell’array da analizzare.
- L’algoritmo continua fino a ordinare completamente l’intera lista.
In sintesi, il Selection Sort garantisce che, ad ogni passaggio, il valore massimo (o minimo) venga spostato alla sua posizione definitiva, riducendo progressivamente la porzione non ordinata dell’array.
Esempio pratico di selection sort
Passo 1:
Consideriamo un array iniziale come A=[7,2,9,4,5], giusto per fare un esempio.
Passo 2:
Si inizia con l’iterazione dell’array per trovare il valore più piccolo. Utilizzeremo una funzione astratta
min_index(A, start)
che restituisce l’indice dell’elemento più piccolo nell’array A a partire dall’indice ‘start’.
-
min_index(A, 0)restituirà l’indice 1 (valore 2) poiché 2 è il più piccolo nell’array.
Passo 3:
Si effettua lo swap tra l’elemento in posizione 0 (7) e l’elemento più piccolo trovato (2). La funzione
swap(a, b)
scambia gli elementi nella posizione ‘a’ e ‘b’.
- Dopo lo swap, l’array diventerà A=[2,7,9,4,5].
Passo 4:
Ora si itera sull’array rimanente (escludendo il primo elemento già ordinato).
-
min_index(A, 1)restituirà l’indice 3 (valore 4) poiché 4 è il più piccolo nell’array escludendo il primo elemento.
Passo 5:
Si effettua lo swap tra l’elemento in posizione 1 (7) e l’elemento più piccolo trovato (4).
- Dopo lo swap, l’array diventerà a questo passo A=[2,4,9,7,5].
Passo 6:
Si procede iterando sull’array rimanente.
-
min_index(A, 2)restituirà l’indice 4 (valore 5) poiché 5 è il più piccolo nell’array escludendo i primi due elementi.
Passo 7:
Si effettua lo swap tra l’elemento in posizione 2 (9) e l’elemento più piccolo trovato (5).
- Dopo lo swap, l’array diventa A=[2,4,5,7,9].
Passo 8:
L’array è ordinato completamente, abbiamo finito!
Origine e efficacia dell’algoritmo:
L’algoritmo di selection sort è stato ideato da un informatico chiamato John von Neumann nel 1956. È un algoritmo semplice e intuitivo, ma non è efficiente come alcuni altri algoritmi di ordinamento, specialmente per grandi insiemi di dati. La sua complessità temporale è di O(n^2), dove ‘n’ è la dimensione dell’array. Questo lo rende inefficiente per grandi dataset, ma può essere utile per piccoli set di dati o come punto di partenza per capire i concetti di ordinamento.
Viene spesso studiato come esempio introduttivo di algoritmi di ordinamento poiché è facile da comprendere e implementare, e offre una buona base per capire altri algoritmi più efficienti come il quicksort o il mergesort.
👇 Contenuti da non perdere 👇
- Domini Internet 🌍
- Marketing & SEO 🌪
- Meteo
- Programmare 🖥
- Reti 💻
- WordPress 🤵
- 💬 Il nostro canale Telegram: iscriviti
- 🟠 Troppi tentativi Telegram: cosa vuol dire
- 🟡 Domini .company: come e dove registrarne uno
- 🔴 Registrazione domini .ZERO
