Ordinamento rapido in Python
-
Ordinamento veloce in Python usando il metodo
numpy.sort() -
Ordinamento veloce in Python usando il metodo
Series.sort_values()della libreria Pandas - Implementazione dell’ordinamento rapido in Python
Questo tutorial spiegherà come implementare e applicare l ‘algoritmo di ordinamento rapido in Python.
L’ordinamento rapido è un algoritmo divide et impera. L’ordinamento rapido seleziona un elemento come pivot dall’array e quindi partiziona l’array attorno al pivot selezionato in sottoarray inserendo elementi più piccoli del pivot in un array ed elementi maggiori del pivot in un altro array. Se l’array contiene elementi duplicati, gli elementi uguali al pivot possono essere inseriti nel terzo sottoarray o in uno dei due sottoarray a seconda dell’implementazione dell’algoritmo. L’array viene ordinato in base all’ordinamento rapido ordinando i sottoarray tramite chiamate ricorsive.
Poiché l’algoritmo di ordinamento rapido ordina gli elementi confrontandoli, appartiene all’algoritmo di ordinamento per confronto.
Ordinamento veloce in Python usando il metodo numpy.sort()
Il metodo numpy.sort(array, axis, kind) accetta un array come input e restituisce la copia ordinata dell’array di input come output. Il parametro array èl’array che vogliamo ordinare, axis è il lungo il quale vogliamo ordinare l’array e kind specifica l’algoritmo che il metodo userà per ordinare l’array, il suo valore predefinitoèveloce ordinare.
Il codice di esempio sotto mostra come usare il metodo numpy.sort() per ordinare l’array usando l’ordinamento veloce in Python.
import numpy as np
a = np.array([2, 3, 6, 5, 7, 8, 3, 1])
sorted_a = np.sort(a, kind="quick sort")
print(sorted_a)
Produzione:
[1 2 3 3 5 6 7 8]
Ordinamento veloce in Python usando il metodo Series.sort_values() della libreria Pandas
Il metodo Series.sort_values(ascending, inplace, kind) della libreria Pandas accetta una Series Pandas come input e restituisce le serie ordinate.
Il valore predefinito dell’argomento ascending è True, quindi il metodo ordina le serie in ordine crescente. Se è impostato come False, la Series verrà ordinata in ordine decrescente. Se l’argomento inplace è impostato come True, le modifiche verranno apportate nella serie originale; in caso contrario, verrà restituita una copia ordinata dell’input. L’argomento kind determina quale metodo algoritmo utilizzerà per ordinare le serie, e il metodo utilizza l’algoritmo di ordinamento rapido per impostazione predefinita.
Il codice di esempio seguente mostra come utilizzare Series.sortvalues() per ordinare le serie in Python utilizzando l’algoritmo di ordinamento rapido:
import pandas as pd
s = pd.Series([1, 2, 4, 2, 7, 5, 3, 2, 6, 8])
s.sort_values(inplace=True, kind="quick sort")
print(s)
Produzione:
0 1
1 2
3 2
7 2
6 3
2 4
5 5
8 6
4 7
9 8
dtype: int64
Implementazione dell’ordinamento rapido in Python
Il terzo metodo può essere quello di implementare l’algoritmo di ordinamento rapido da soli in Python.
La seguente implementazione del codice dell’ordinamento rapido divide l’array in 3 sottoarray, un sottoarray contiene elementi inferiori al pivot, uno contiene elementi maggiori dei pivot e il terzo sottoarray contiene elementi uguali al pivot.
In ogni chiamata del metodo, otterremo la posizione ordinata del pivot, poiché stiamo separando i valori minori e maggiori del pivot. E tramite la chiamata ricorsiva si otterrà l’array ordinato completo.
Il codice di esempio seguente mostra come implementare l’algoritmo di ordinamento rapido spiegato sopra in Python:
def sort(array):
left = []
equal = []
right = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
left.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
return (
sort(left) + equal + sort(greater)
) # recursive calling of the sort() function
else: # return the array, when it contains only 1 element
return array