Insertion Sort Python

Coding Creativo 06/08/2021

Studiamo l’algoritmo Insertion Sort in Python, un algoritmo di ordinamento molto semplice da implementare.

L’algoritmo funziona in maniera molto simile al modo in cui sistemiamo in mano le carte da gioco.

Infatti si presuppone che la prima carta sia ordinata, dopo si prende una carta non ordinata e si posiziona alla sua sinistra se è minore, alla sua destra se è maggiore. In questo modo le carte non ordinate verranno messe al loro posto.

In modo molto simile funziona l’algortimo di ordinamento Insertion Sort.

Supponiamo che la lista di partenza sia questa:

numbers = [3,6,1,9,2]

Si scorre la lista dalla posizione i che va da 1 fino ad n, quindi da numero 6 al numero 2.

Dunque se l’elemento della lista nella posizione i è maggiore del suo predecessore non si sposta, se invece è minore si sposta sulla sinistra finchè non si trova un precedessore più piccolo o si raggiunge la posizione più a sinistra dell’array.

Insertion Sort Python – code

Definiamo una funzione insertion_sort che prende come parametro la lista.

Creaimo un ciclo for che scorre gli elementi della lista da a 1 fino alla sua lunghezza, memorizziamo l’elemento da confrontare in una variabile temp e assegniamo a j l’elemento precedente dell’indice i.

Poi con un ciclo while continuiamo finchè l’elemento da confrontare è più piccolo dei predecessori o raggiunge la posizione più a sinistra (ovvero quella con indice 0). Di volta in volta scambiamo l’elemento e decrementiamo la variabile j.

Dopo il ciclo while, in ogni caso, assegniamo ad a[j+1] il valore di temp, anche se non ci sono stati scambi.

Ecco dunque il nostro codice dell’Insertion Sort in Python:


def insertion_sort(a):
    for i in range(1, len(a)):  
        temp = a[i] #primo elemento da confrontare
 
        j = i-1 #la prima volta è il primo elemento
        while j >= 0 and temp  a[j]:
                a[j+1] = a[j]
                j -= 1
        a[j+1] = temp
       
a = [3,6,1,9,2]
insertion_sort(a)
print(a)

Potremmo anche evitare l’utilizzo della variabile temporanea assegnando a j la variabile i. Ecco una possibile implementazione:



def insertion_sort(a):
    for i in range(1, len(a)):
        j = i
        while j > 0 and a[j - 1] > a[j]:
            a[j], a[j - 1] = a[j - 1], a[j]
            j -= 1
       
a = [3,6,1,9,2]
insertion_sort(a)
print(a)

Possiamo provare il nostro codice nell’editor sotto:

In questa lezione abbiamo sviluppato l’algortimo Insertion Sort in Python, nelle prossime studieremo altri arlgoritmi di ordinamento.

Alcuni link utili

Indice tutorial sul linguaggio Python

1 – Introduzione al linguaggio Python

2 – Le variabili

3 – Operatori aritmetici e di assegnazione

4 – Stringhe

5 – Casting

6 – Input e print

7 – Primi esercizi in Python

8 – Errori in Python

Continua la lettura su: https://www.codingcreativo.it/insertion-sort-python/ Autore del post: Coding Creativo Fonte: https://www.codingcreativo.it

Categorie: Coding Creativo, Vedi tutti i blog di Didattica

Tags: Python

Coding Creativo

Quicksort Python

Implementiamo l’algoritmo quicksort in Python, noto anche come l’algoritmo di ordinamento che è basato sull’approccio divide et impera!

Il suo funzionamento è basato sul pivot, ovvero un elemento che può essere selezionato in vari modi. Nel corso della presente guida studieremo i vari modi. Infatti, ad esempio, il pivot può essere il primo elemento, oppure l’ultimo o ancora l’elemento di mezzo ed infine può anche essere un elemento scelto a caso.

Il ragionamento che sta alla base di questo algoritmo è la partizione, ovvero la suddivisione di un array in sottoarray. Metteremo gli elementi più piccoli del pivot alla sua sinistra mentre gli elementi più grandi saranno posizionati alla sua destra.

Quicksort in Python – funzionamento

Lista di partenza:

number_list = [10,5,12,1,9,7]

I passaggi per ordinare una qualsiasi lista con il quicksort sono questi:

Divide – Dividendo la lista da ordinare scomponiamo il problema in sotto-problemi.Impera – Si risolve l’algoritmo e si applica la ricorsione.Combina – Si combinano gli output precedenti ottenuti dalle chiamate ricorsive.

Iniziamo con il primo passo, ovvero la partizione.

Scegliamo come pivot l’ultimo elemento: 7. Per estrarlo uso semplicemetne il metodo pop di Python, dunque avremo:

pivot = number_list.pop()

Dopo creiamo due liste vuote, low and high per contenere rispettivamente gi elemnti più piccoli e quelli più grandi del pivot.

low, high = [], []

Confrontiamo ciascun elemento con il pivot e lo inseriamo nella lista opportuna.

number_list = [10,5,12,1,9,7]
pivot = number_list.pop()
high, low = [], []

for number in number_list:
if number > pivot:
high.append(number)
else:
low.append(number)

print(number_list)
print(high)
print(low)

In questo modo la lista number_list non conterrà più l’ultimo elemento perchè è stato estratto e le due liste high e low sono popolate con gli elementi più grandi e più piccoli del pivot, rispettivamente.

L’output prodotto sarà questo:

number_list: [10, 5, 12, 1, 9] #manca l’elemento 7, ovvero il pivothigh: [10, 12, 9] #tutti gli elementi maggiori di 7low: [5, 1] #tutti gli elementi minori o uguali a 7

