Ordinamento della selezione: algoritmo spiegato con Python Esempio di codice

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(n²) 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]

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. 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 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 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(n²).

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(n²)
caso migliore – questo si verifica quando l'elenco fornito è già ordinato. L'algoritmo esegue il numero minimo di esecuzioni che è espresso come [Big-Omega] ?(n²)
Caso medio – questo accade quando l'elenco è in ordine casuale. La complessità media è espressa come [Big-theta] ?(n²)

L'ordinamento per selezione ha una complessità spaziale di O(1) poiché richiede una variabile temporale utilizzata per lo scambio di 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 scambio di valori è 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.

Sommario

Selection sort è un algoritmo di confronto in loco che viene utilizzato per ordinare un elenco casuale in un elenco ordinato. Ha una complessità temporale di O(n²)
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 cosa viene ripetuta finché tutti gli elementi non sono stati ordinati.
Implementazione dello pseudocodice in Python 3 prevede l'utilizzo di due cicli for e istruzioni if per verificare se è necessario lo scambio
La complessità temporale misura il numero di passaggi necessari per ordinare l'elenco.
La complessità temporale peggiore si verifica quando l'elenco è in ordine decrescente. Ha una complessità temporale di [Big-O] O(n²)
La complessità temporale migliore si verifica quando l'elenco è già in ordine crescente. Ha una complessità temporale di [Big-Omega] ?(n²)
La complessità temporale del caso medio si verifica quando l'elenco è in ordine casuale. Ha una complessità temporale di [Big-theta] ?(n²)
L'ordinamento per selezione viene utilizzato al meglio quando si dispone di un piccolo elenco di elementi da ordinare, il costo dello scambio di valori non ha importanza e il controllo di tutti i valori è obbligatorio.
L'ordinamento della selezione non funziona bene su elenchi di grandi dimensioni
Altri algoritmi di ordinamento, come Quicksort, hanno prestazioni migliori rispetto all'ordinamento per selezione.