Algoritmo di selezione per ordinamento con Python Code Esempio
Sara Chen
⚡ Riepilogo intelligente
L'ordinamento per selezione è un algoritmo di confronto in loco che ordina un elenco casuale in ordine crescente selezionando ripetutamente il valore non ordinato più piccolo e spostandolo nella sezione ordinata. Questa risorsa spiega un Python esempio e la sua complessità temporale.
Cos'è l'ordinamento della selezione?
ORDINAMENTO SELEZIONE è un algoritmo di ordinamento per confronto utilizzato per ordinare un elenco casuale di elementi in ordine crescente. Il confronto non richiede molto spazio aggiuntivo. Richiede solo uno spazio di memoria aggiuntivo per la variabile temporale.
Questo è noto come a posto ordinamento. L'ordinamento per selezione ha una complessità temporale di O(n2) 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 individuare il valore minimo, che viene quindi inserito nell'elenco ordinato. Questo processo viene ripetuto finché tutti i valori non sono stati confrontati e ordinati.
Come funziona l'ordinamento della selezione?
Il primo elemento nella partizione non ordinata viene confrontato con tutti i valori sul lato destro 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 posizionato nell'indice 0 mentre il valore che era nell'indice 0 viene posizionato nell'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ù e più volte finché tutti gli elementi non sono stati confrontati e ordinati in base ai loro valori.
Definizione del problema
Un elenco di elementi che sono in ordine casuale deve essere ordinato in ordine ascendente. Considerare il seguente elenco come esempio.
[21,6,9,33,3]
L'elenco sopra riportato dovrebbe essere ordinato per produrre i seguenti risultati
[3,6,9,21,33]
Soluzione (algoritmo)
Passo 1) Ottieni il valore di n che è la dimensione totale dell'array
Passo 2) Suddividere l'elenco in sezioni ordinate e non ordinate. La sezione ordinata è inizialmente vuota mentre la sezione non ordinata contiene l'intero elenco
Passo 3) Scegli il valore minimo dalla sezione non partizionata e inseriscilo nella sezione ordinata.
Passo 4) Ripeti il processo (n – 1) volte finché tutti gli elementi dell'elenco non saranno stati ordinati.
Rappresentazione visiva
Dato un elenco di cinque elementi, le immagini seguenti illustrano come l'algoritmo di ordinamento per selezione esegue un'iterazione sui 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 di 21 e 3 vengono scambiate. I valori con 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.
Passo 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.
Passo 4)
Il valore 33 viene confrontato con il resto dei valori.
Il valore 21 è inferiore a 33, quindi le posizioni vengono scambiate per produrre la nuova lista sopra.
Passo 5)
Abbiamo solo un valore rimasto nell'elenco non partizionato. Pertanto, è già ordinato.
L'elenco finale è come quello mostrato nell'immagine sopra.
Selezione Ordina programma utilizzando Python 3
Il codice seguente mostra l'implementazione dell'ordinamento per selezione utilizzando Python 3
def selectionSort( itemsList ): n = len( itemsList ) for i in range( n - 1 ): minValueIndex = i for j in range( i + 1, n ): if itemsList[j] < itemsList[minValueIndex] : minValueIndex = j if minValueIndex != i : temp = itemsList[i] itemsList[i] = itemsList[minValueIndex] itemsList[minValueIndex] = temp return itemsList el = [21,6,9,33,3] print(selectionSort(el))
Eseguendo il codice soprastante si ottengono i seguenti risultati
[3, 6, 9, 21, 33]
Code Spiegazione
La spiegazione del codice è la seguente
Qui è Code spiegazione:
- Definisce una funzione denominata SelectionSort
- Ottiene il numero totale di elementi nell'elenco. Ne abbiamo bisogno per determinare il numero di passaggi da effettuare 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 dall'indice 0. Inizia da (i + 1). Ciò esclude i valori che sono già stati ordinati in modo da concentrarci sugli elementi che non sono ancora stati ordinati.
- Trova il valore minimo nell'elenco non ordinato e lo posiziona nella posizione corretta
- Aggiorna il valore di minValueIndex quando lo scambioping la condizione è vera
- Confronta i valori dei numeri di indice minValueIndex e i per vedere se non sono uguali
- Il valore più a sinistra viene memorizzato in una variabile temporale
- Il valore più basso dal lato destro occupa la prima posizione
- Il valore memorizzato nel valore temporale viene memorizzato nella posizione precedentemente occupata 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 Ordina di selezione passando el come parametro.
Complessità temporale dell'ordinamento per selezione
La complessità di ordinamento è utilizzata per esprimere il numero di volte di esecuzione necessarie per ordinare l'elenco. L'implementazione ha due cicli.
Il ciclo esterno che preleva 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(n2).
L'ordinamento per selezione presenta tre categorie di complessità, ovvero:
- Caso peggiore – qui è dove l'elenco fornito è in ordine decrescente. L'algoritmo esegue il numero massimo di esecuzioni espresso come [Big-O] O(n2)
- caso migliore – questo si verifica quando l'elenco fornito è già ordinato. L'algoritmo esegue il numero minimo di esecuzioni che è espresso come [Big-Omega] Ω(n2)
- Caso medio – questo accade quando l'elenco è in ordine casuale. La complessità media è espressa come [Big-theta] Θ(n2)
L'ordinamento per selezione ha una complessità spaziale di O(1) poiché richiede una variabile temporale utilizzata per lo scambioping valori.
Quando utilizzare l'ordinamento per selezione?
L'ordinamento della selezione è utilizzato al meglio quando si desidera:
- Devi ordinare un piccolo elenco di elementi in ordine crescente
- Quando il costo dello scambioping il valore è insignificante
- Viene utilizzato anche quando è necessario assicurarsi che tutti i valori nell'elenco siano stati controllati.
Vantaggi dell'ordinamento della selezione
Di seguito sono riportati i vantaggi dell'ordinamento per selezione
- Funziona molto bene su elenchi piccoli
- È un algoritmo sul posto. Non richiede molto spazio per l'ordinamento. È necessario solo uno spazio aggiuntivo per contenere la variabile temporale.
- Funziona bene con gli elementi che sono già stati ordinati.
Svantaggi dell'ordinamento della selezione
Di seguito sono riportati gli svantaggi dell'ordinamento per selezione.
- Funziona male quando si lavora su elenchi di grandi dimensioni.
- Il numero di iterazioni effettuate durante l'ordinamento è n al quadrato, dove n è il numero totale di elementi nell'elenco.
- Altri algoritmi, come Quicksort, hanno prestazioni migliori rispetto all'ordinamento per selezione.
