Cos'è l'ordinamento di selezione?
SELECTION SORT è un algoritmo di ordinamento per confronto utilizzato per ordinare un elenco casuale di elementi in ordine crescente. Il confronto non richiede molto spazio extra. Richiede solo uno spazio di memoria aggiuntivo per la variabile temporale.
Questo è noto come ordinamento sul posto . L'ordinamento della selezione ha una complessità temporale di O (n 2 ) dove n è il numero totale di elementi nell'elenco. La complessità temporale misura il numero di iterazioni necessarie per ordinare l'elenco. L'elenco è diviso in due partizioni: il primo elenco contiene elementi ordinati, mentre il secondo elenco contiene elementi non ordinati.
Per impostazione predefinita, l'elenco ordinato è vuoto e l'elenco non ordinato contiene tutti gli elementi. L'elenco non ordinato viene quindi scansionato per il valore minimo, che viene quindi inserito nell'elenco ordinato. Questo processo viene ripetuto finché tutti i valori non sono stati confrontati e ordinati.
In questo tutorial sull'algoritmo imparerai:
- Cos'è l'ordinamento di selezione?
- Come funziona l'ordinamento della selezione?
- Definizione del problema
- Soluzione (algoritmo)
- Rappresentazione visiva
- Selezione programma di ordinamento utilizzando Python 3
- Spiegazione del codice
- Complessità temporale dell'ordinamento di selezione
- Quando utilizzare l'ordinamento di selezione?
- Vantaggi dell'ordinamento di selezione
- Svantaggi dell'ordinamento di selezione
Come funziona l'ordinamento della selezione?
Il primo elemento nella partizione non ordinata viene confrontato con tutti i valori a destra per verificare se è il valore minimo. Se non è il valore minimo, la sua posizione viene scambiata con il valore minimo.
Esempio:
- Ad esempio, se l'indice del valore minimo è 3, il valore dell'elemento con indice 3 viene posto all'indice 0 mentre il valore che era all'indice 0 viene posto all'indice 3. Se il primo elemento nella partizione non ordinata è il valore minimo, quindi restituisce le sue posizioni.
- L'elemento che è stato determinato come valore minimo viene quindi spostato nella partizione sul lato sinistro, che è l'elenco ordinato.
- Il lato partizionato ora ha un elemento, mentre il lato non partizionato ha (n - 1) elementi dove n è il numero totale di elementi nell'elenco. Questo processo viene ripetuto più volte finché tutti gli elementi non sono stati confrontati e ordinati in base ai loro valori.
Definizione del problema
Un elenco di elementi in ordine casuale deve essere ordinato in ordine crescente. Considera il seguente elenco come esempio.
[21,6,9,33,3]
L'elenco precedente dovrebbe essere ordinato per produrre i seguenti risultati
[3,6,9,21,33]
Soluzione (algoritmo)
Passaggio 1) Ottieni il valore di n che è la dimensione totale dell'array
Passaggio 2) Partizionare l'elenco in sezioni ordinate e non ordinate. La sezione ordinata è inizialmente vuota mentre la sezione non ordinata contiene l'intero elenco
Passaggio 3) Scegli il valore minimo dalla sezione non partizionata e posizionalo nella sezione ordinata.
Passaggio 4) Ripetere il processo (n - 1) volte finché tutti gli elementi nell'elenco non sono stati ordinati.
Rappresentazione visiva
Dato un elenco di cinque elementi, le immagini seguenti illustrano come l'algoritmo di ordinamento della selezione esegue l'iterazione dei valori durante l'ordinamento.
L'immagine seguente mostra l'elenco non ordinato
Passo 1)
Il primo valore 21 viene confrontato con il resto dei valori per verificare se è il valore minimo.
3 è il valore minimo, quindi le posizioni 21 e 3 vengono scambiate. I valori con uno sfondo verde rappresentano la partizione ordinata dell'elenco.
Passo 2)
Il valore 6 che è il primo elemento nella partizione non ordinata viene confrontato con il resto dei valori per scoprire se esiste un valore inferiore
Il valore 6 è il valore minimo, quindi mantiene la sua posizione.
Passaggio 3)
Il primo elemento dell'elenco non ordinato con il valore 9 viene confrontato con il resto dei valori per verificare se è il valore minimo.
Il valore 9 è il valore minimo, quindi mantiene la sua posizione nella partizione ordinata.
Passaggio 4)
Il valore 33 viene confrontato con il resto dei valori.
Il valore 21 è inferiore a 33, quindi le posizioni vengono scambiate per produrre il nuovo elenco precedente.
Passaggio 5)
È rimasto solo un valore nell'elenco non partizionato. Pertanto, è già ordinato.
L'elenco finale è come quello mostrato nell'immagine sopra.
Selezione programma di ordinamento utilizzando Python 3
Il codice seguente mostra l'implementazione dell'ordinamento della selezione utilizzando Python 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))
Eseguire il codice precedente produce i seguenti risultati
[3, 6, 9, 21, 33]
Spiegazione del codice
La spiegazione del codice è la seguente
Ecco la spiegazione del codice:
- Definisce una funzione denominata selectionSort
- Ottiene il numero totale di elementi nell'elenco. Abbiamo bisogno di questo per determinare il numero di passaggi da eseguire quando si confrontano i valori.
- Anello esterno. Utilizza il ciclo per scorrere i valori dell'elenco. Il numero di iterazioni è (n - 1). Il valore di n è 5, quindi (5 - 1) ci dà 4. Ciò significa che le iterazioni esterne verranno eseguite 4 volte. In ogni iterazione, il valore della variabile i viene assegnato alla variabile minValueIndex
- Anello interno. Utilizza il ciclo per confrontare il valore più a sinistra con gli altri valori sul lato destro. Tuttavia, il valore di j non inizia con l'indice 0. Inizia con (i + 1). Ciò esclude i valori che sono già stati ordinati in modo che ci concentriamo sugli elementi che non sono stati ancora ordinati.
- Trova il valore minimo nell'elenco non ordinato e lo colloca nella posizione corretta
- Aggiorna il valore di minValueIndex quando la condizione di scambio è vera
- Confronta i valori dei numeri di indice minValueIndex e i per vedere se non sono uguali
- Il valore più a sinistra è memorizzato in una variabile temporale
- Il valore più basso dal lato destro prende la posizione prima posizione
- Il valore memorizzato nel valore temporale viene memorizzato nella posizione precedentemente mantenuta dal valore minimo
- Restituisce l'elenco ordinato come risultato della funzione
- Crea una lista el che ha numeri casuali
- Stampa l'elenco ordinato dopo aver chiamato la funzione Sort di selezione passando el come parametro.
Complessità temporale dell'ordinamento di selezione
La complessità dell'ordinamento viene utilizzata per esprimere il numero di tempi di esecuzione necessari per ordinare l'elenco. L'implementazione ha due cicli.
Il ciclo esterno che seleziona i valori uno per uno dall'elenco viene eseguito n volte dove n è il numero totale di valori nell'elenco.
Anche il ciclo interno, che confronta il valore del ciclo esterno con il resto dei valori, viene eseguito n volte dove n è il numero totale di elementi nell'elenco.
Pertanto, il numero di esecuzioni è (n * n), che può anche essere espresso come O (n 2 ).
L'ordinamento di selezione ha tre categorie di complessità e cioè;
- Nel peggiore dei casi : qui è dove l'elenco fornito è in ordine decrescente. L'algoritmo esegue il numero massimo di esecuzioni espresso come [Big-O] O (n 2 )
- Caso migliore : si verifica quando l'elenco fornito è già ordinato. L'algoritmo esegue il numero minimo di esecuzioni espresso come [Big-Omega] Ω (n 2 )
- Caso medio : si verifica quando l'elenco è in ordine casuale. La complessità media è espressa come [Big-theta] ⊝ (n 2 )
L'ordinamento di selezione ha una complessità spaziale di O (1) in quanto richiede una variabile temporale utilizzata per lo scambio di valori.
Quando utilizzare l'ordinamento di selezione?
L'ordinamento di selezione viene utilizzato al meglio quando si desidera:
- Devi ordinare un piccolo elenco di elementi in ordine crescente
- Quando il costo dello scambio di valori è insignificante
- Viene utilizzato anche quando è necessario assicurarsi che tutti i valori nell'elenco siano stati controllati.
Vantaggi dell'ordinamento di selezione
I seguenti sono i vantaggi dell'ordinamento di selezione
- Funziona molto bene su piccoli elenchi
- È un algoritmo sul posto. Non richiede molto spazio per lo smistamento. È richiesto solo uno spazio aggiuntivo per contenere la variabile temporale.
- Funziona bene sugli articoli che sono già stati ordinati.
Svantaggi dell'ordinamento di selezione
I seguenti sono gli svantaggi dell'ordinamento di selezione.
- Funziona male quando si lavora su elenchi enormi.
- Il numero di iterazioni effettuate durante l'ordinamento è n quadrato, dove n è il numero totale di elementi nell'elenco.
- Altri algoritmi, come Quicksort, hanno prestazioni migliori rispetto all'ordinamento di selezione.
Sommario:
- L'ordinamento di selezione è un algoritmo di confronto sul posto utilizzato per ordinare un elenco casuale in un elenco ordinato. Ha una complessità temporale di O (n 2 )
- L'elenco è diviso in due sezioni, ordinate e non ordinate. Il valore minimo viene prelevato dalla sezione non ordinata e inserito nella sezione ordinata.
- Questa operazione viene ripetuta fino a quando tutti gli elementi non sono stati ordinati.
- L'implementazione dello pseudocodice in Python 3 implica l'uso di due cicli for e istruzioni if per verificare se lo scambio è necessario
- La complessità temporale misura il numero di passaggi necessari per ordinare l'elenco.
- La complessità temporale nel caso peggiore si verifica quando l'elenco è in ordine decrescente. Ha una complessità temporale di [Big-O] O (n 2 )
- La complessità temporale nel migliore dei casi si verifica quando l'elenco è già in ordine crescente. Ha una complessità temporale di [Big-Omega] Ω (n 2 )
- La complessità temporale del caso medio si verifica quando l'elenco è in ordine casuale. Ha una complessità temporale di [Big-theta] ⊝ (n 2 )
- L'ordinamento di selezione viene utilizzato al meglio quando si dispone di un piccolo elenco di elementi da ordinare, il costo dello scambio dei valori non è importante e il controllo di tutti i valori è obbligatorio.
- L'ordinamento della selezione non funziona bene su elenchi enormi
- Altri algoritmi di ordinamento, come Quicksort, hanno prestazioni migliori rispetto all'ordinamento di selezione.