Come utilizzare l'ordinamento di selezione

L'ordinamento di selezione è una tecnica di ordinamento che seleziona un elemento dell'elenco e quindi ne scambia il posto con un altro. Seleziona l'elemento più grande e poi lo scambia con un elemento nell'indice più alto dell'elenco.

L'algoritmo esegue questa operazione ripetutamente finché l'elenco non viene ordinato. Se non sei sicuro di come funziona l'ordinamento per selezione, sei nel posto giusto. Lo spiegheremo in modo più approfondito di seguito, oltre a mostrarti un esempio.

Ordinamento di selezione: uno sguardo più da vicino

Supponiamo di avere la lista: [39, 82, 2, 51, 30, 42, 7]. Per ordinare l'elenco utilizzando l'ordinamento per selezione, dovresti prima trovare il numero più alto in esso.

Con l'elenco fornito, quel numero è 82. Scambia 82 con il numero nell'indice più alto (cioè 7).

Dopo il primo passaggio, il nuovo ordine delle liste sarà: [39, 7, 2, 51, 30, 42, 82]. Ogni volta che l'algoritmo passa attraverso l'intero elenco, questo viene chiamato "pass".

Si noti che l'elenco mantiene un sottoelenco ordinato e un sottoelenco non ordinato durante il processo di ordinamento.

Relazionato: Che cos'è la notazione Big-O?

L'elenco originale inizia con un elenco ordinato di zero elementi e un elenco non ordinato di tutti gli elementi. Quindi, dopo il primo passaggio, ha un elenco ordinato con solo il numero 82.

Al secondo passaggio, il numero più alto nella sottolista non ordinata sarà 51. Questo numero verrà scambiato con 42 per dare il nuovo ordine della lista di seguito:

[39, 7, 2, 42, 30, 51, 82].

Il processo viene ripetuto fino a quando non viene ordinato l'intero elenco. La figura seguente riassume l'intero processo:

I numeri in grassetto nero mostrano il valore di elenco più alto in quel momento. Quelli in verde mostrano la sottolista ordinata.

Analisi dell'algoritmo

Per ottenere la complessità (usando la notazione Big-O) di questo algoritmo, segui di seguito:

Al primo passaggio, vengono effettuati (n-1) confronti. Al secondo passaggio, (n-2). Al terzo passaggio, (n-3) e così via fino al passaggio (n-1) che fa un solo confronto.

Riassumendo i confronti come di seguito si ottiene:

(n-1)+ (n-1)+ (n-1)+...+1 = ((n-1)n)/2.

Quindi l'ordinamento di selezione è O(n²).

Implementazione del codice

Il codice mostra le funzioni che è possibile utilizzare per eseguire l'ordinamento di selezione utilizzando Python e Java.

Pitone:

def selectionSort (mylist):
per x nell'intervallo (len (mylist) - 1, 0, -1):
max_idx = 0
per posizione nell'intervallo (1, x + 1):
if mialista[posn] > mialista[max_idx]:
max_idx = posizione
temp = mialista[x]
mialista[x] = mialista[max_idx]
mialista[max_idx] = temp

Giava:

void selectionSort (int my_array[]){ 
per (int x = 0; x < my_array.length - 1; x++) 
{ 
int indice = x; 
per (int y = x + 1; y < mio_array.length; y++){ 
if (mio_array[y] < mio_array[indice]){ 
indice = y; // trova l'indice più basso 
} 
} 
int temp = mio_array[indice]; // temp è un archivio temporaneo
mio_array[indice] = mio_array[x]; 
mio_array[x] = temperatura; 
}}

Passare dall'ordinamento di selezione all'ordinamento di unione

Come ha mostrato l'analisi dell'algoritmo sopra, l'algoritmo di ordinamento per selezione è O(n²). Ha una complessità esponenziale ed è quindi inefficiente per set di dati molto grandi.

Un algoritmo molto migliore da usare sarebbe il merge sort con una complessità di O(nlogn). E ora che sai come funziona l'ordinamento di selezione, il prossimo elenco di studi per gli algoritmi di ordinamento dovrebbe essere il merge sort.

Circa l'autore