Un tour dei 5 migliori algoritmi di ordinamento con codice Python

Complessità degli algoritmi di ordinamento

L'ordinamento è un'abilità di cui ogni ingegnere e sviluppatore software necessita di alcune conoscenze. Non solo per passare interviste di codifica, ma come una comprensione generale della programmazione stessa. I diversi algoritmi di ordinamento sono una perfetta dimostrazione di come il design degli algoritmi può avere un effetto così forte sulla complessità, sulla velocità e sull'efficienza del programma.

Facciamo un giro tra i primi 6 algoritmi di ordinamento e vediamo come possiamo implementarli in Python!

Bubble Sort

L'ordinamento a bolle è quello di solito insegnato nelle lezioni introduttive di CS poiché dimostra chiaramente come funziona l'ordinamento pur essendo semplice e facile da capire. L'ordinamento a bolle scorre l'elenco e confronta le coppie di elementi adiacenti. Gli elementi vengono scambiati se sono nell'ordine sbagliato. Il passaggio attraverso la parte non ordinata dell'elenco viene ripetuto fino a quando l'elenco non viene ordinato. Poiché l'ordinamento Bubble passa ripetutamente attraverso la parte non ordinata dell'elenco, presenta una complessità nel caso peggiore di O (n²).

Ordinamento selezione

L'ordinamento di selezione è anche abbastanza semplice ma sovraperforma spesso l'ordinamento a bolle. Se stai scegliendo tra i due, è meglio semplicemente impostare correttamente l'ordinamento per selezione. Con l'ordinamento Selezione, dividiamo la nostra lista di input / matrice in due parti: la lista secondaria di voci già ordinate e la lista secondaria di voci rimanenti da ordinare che compongono il resto della lista. Prima troviamo l'elemento più piccolo nell'elenco secondario non ordinato e lo posizioniamo alla fine dell'elenco secondario ordinato. Pertanto, afferriamo continuamente il più piccolo elemento non ordinato e lo posizioniamo in ordine ordinato nella lista secondaria ordinata. Questo processo continua in modo iterativo finché l'elenco non è completamente ordinato.

Ordinamento inserzione

L'ordinamento per inserzione è sia più veloce che, probabilmente, più semplicistico sia dell'ordinamento a bolle che dell'ordinamento per selezione. Abbastanza divertente, è quante persone ordinano le loro carte quando giocano a un gioco di carte! Su ogni iterazione di loop, l'ordinamento di inserzione rimuove un elemento dall'array. Quindi trova la posizione in cui quell'elemento appartiene all'interno di un altro array ordinato e lo inserisce lì. Ripete questo processo fino a quando non rimangono elementi di input.

Unisci ordinamento

Unisci ordinamento è un esempio perfettamente elegante di un algoritmo Divide and Conquer. Usa semplicemente i 2 passaggi principali di un tale algoritmo:

(1) Dividi continuamente l'elenco non ordinato fino a quando non hai N elenchi secondari, in cui ciascun elenco secondario ha 1 elemento "non ordinato" e N è il numero di elementi dell'array originale.

(2) Unire ripetutamente, cioè conquistare le liste secondarie 2 alla volta per produrre nuove liste secondarie ordinate fino a quando tutti gli elementi non sono stati completamente uniti in un singolo array ordinato.

Ordinamento rapido

L'ordinamento rapido è anche un algoritmo di divisione e conquista come unire l'ordinamento. Sebbene sia un po 'più complicato, nella maggior parte delle implementazioni standard si comporta in modo significativamente più veloce rispetto all'unione dell'ordinamento e raramente raggiunge la complessità peggiore di O (n²). Ha 3 passaggi principali:

(1) Per prima cosa selezioniamo un elemento che chiameremo il perno dall'array.

(2) Sposta tutti gli elementi che sono più piccoli del perno a sinistra del perno; sposta tutti gli elementi che sono più grandi del perno a destra del perno. Questa è chiamata operazione di partizione.

(3) Applicare ricorsivamente i 2 passaggi precedenti separatamente a ciascuno dei sotto-array di elementi con valori sempre più piccoli rispetto all'ultimo perno.

Ti piace imparare?

Seguitemi su Twitter, dove posterò tutte le più recenti e importanti AI, tecnologia e scienza! Connettiti con me anche su LinkedIn!

Lettura consigliata

Vuoi saperne di più sulla programmazione in Python? Il libro Python Crash Course è la migliore risorsa per imparare a programmare in Python!

E solo un avvertimento, sostengo questo blog con link di affiliazione Amazon a grandi libri, perché condividere grandi libri aiuta tutti! Come socio Amazon guadagno da acquisti idonei.