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 👇
- Domini Internet 🌍
- Informatica 🖥
- Marketing & SEO 🌪
- Mondo Apple 🍎
- Scrivere 🖋
- Sicurezza & Privacy 👁
- Svago 🎈
- WordPress 🤵
- 💬 Il nostro canale Telegram: iscriviti
- 🟡 Alberi decisionali: cosa sono e come funzionano
- 🟠 Che vuol dire sito responsive?
- 🟡 [Permessi CHMOD] Come impostarli sui file di un sito WordPress
