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.
Passo 1:
Consideriamo un array iniziale come A=[7,2,9,4,5].
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 diventa 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 diventa 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.
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.
👇 Da non perdere 👇
- Gratis 🎉
- intelligenza artificiale 👁
- Marketing & SEO 🌪
- Programmare 🖥
- Spiegoni artificiali 🎓
- 💬 Il nostro canale Telegram: iscriviti
- 🟡 Come configurare OPCache per PHP
- 🔴 Non c’è posto come 127.0.0.1 non fa ridere
- 🔴 Cos’è una mesh in grafica 3D