selezione sort python
Funzioni e metodi Python
Michael Zippo
31.10.2021
Un ordinamento di selezione Python divide un elenco in due piccoli elenchi. Un elenco rappresenta gli elementi ordinati. L’altro elenco contiene gli elementi non ordinati. L’ordinamento della selezione trova i valori più piccoli o più alti in ogni iterazione e sposta quei valori nell’elenco ordinato.
L’ordinamento degli elenchi è un’operazione comune in una serie di programmi.
Considera questo esempio: un insegnante vuole saperne di più sui risultati ottenuti dai suoi studenti nel test più recente. Un insegnante potrebbe voler ordinare gli studenti‚Äô punteggi in ordine crescente e decrescente. Ciò consentirà loro di scoprire facilmente quali erano i punteggi dei test più alti e più bassi.
Inserisci, l’ordinamento della selezione. L’ordinamento per selezione è un algoritmo che puoi utilizzare per ordinare un elenco in ordine crescente o decrescente.
In questa guida, discuteremo come scrivere un programma di ordinamento per selezione in Python. Esamineremo un esempio in questa guida in modo che tu possa imparare i dettagli degli ordinamenti di selezione.
Che cos’è un ordinamento di selezione Python?
Un ordinamento di selezione Python trova ripetutamente l’elemento minimo in una lista e sposta quell’elemento in una particolare fine della lista. L’ordinamento continua finché l’array non viene ordinato in ordine. Puoi anche istruire un ordinamento di selezione per trovare l’elemento massimo. Entrambi gli approcci ordinano un elenco.
Gli ordinamenti per selezione presuppongono che il primo elemento in un elenco sia il valore più piccolo. L’ordinamento confronterà quindi quel valore con il secondo elemento. Se il secondo elemento è minore del valore minimo, il secondo elemento diventa il valore minimo.
Questo processo viene ripetuto fino a raggiungere l’ultimo elemento della lista. Una volta raggiunto questo elemento, il valore minimo viene posizionato all’inizio dell’elenco non ordinato.
L’81% dei partecipanti ha dichiarato di sentirsi più sicuro delle proprie prospettive di lavoro nel settore tecnologico dopo aver frequentato un bootcamp. Fatti abbinare a un bootcamp oggi.
Il laureato medio di un bootcamp ha trascorso meno di sei mesi nella transizione di carriera, dall’avvio di un bootcamp alla ricerca del primo lavoro.
Non c’è modo migliore per conoscere gli ordinamenti di selezione piuttosto che per eseguire un esempio. Esaminiamo e ordiniamo un elenco di voti degli studenti in ordine crescente. Considera questo elenco non ordinato:
Inizieremo chiamando il primo valore della nostra lista il minimo . Ogni iterazione dell’ordinamento di selezione troverà l’elemento più piccolo e lo sposterà nella sottomatrice ordinata.
L’ordinamento dell’elemento minimo è un’opzione. Un ordinamento di selezione funziona se ordini l’elemento massimo. Ma, noi‚Äô utilizzando nuovamente l’elemento minimo in questo esempio.
Successivamente, confronteremo il valore minimo con il secondo elemento. Se questo elemento è inferiore al minimo, il secondo elemento dovrebbe diventare il valore minimo.
Confronteremo 73 e 62. 73 è maggiore di 62, il che significa che il nostro nuovo valore minimo è 62. La nostra lista passerà quindi attraverso tutti gli altri numeri della nostra lista:
- è 61 maggiore di 6 2 (il nostro valore minimo)? No, quindi scambia i numeri. Il minimo diventa 61.
- 69 è maggiore di 61 (il nostro valore minimo)? Si, quindi non fare nulla. Soggiorni minimi a 61.
Il nostro elenco sembra lo stesso:
Quando raggiungi il fine dell’elenco, puoi spostare il minimo all’inizio dell’elenco:
61 (il nostro valore minimo) è stato spostato all’inizio dell’elenco e ogni altro valore è aumentato di uno. Ripeteremo questo processo finché tutti gli elementi non saranno ordinati.
Ogni iterazione del nostro elenco restituirà quanto segue:
- 73, 62, 61, 69
- 61, 73, 62, 69
- 61, 62, 73, 69
- 61, 62, 69, 73
Quando l’ordinamento di selezione ha verificato tutti gli elementi nell’elenco, l’ordinamento si fermerà.
Il sottoarray ordinato e il sottoarray non ordinato sono entrambi invisibili per noi. Il nostro algoritmo ordina un array per noi e tiene traccia della parte non ordinata dell’array.
Come eseguire un ordinamento di selezione in Python
Ora conosci la teoria: bene fatto! è il momento della grande sfida. Implementeremo l’algoritmo di ordinamento della selezione in Python. Scriviamo un programma che accetta un array Python e lo ordina in ordine crescente.
Definire una funzione di ordinamento
Inizieremo definendo una funzione Python che esegue il nostro ordinamento di selezione :
Abbiamo iniziato utilizzando il metodo Python len() per ottenere la lunghezza della nostra lista. quindi usalo per avviare un ciclo Python for che esegue un ciclo su ogni elemento della nostra lista.
Per ogni iterazione nel ciclo, impostiamo il valore di minimo come primo elemento del nostro elenco. Lo abbiamo fatto nella nostra procedura dettagliata in precedenza. Una volta che abbiamo’ Dopo aver impostato un valore minimo, inizia un altro ciclo for che attraversa ogni elemento della nostra lista.
Per ogni elemento della lista, il nostro algoritmo verifica se il valore minimo è maggiore di quell’oggetto. Se lo è, non succede nulla; altrimenti, il valore minimo diventa l’elemento che il programma sta leggendo.
Dopo aver eseguito il ciclo di ogni elemento nella nostra lista, il nostro algoritmo sposta il valore minimo all’inizio dell’elenco. Quindi, il nostro programma continuerà fino al termine del ciclo for superiore. Questo perché gli ordinamenti di selezione vengono eseguiti un numero di volte pari alla lunghezza di un elenco.
Chiama la funzione di ordinamento
Avrete notato che se eseguiamo il nostro programma, non succede nulla. Questo perché non abbiamo ancora detto al nostro codice quali valori usare. Aggiungi il seguente codice in fondo al tuo programma, al di fuori della funzione sortList:
"Il Karma di carriera è entrato nella mia vita quando ne avevo più bisogno e mi ha aiutato rapidamente ad abbinare un bootcamp. Due mesi dopo la laurea, ho trovato il lavoro dei miei sogni in linea con i miei valori e obiettivi nella vita!"
Venus, Software Engineer presso Rockbot
Quando eseguiamo il nostro programma , viene restituito quanto segue:
Il nostro elenco è stato ordinato. Datti una pacca sulla schiena; ce l’hai fatta!
Gli ordinamenti di selezione possono essere utilizzati per ordinare un elenco in ordine decrescente. Se desideri ordinare un elenco in questo modo, puoi modificare il parametro "if" istruzione nell’ordinamento di selezione come segue:
Abbiamo cambiato il segno di minore di in un segno di maggiore. Questo ordinerà il nostro elenco in ordine decrescente, perché il valore minimo sarà impostato sul valore più alto nell’elenco. Tecnicamente, il nostro valore minimo diventa un valore massimo.
Gli ordinamenti di selezione, come gli ordinamenti a bolle, sono migliori per gli elenchi più piccoli, perché l’algoritmo non è‚Äô t efficiente quanto altri, come un ordinamento per inserimento quando utilizzato in elenchi più grandi.
Un ordinamento per selezione è un ottimo ordinamento da imparare quando si inizia solo con gli algoritmi di ordinamento. Altri tipi possono essere difficili da padroneggiare, ma avere una chiara comprensione degli ordinamenti di selezione può aiutarti a capire i diversi tipi di elenchi.
L’ordinamento di selezione ha una complessità temporale di O( n2). Ciò significa che la complessità dell’algoritmo crescerà esponenzialmente a seconda di quanti elementi ci sono nell’elenco.
O(n2) è la complessità del caso peggiore, media e migliore per questo algoritmo. Se desideri saperne di più e sulle complessità dell’ordinamento, consulta la nostra guida alla Notazione Big O.
Selezione gli ordinamenti sono un metodo importante per ordinare i dati. Gli ordinamenti di selezione leggono ogni elemento in un elenco e, a ogni iterazione, spostano l’elemento più piccolo all’inizio dell’elenco. Questo accade finché ogni elemento dell’elenco non è stato letto.
Gli ordinamenti di selezione non sono ampiamente utilizzati al di fuori dell’insegnamento perché ci sono algoritmi più efficienti da usare. Detto questo, sono un buon trampolino di lancio per imparare altri tipi, come un ordinamento per inserimento o unione.
