Python quicksort
Funzioni e metodi Python
Michael Zippo
31.10.2021
Un QuickSort Python seleziona un elemento pivot e divide gli elementi di un array in due nuovi arrays. I numeri superiori al pivot entrano in un array; i numeri inferiori al pivot entrano in un altro. Ogni array viene ordinato e quindi tutti gli array vengono uniti in uno.
Ci sono molti algoritmi di ordinamento che puoi usare per ordinare un elenco nella programmazione. Esistono Python ordinamenti di inserimento, ordinamento delle bolle e altro ancora. QuickSort è uno dei tipi più comuni di ordinamento.
In questa guida, parleremo di cosa sono i QuickSort e di come funzionano. Esamineremo un esempio di Python QuickSort in modo che tu possa imparare come implementarne uno.
Senza ulteriori indugi, iniziamo!
Che cos’è un Python QuickSort?
Un algoritmo Python QuickSort divide un array in sottoarray. Questo algoritmo chiama ricorsivamente questi sottoarray per ordinare ogni elemento nell’elenco. I contenuti di un sottoarray sono determinati da un elemento pivot che non viene spostato in un nuovo sottoarray.
L’algoritmo QuickSort divide et impera. Ciò significa che l’attività di ordinamento di un elenco è suddivisa in diverse attività secondarie. Alla fine dell’ordinamento, i risultati di queste sottoattività si uniscono per restituire un elenco ordinato.
In un QuickSort, la sottoattività imposta un pivot per ogni sottoelenco e ordina gli elementi in base al loro valore relativo a il pivot.
Quando dovrei usare un QuickSort Python?
Un QuickSort è utile quando la complessità del tempo è importante. Questo perché QuickSort utilizza meno spazio di memoria rispetto ad altri algoritmi, il che dà loro un aumento dell’efficienza.
L’81% dei partecipanti ha dichiarato di sentirsi più sicuro delle proprie prospettive di lavoro nel settore tecnologico dopo aver partecipato a 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.
Dovresti usare solo QuickSort se hai familiarità con la ricorsione di Python. Questo perché l’algoritmo QuickSort dipende da funzioni ricorsive.
Un QuickSort è più efficiente di un merge sort su array più piccoli. Tuttavia, su set di dati più grandi, un ordinamento per inserimento o un unione può essere più veloce.
Come funziona un QuickSort?
Un QuickSort seleziona un elemento da utilizzare come pivot. Questo può essere qualsiasi elemento in un elenco. Per questo tutorial , sceglieremo l’ultimo elemento in un elenco (3).
Un QuickSort confronta il valore di pivot con ogni numero quando eseguiamo il ciclo degli elementi nell’elenco. Se un elemento è maggiore del numero di pivot, spostiamo il numero dopo il pivot; altrimenti, spostiamo il numero prima del pivot:
Il valore 3 è stato spostato in basso nell’elenco. Tutti gli elementi inferiori a 3 m inclinato alla sua sinistra; tutti i valori maggiori di tre sono stati spostati alla sua destra.
Il nostro array Python è diviso in due metà: elementi maggiori del pivot e elementi meno di un pivot.
Una volta avviato questo processo, inizia un nuovo pivot su ciascuna delle due metà. Questo pivot inizia separatamente e utilizza lo stesso algoritmo di cui sopra. Innanzitutto, imposteremo un valore pivot che è uguale all’ultimo valore in ogni elenco:
Successivamente, sposteremo tutti i valori maggiori di un pivot a destra del pivot. Spostiamo tutti i valori in meno rispetto al pivot a sinistra.
Questo processo continua finché non ordiniamo la nostra lista:
| Prima volta | 1 | 2 |
| 4 | 8 | 5 |
| Seconda volta |
| 1 |
|
| 8 | 5 |
|
|
|
|
| 5 | 87t?/ |
| Terzo Tempo |
|
|
|
|
| 8 |
Il nostro array finale ha questo aspetto:
Esempio Python QuickSort
Il QuickSort necessita di due funzioni: una funzione pivot e una funzione QuickSort.
Cominciamo con la funzione di partizione. Questo partirà, o preparerà, l’array in base al valore dell’elemento pivot.
La nostra funzione di partizione:
- Seleziona l’elemento pivot
- Sposta tutti gli elementi maggiori del pivot a destra del pivot
- Sposta tutti gli elementi inferiori al pivot a sinistra del pivot
Programma QuickSort Python
Scriviamo un programma che implementi questo algoritmo:
Per prima cosa, selezioniamo un elemento pivot. Questo è uguale al numero più alto nella nostra lista.
Successivamente, eseguiamo il ciclo di tutti gli elementi nell’elenco utilizzando un Python for loop. Se un numero è minore di o uguale al pivot, viene spostato a sinistra del pivot, altrimenti va a destra del pivot.
La nostra funzione Python restituisce il nuovo valore alto. Il nuovo valore alto è uguale all’elemento + 1.
Dopo, dobbiamo eseguire il nostro algoritmo. Possiamo farlo scrivendo una funzione separata:
"Il Karma di carriera è entrato nella mia vita quando ne avevo più bisogno e mi ha aiutato rapidamente ad abbinarmi a 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
Questa funzione verifica se il valore di "basso" è inferiore al valore di "alto". Se lo è, il nostro ordinamento può continuare. Altrimenti, il nostro ordinamento si interrompe. Se il nostro ordinamento si interrompe, significa che abbiamo ordinato l’elenco.
Successivamente, la nostra funzione chiama il metodo prepare(), che identifica un puntatore per il pivot e sposta gli elementi nella posizione corretta.
La nostra funzione chiama quindi due volte il metodo quick_sort(). La prima volta, eseguiamo QuickSort sugli elementi a sinistra del pivot. La seconda volta, eseguiamo QuickSort sugli elementi al a destra del pivot. Quindi, la nostra funzione è ricorsiva perché chiama se stessa.
Questo continua finché ogni elemento nell’elenco non viene ordinato.
Scrivere un metodo principale
Scriviamo un programma principale che definisca un elenco per cosi rt:
Per prima cosa, specifichiamo un elenco di valori da ordinare. Usiamo il metodo Python len() per calcolare la lunghezza del nostro elenco di valori. Successivamente, chiamiamo il metodo quick_sort().
Passiamo "valori" come numeri che vogliamo ordinare. Quindi passiamo 0 come numero basso. La lunghezza di "valori" meno 1 è il valore alto che specifichiamo. Il valore alto è la lunghezza dei valori meno 1 perché il primo elemento in un elenco ha il numero di indice 0.
Il nostro codice restituisce un elenco ordinato! Ce l’abbiamo fatta. Datti una pacca sulla spalla. QuickSort non è facile da capire o implementare.
In media, questo algoritmo funzionerà a O(n* log n). Questo accade quando l’elemento pivot non è l’elemento più grande o più piccolo e quando l’elemento pivot non è vicino all’elemento centrale.
Il QuickSort ha il caso peggiore com plexity di O(n2). Ciò si verifica quando l’elemento selezionato come pivot è l’elemento più grande o più piccolo. In questo caso, l’elemento pivot sarà sempre alla fine di un array ordinato. Questo creerà un numero di sottoarray non necessari.
La complessità del caso migliore per questo algoritmo è O(n* log n). Questo accade quando l’elemento pivot è uguale all’elemento centrale o vicino all’elemento centrale.
Python QuickSort usa la ricorsione per suddividere un elenco in elenchi più piccoli che vengono poi ordinati. Ogni elenco è ordinato attorno a un elemento pivot. Gli elementi maggiori del pivot vengono spostati alla sua destra; gli elementi più piccoli vengono spostati a sinistra del perno.
Per indicazioni sulle migliori risorse di apprendimento di Python, corsi online e libri, leggi il nostro completo Guida all’apprendimento di Python.
