Selection sort è un semplice algoritmo di ordinamento. Questo algoritmo di ordinamento è un algoritmo basato sul confronto sul posto in cui l’elenco è diviso in due parti, la parte ordinata all’estremità sinistra e la parte non ordinata all’estremità destra. Inizialmente, la parte ordinata è vuota e la parte non ordinata è l’intero elenco.
L’elemento più piccolo viene selezionato dall’array non ordinato e scambiato con l’elemento più a sinistra, e quell’elemento diventa parte dell’array ordinato. Questo processo continua a spostare il limite dell’array non ordinato di un elemento a destra.
Questo algoritmo non è adatto per set di dati di grandi dimensioni poiché le sue complessità medie e peggiori sono di Ο(n2), dove n è il numero di elementi.
Come funziona l’ordinamento di selezione?
Considera il seguente array raffigurato come esempio.
Per la prima posizione nell’elenco ordinato, l’intero elenco viene scansionato in sequenza. La prima posizione in cui è memorizzato 14 attualmente, cerchiamo l’intera lista e scopriamo che 10 è il valore più basso.
Quindi sostituiamo 14 con 10. Dopo un’iterazione 10, che sembra essere il valore minimo nell’elenco, appare nella prima posizione dell’elenco ordinato.
Per la seconda posizione, dove risiede 33, iniziamo la scansione del resto dell’elenco in modo lineare.
Troviamo che 14 è il secondo valore più basso nella lista e dovrebbe apparire al secondo posto. Scambiamo questi valori.
Dopo due iterazioni, due valori minimi vengono posizionati all’inizio in modo ordinato.
Lo stesso processo viene applicato al resto degli elementi nell’array.
Di seguito è riportata una rappresentazione pittorica dell’intero processo di ordinamento −
Ora, impariamo alcuni aspetti di programmazione dell’ordinamento di selezione.
Algoritmo
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
Pseudocodice
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
Per conoscere l’implementazione dell’ordinamento di selezione nel linguaggio di programmazione C, fare clic qui.