Come possiamo notare le due liste high e low non sono ordinate. Cosa possiamo fare?

Sicuramente possiamo applicare lo stesso metodo a queste due sotto-liste. Dunque richiamiamo la funzione in maniera ricorsica.

Ricordiamo di controllare la lunghezza della lista e fermarci quando non ha più elementi.

Scriviamo dunque tutto l’algoritmo che ci consente di risolvere l’ordinamento utilizzando il quicksort in Python.

def quick_sort(numbers):
length = len(numbers)
if length = 1:
return numbers

pivot = numbers.pop()
high, low = [], []
for number in numbers:
if number > pivot:
high.append(number)
else:
low.append(number)
return quick_sort(low) + [pivot] + quick_sort(high)
number_list = [10,5,12,1,9,7]
print(quick_sort(number_list))

Potete provare l’algoritmo nel compiler online sotto:

La soluzione più classica dell’algoritmo quicksort è questa:

def quicksort(numbers, p, r):
“””indichiamo con:
p – l’indice della sottolista di sinistra
r – l’indice della sottolista di destra
“””
if p r:
q = partition(numbers, p, r)
quicksort(numbers, p, q – 1)
quicksort(numbers, q + 1, r)

def partition(numbers, p, r):
pivot = numbers[r] #definiamo il pivot assegnando l’ultimo elemento
i = p – 1 #inizilizziamo l’indice dell’array di sinistra

for j in range(p, r):
if numbers[j] = pivot:
i += 1
numbers[i], numbers[j] = numbers[j], numbers[i] #scambio i valori
numbers[i + 1], numbers[r] = numbers[r], numbers[i + 1] #scambio i valori
return i + 1

number_list = [10,5,12,1,9,7]
quicksort(number_list,0,len(number_list)-1)
print(number_list)

Chiaramente ci possono essere tante altre soluzioni sull’algoritmo quicksort in Python, provate ad implementare la vostra e lasciatela nei commenti sotto.

Alcuni link utili

Indice tutorial sul linguaggio Python

1 – Introduzione al linguaggio Python

2 – Le variabili

3 – Operatori aritmetici e di assegnazione

4 – Stringhe

5 – Casting

6 – Input e print

7 – Primi esercizi in Python

8 – Errori in Python

9 – Script Python

10 – Scambio di variabili

11 – Modulo math

Coding Creativo 05/08/2021

Python sort

In questa lezione parleremo del metodo sort() di Python utile per ordinare velocemente una lista in ordine crescente o decrescente.

Realizziamo dunque alcuni esempi per capirne il funzionamento.

Ordinamento crescente/decrescente di una lista con Python sort

Prendiamo in input una lista di numeri qualsiasi ed applichiamo il metodo sort su di essa per effettuare l’ordinamento in senso crescente.

numbers = [1,7,9,3,4]
numbers.sort()
print(numbers)

Parametro reverse di Python sort

Ordiniamo adesso in ordine descrescente utilizzando il parametro opzionale reverse. Se reverse è False si ordina la lista in senso crescente, è infatti il valore di default, se invece reverse è True, si ordina la lista in senso descrescente.

Ecco in esempio:

numbers = [1,7,9,3,4]
numbers.sort(reverse=True)
print(numbers)

Parametro key di sort

Il parametro key consente di specificare un criterio di ordinamento in base ad una funzione.

Facciamo un esempio ordinando una lista in base alla lunghezza dei nomi. Definiamo una funzione che calcola la lunghezza dei nomi di un array.

Applichiamo l’ordinamento impostando la key con la funzione definita.

Ecco di seguito il semplice esempio dell’algoritmo di ordinamento Python sort():

names = [‘Paul’,’Robert’,’Elena’,’Tom’]

def len_names(array):
return len(array)

names.sort(key=len_names)

print(names)

Se volessimo ordinare in ordine inverso, basterà indicare anche il parametro reverse.

names = [‘Paul’,’Robert’,’Elena’,’Tom’]

def len_names(array):
return len(array)

names.sort(reverse = True, key=len_names)

print(names)

Esempio di ordinamento con Python sort

In questo esempio proviamo ad ordinare una lista di lettere maiuscole e minuscole.

names = [‘B’,’a’,’C’,’s’]
names.sort()

print(names)

In output avremo: [‘B’, ‘C’, ‘a’, ‘s’]

Il risultato ottenuto non è quello che ci aspettavamo! Perchè? Ovviamente perché ogni lettera dell’alfabeto corrsiponde ad un carattere della codifica ASCII e le lettere maiuscole hanno una codifica diversa rispetto alle minuscole.

Possiamo ottenere un ordinamento corretto ad esempio convertendo tutti i caratteri della lista in minuscolo.

names = [‘B’,’a’,’C’,’s’]
names_order = [name.lower() for name in names]
names_order.sort()

print(names_order)

Potremmo anche scrivere in questo modo:

names = [‘B’,’a’,’C’,’s’]

for i in range(len(names)):
names[i] = names[i].lower()

names.sort()

print(names)

Conclusione

In questa lezione abbiamo visto come ordinare velocemente una lista utilizzando Python sort, nelle prossime lezioni studieremo alcuni algoritmi di ordinamento a scopo didattico.

Some useful links

Python tutorial

Python Compiler

Install Python

Variables

Assignment operators

Strings

Casting

How to find the maximum of N numbers

Python

Bubble sort

Matplotlib Plot

Coding Creativo 31/05/2022

Insertion Sort Python – code

Alcuni link utili

Articoli Correlati