L'algoritmo di ordinamento Selection Sort è un miglioramento dell'algoritmo Bubble Sort poiché cerca di ridurre al minimo il numero di scambi richiesti per ordinare una lista di elementi.
Strategia
La strategia adottata dall'algoritmo prevede un solo scambio per passaggio al
posto degli N-1 richiesti dal Bubble
Sort; l'algoritmo Bubble
Sort porta in cima l'elemento più
grande attraverso un numero di piccoli passi, mentre l'algoritmo Selection
Sort porta in cima l'elemento più grande ad ogni iterazione.
I passaggi eseguiti dal Selection Sort per ordinare una lista di N elementi
prevedono:
- prima iterazione: spostamento dell'elemento più grande tra gli
Nelementi della lista - seconda iterazione: spostamento dell'elemento più grande degli
N-1elementi della lista (non si considera più l'elemento più grande portato in cima all'iterazione precedente) - terza iterazione: spostamento dell'elemento più grande degli
N-2elementi della lista (non consideriamo i due elementi della lista già ordinati) - e così via per tutti gli altri elementi
Per ordinare una lista di N elementi, l'algoritmo Selection Sort ha
bisogno di N-1 passaggi.
Esempio
Per ordinare la lista [9, 8, 7, 6, 5], l'algoritmo Selection Sort prevede
i seguenti passaggi.
Iterazione 0
Impostiamo l'ultimo elemento come elemento massimo ed iteriamo sulle altre posizioni
Iterazione 1
Impostiamo il penultimo elemento come elemento massimo ed iteriamo le altre posizioni, non considerando più l'ultima posizione, ordinata al passaggio precedente
Iterazione 2
Impostiamo il terzultimo elemento come massimo ed iteriamo
Iterazione 3
Impostiamo il quartultimo elemento come massimo e iteriamo
A questo punto possiamo notare che la lista è ordinata.
La strategia descritta può essere applicata considerando l'elemento minimo della lista ad ogni passaggio portandolo in cima alla lista ed iterando per tutte gli indici della lista considerata.
Implementazione in Python
Una possibile implementazione in Python dell'algoritmo Selection Sort, è la seguente:
def selection_sort(elements):
for target_slot in range(len(elements)-1, 0, -1):
print(f"Target Slot: {target_slot}")
max_index = target_slot
for current_index in range(0, target_slot):
print(f"\tCurrent Index:{current_index}")
if elements[current_index] > elements[max_index]:
max_index = current_index
print(f"\tMaxValue:{elements[max_index]}")
elements[target_slot], elements[max_index] = elements[max_index], elements[target_slot]
return elements
Prestazioni
Le prestazioni dell'algoritmo Selection Sort sono in linea con le prestazioni dell'algoritmo Bubble Sort. Nel caso peggiore, infatti, anche l'algoritmo Selection Sort prevede una complessità di O(n²), quindi non dovrebbe essere utilizzato con liste che contengono un elevato numero di elementi.
Rispetto all'algoritmo Bubble Sort, l'algoritmo Selection Sort esegue un minor numero di scambi per ordinare gli elementi O(n).
Conclusioni
L'algoritmo di Selection Sort può essere utilizzato:
- per ordinare liste con pochi elementi
- quando è obbligatorio controllare tutti gli elementi
- quando è importante considerare il numero di scritture che facciamo in memoria (ad esempio quando utilizziamo una memoria flash).