Ricerca e ordinamento¶

Cercare un dato e mettere in ordine un elenco sono tra le operazioni più comuni in programmazione. Pensa alla rubrica del telefono: i nomi sono in ordine alfabetico proprio perché così si trovano in fretta. Python ha già strumenti pronti (in, sort), ma all'esame ti viene chiesto di scrivere tu l'algoritmo. In questo capitolo vediamo come funzionano, passo per passo.

In questo capitolo vettore e lista sono sinonimi: una sequenza di elementi a cui si accede con un indice che parte da 0.

Ricerca sequenziale¶

Il problema è semplice: dato un vettore e un valore x, vuoi sapere se x è presente e in quale posizione.

La ricerca sequenziale (o lineare) è l'algoritmo più intuitivo: scorri il vettore dall'inizio verso la fine e confronti ogni elemento con x. Ti fermi appena lo trovi, oppure quando il vettore finisce. È l'unico algoritmo possibile se il vettore non è ordinato.

Esempio: cerchiamo 23 nel vettore [15, 5, 1, 23, 3].

Sono serviti 4 confronti. Se cercassi 8, che non c'è, dovresti confrontare tutti i 5 elementi prima di poter dire "non trovato".

Nel codice si usa una variabile booleana trovato, un flag: parte da False e diventa True quando il valore viene trovato. Il ciclo while continua solo finché il valore non è stato trovato e ci sono ancora elementi da guardare.

a = [15, 5, 1, 23, 3]
x = int(input('Numero da cercare: '))

trovato = False
pos_trovato = -1      # -1 significa "nessuna posizione"
confronti = 0
i = 0
while not trovato and i < len(a):
    confronti = confronti + 1
    print(f'Passo {confronti}: confronto a[{i}] = {a[i]} con {x}')
    if a[i] == x:
        trovato = True
        pos_trovato = i
    i = i + 1

if trovato:
    print(f'Numero trovato in posizione {pos_trovato} con {confronti} confronti')
else:
    print(f'Numero non trovato dopo {confronti} confronti')

Prova con 23 (trovato al passo 4), con 15 (trovato subito) e con 8 (non trovato, 5 confronti).

Ricerca su una lista di record¶

Nelle prove d'esame i dati sono quasi sempre una lista di dizionari: ogni dizionario è un record con dei campi, ad esempio nome, cognome, eta. La ricerca è identica: cambia solo il confronto, che ora riguarda un campo del record. Conviene scriverla come funzione che restituisce due valori: se l'ha trovato e dove.

def ricerca_studente(lista, cognome):
    trovato = False
    pos_trovato = -1
    i = 0
    while not trovato and i < len(lista):
        if lista[i]["cognome"].lower() == cognome.lower():
            trovato = True
            pos_trovato = i
        i = i + 1
    return trovato, pos_trovato

studenti = [
    {"nome": "Alessandro", "cognome": "Manzoni", "eta": 14},
    {"nome": "Dante", "cognome": "Alighieri", "eta": 11},
    {"nome": "Giovanni", "cognome": "Boccaccio", "eta": 13},
]

cognome = input('Cognome da cercare: ')
trovato, pos = ricerca_studente(studenti, cognome)
if trovato:
    s = studenti[pos]
    print(f'Trovato in posizione {pos}: {s["cognome"]} {s["nome"]} - {s["eta"]} anni')
else:
    print('Nessuno studente con questo cognome')

Grazie a .lower() il confronto non distingue maiuscole e minuscole: alighieri e ALIGHIERI trovano lo stesso studente.

Ricerca binaria¶

Se il vettore è ordinato puoi fare molto meglio. Pensa a come cerchi una parola nel dizionario: apri a metà, guardi dove sei e scarti la metà che non può contenere la parola. Poi ripeti sulla metà rimasta.

La ricerca binaria (o dicotomica) fa esattamente questo. Usa tre indici:

• primo: inizio della zona in cui cercare;
• ultimo: fine della zona in cui cercare;
• medio: l'elemento centrale, (primo + ultimo) // 2 (divisione intera).

A ogni passo confronta x con a[medio]:

• se sono uguali, trovato;
• se x è più grande, il valore può essere solo a destra: primo = medio + 1;
• se x è più piccolo, il valore può essere solo a sinistra: ultimo = medio - 1.

Se primo supera ultimo, la zona è vuota: il valore non c'è.

Esempio: cerchiamo 10 nel vettore ordinato [1, 3, 5, 10, 15, 23, 31, 47, 47, 56, 64] (indici da 0 a 10).

Ora cerchiamo 8, che non è nel vettore.

Con la ricerca sequenziale per 8 avresti fatto 11 confronti; qui ne bastano 3.

a = [1, 3, 5, 10, 15, 23, 31, 47, 47, 56, 64]
x = int(input('Numero da cercare: '))

primo = 0
ultimo = len(a) - 1
trovato = False
medio = 0
passo = 0
while primo <= ultimo and not trovato:
    medio = (primo + ultimo) // 2      # l'operatore // esegue la divisione intera
    passo = passo + 1
    print(f'Passo {passo}: primo={primo}, ultimo={ultimo}, medio={medio}, a[medio]={a[medio]}')
    if a[medio] == x:
        trovato = True
    elif x > a[medio]:
        primo = medio + 1
    else:
        ultimo = medio - 1

if trovato:
    print(f'Numero trovato in posizione: {medio}')
else:
    print('Numero non trovato')

Prova con 10, con 8 e con 64 (l'ultimo elemento).

Ricerca binaria su una lista di record¶

Con i record la lista deve essere ordinata per il campo che cerchi. Qui gli studenti sono già in ordine alfabetico di cognome, quindi possiamo cercare per cognome. Le stringhe si confrontano con < e > in ordine alfabetico, come i numeri.

def ricerca_binaria_cognome(lista, cognome):
    primo = 0
    ultimo = len(lista) - 1
    trovato = False
    medio = -1
    while primo <= ultimo and not trovato:
        medio = (primo + ultimo) // 2
        cognome_medio = lista[medio]["cognome"].lower()
        if cognome_medio == cognome.lower():
            trovato = True
        elif cognome.lower() > cognome_medio:
            primo = medio + 1
        else:
            ultimo = medio - 1
    return trovato, medio

# Lista GIA' ordinata per cognome
studenti = [
    {"nome": "Dante", "cognome": "Alighieri", "eta": 11},
    {"nome": "Giovanni", "cognome": "Boccaccio", "eta": 13},
    {"nome": "Ugo", "cognome": "Foscolo", "eta": 12},
    {"nome": "Alessandro", "cognome": "Manzoni", "eta": 14},
    {"nome": "Francesco", "cognome": "Petrarca", "eta": 15},
]

cognome = input('Cognome da cercare: ')
trovato, pos = ricerca_binaria_cognome(studenti, cognome)
if trovato:
    print(f'Trovato in posizione {pos}: {studenti[pos]["nome"]} {studenti[pos]["cognome"]}')
else:
    print('Studente non trovato')

Quanto costa cercare¶

Per confrontare due algoritmi si conta quante operazioni fanno al crescere della dimensione n dei dati: è la complessità computazionale. Di solito si guarda il caso peggiore, che dà una garanzia sul tempo massimo.

• Ricerca sequenziale: nel caso peggiore (valore in fondo o assente) fa n confronti. Raddoppiando il vettore, raddoppia il tempo: complessità lineare.
• Ricerca binaria: a ogni passo dimezza la zona in cui cercare. Il numero di passi cresce come log₂ n: complessità logaritmica.

La differenza è enorme. Il prezzo da pagare è che il vettore deve essere ordinato: per questo servono gli algoritmi di ordinamento.

Il problema dell'ordinamento¶

Ordinare un vettore significa disporre i suoi elementi in modo che ognuno sia minore o uguale al successivo (ordine crescente). Gli elementi devono essere confrontabili con gli operatori relazionali: numeri tra loro, stringhe tra loro.

• Input: una sequenza di n elementi a₁, a₂, …, aₙ.
• Output: gli stessi elementi, riordinati in modo che a'₁ ≤ a'₂ ≤ … ≤ a'ₙ.

Tutti gli algoritmi che vediamo si basano su un'operazione: lo scambio di due elementi. Per scambiare a[i] e a[j] serve una variabile di appoggio, temp: senza, il primo valore andrebbe perso. Python permette anche una forma compatta, con l'assegnazione multipla.

a = [15, 5, 1]
print('Prima:', a)

# Scambio con la variabile di appoggio
temp = a[0]
a[0] = a[2]
a[2] = temp
print('Dopo il primo scambio:', a)

# Scambio con l'assegnazione multipla: fa la stessa cosa
a[0], a[1] = a[1], a[0]
print('Dopo il secondo scambio:', a)

Selection sort¶

Il selection sort (ordinamento per selezione) è molto intuitivo:

1. cerca l'elemento più piccolo del vettore;
2. scambialo con il primo elemento;
3. ripeti i passi 1 e 2 sul sotto-vettore che resta (dal secondo elemento in poi), finché il sotto-vettore non è vuoto.

A ogni passo la parte iniziale del vettore è già ordinata e non si tocca più.

Esempio con [15, 5, 1, 23, 3]. In grassetto la parte già ordinata.

Con 5 elementi bastano 4 passi: quando restano un solo elemento, è per forza al suo posto.

Nel codice, il ciclo esterno con indice i indica dove mettere il minimo. Il ciclo interno con indice j cerca il minimo nel resto del vettore. Lo scambio si fa una sola volta per passo, dopo il ciclo interno.

numeri = [64, 25, 12, 22, 11]
print(f'Lista originale: {numeri}')
n = len(numeri)
# Percorriamo tutta la lista, tranne l'ultimo elemento che sarà già al suo posto
for i in range(n - 1):
    # Assumiamo che il primo elemento non ordinato sia il minimo
    indice_minimo = i
    # Cerchiamo il vero minimo nella parte restante della lista
    for j in range(i + 1, n):
        if numeri[j] < numeri[indice_minimo]:
            indice_minimo = j
    # Scambiamo il minimo trovato con il primo elemento non ordinato
    temp = numeri[i]
    numeri[i] = numeri[indice_minimo]
    numeri[indice_minimo] = temp
    print(f'Passo {i}: minimo {numeri[i]}, lista = {numeri}')
print(f'Lista ordinata: {numeri}')

Selection sort su una lista di record¶

Nelle esercitazioni si scrive una funzione ricerca_massimo(lista, inizio) che restituisce la posizione del massimo a partire dall'indice inizio. L'ordinamento la richiama per ogni i. Cercando il massimo invece del minimo si ottiene un ordinamento decrescente.

Qui ordiniamo le vendite di un negozio per incasso (quantità × prezzo), dal più alto al più basso.

def calcola_incasso(vendita):
    return vendita["quantita"] * vendita["prezzo"]

def ricerca_massimo(lista, inizio):
    pos_massimo = inizio
    massimo = calcola_incasso(lista[inizio])
    for i in range(inizio + 1, len(lista)):
        incasso = calcola_incasso(lista[i])
        if incasso > massimo:
            massimo = incasso
            pos_massimo = i
    return pos_massimo

def ordina_per_incasso(lista):
    for i in range(len(lista) - 1):
        pos_max = ricerca_massimo(lista, i)
        if pos_max != i:
            temp = lista[i]
            lista[i] = lista[pos_max]
            lista[pos_max] = temp

vendite = [
    {"nome": "penne", "quantita": 10, "prezzo": 1.5},
    {"nome": "sapone", "quantita": 3, "prezzo": 2.0},
    {"nome": "pane", "quantita": 20, "prezzo": 1.2},
    {"nome": "quaderno", "quantita": 5, "prezzo": 3.0},
]

ordina_per_incasso(vendite)
for v in vendite:
    print(f'{v["nome"]:<10} incasso: {calcola_incasso(v):6.2f}')

Nota che si scambia l'intero dizionario, non solo il campo prezzo o quantita: altrimenti mescoleresti i dati di prodotti diversi.

Bubble sort¶

Il bubble sort (ordinamento a bolle) deve il nome a come si muovono gli elementi: i più grandi "affondano" verso la fine del vettore, i più piccoli "risalgono" verso l'inizio, come le bolle in un bicchiere.

L'algoritmo confronta gli elementi a due a due, vicini:

1. partendo dal primo elemento, confronta due elementi successivi a[j] e a[j+1];
2. se il primo è più grande del secondo, li scambia;
3. ripete su tutto il vettore. Se durante un giro (una passata) è avvenuto almeno uno scambio, fa un'altra passata; se non è avvenuto nessuno scambio, il vettore è ordinato e si ferma.

Ecco la prima passata su [15, 5, 1, 23, 3]:

Alla fine della prima passata il massimo (23) è all'ultimo posto. Alla passata successiva non serve più confrontarlo. In generale, dopo la passata numero i gli ultimi i elementi sono già al loro posto.

Nel codice il flag scambiato ricorda se nella passata c'è stato almeno uno scambio. Se no, l'istruzione break interrompe subito il ciclo esterno: è inutile continuare.

a = [64, 34, 25, 12, 22, 11]
n = len(a)
print(f'Vettore originale: {a}')
for i in range(n):
    scambiato = False
    # Gli ultimi i elementi sono già a posto, quindi accorciamo il range
    for j in range(0, n - i - 1):
        if a[j] > a[j + 1]:                  # confronta l'elemento con il successivo
            a[j], a[j + 1] = a[j + 1], a[j]  # scambio
            scambiato = True
    print(f'Passata {i + 1}: {a}')
    if not scambiato:
        print(f'Nessuno scambio: ordinamento completato alla passata {i + 1}')
        break
print(f'Vettore ordinato: {a}')

Prova a cambiare la prima riga con un vettore già ordinato, ad esempio a = [1, 2, 3, 4, 5]: basta una passata.

Bubble sort migliorato¶

Si può risparmiare ancora. Dopo una passata, tutto quello che sta dopo l'ultimo scambio è già ordinato. Quindi la passata successiva può fermarsi lì, invece di arrivare a n - i - 1.

1. La prima passata si fa su tutto il vettore.
2. Durante la passata si ricorda la posizione dell'ultimo scambio effettuato.
3. La passata successiva confronta gli elementi solo fino a quella posizione.
4. Ci si ferma quando in una passata non avviene nessuno scambio.

Nelle soluzioni delle esercitazioni si usano tre variabili:

• scambio_avvenuto: il flag, vale True se nella passata c'è stato almeno uno scambio;
• uscambio: la posizione dell'ultimo scambio nella passata in corso;
• ultimo_scambio: fin dove arrivare nella passata (all'inizio, len(lista) - 1).

a = [3, 1, 2, 4, 5, 6, 7]
print(f'Vettore originale: {a}')
scambio_avvenuto = True
ultimo_scambio = len(a) - 1
passata = 0
while scambio_avvenuto:
    scambio_avvenuto = False
    uscambio = 0
    passata = passata + 1
    for i in range(ultimo_scambio):
        if a[i] > a[i + 1]:
            temp = a[i]
            a[i] = a[i + 1]
            a[i + 1] = temp
            scambio_avvenuto = True
            uscambio = i + 1
    print(f'Passata {passata}: {ultimo_scambio} confronti, vettore = {a}, ultimo scambio in posizione {uscambio}')
    ultimo_scambio = uscambio
print(f'Vettore ordinato: {a}')

Qui la prima passata fa 6 confronti e l'ultimo scambio avviene in posizione 2. La seconda passata fa solo 2 confronti, non trova scambi e l'algoritmo termina. Il bubble sort della sezione precedente, nella seconda passata, avrebbe fatto 5 confronti.

Bubble sort su una lista di record¶

Questo è lo schema della funzione ordina_studenti dell'esercitazione Elenco studenti: ordina per cognome e, a parità di cognome, per nome. Si confrontano i campi, ma si scambiano i record interi.

def ordina_studenti(lista):
    # Bubble sort migliorato
    scambio_avvenuto = True
    ultimo_scambio = len(lista) - 1
    while scambio_avvenuto:
        scambio_avvenuto = False
        uscambio = 0
        for i in range(ultimo_scambio):
            cognome_i = lista[i]["cognome"].lower()
            cognome_succ = lista[i + 1]["cognome"].lower()
            nome_i = lista[i]["nome"].lower()
            nome_succ = lista[i + 1]["nome"].lower()
            # Fuori ordine se il cognome viene dopo, oppure se il cognome è uguale e il nome viene dopo
            if cognome_i > cognome_succ or (cognome_i == cognome_succ and nome_i > nome_succ):
                temp = lista[i]
                lista[i] = lista[i + 1]
                lista[i + 1] = temp
                scambio_avvenuto = True
                uscambio = i + 1
        ultimo_scambio = uscambio

studenti = [
    {"nome": "Alessandro", "cognome": "Manzoni", "eta": 14},
    {"nome": "Giovanni", "cognome": "Boccaccio", "eta": 13},
    {"nome": "Pietro", "cognome": "Alighieri", "eta": 12},
    {"nome": "Dante", "cognome": "Alighieri", "eta": 11},
]

ordina_studenti(studenti)
for s in studenti:
    print(f'{s["cognome"]} {s["nome"]} - {s["eta"]} anni')

I due Alighieri hanno lo stesso cognome: decide il nome, quindi Dante viene prima di Pietro.

Quanto costa ordinare¶

Per confrontare gli algoritmi di ordinamento si contano i confronti e gli scambi.

• Selection sort: al primo passo fa n − 1 confronti, al secondo n − 2, e così via. In totale circa n²/2 confronti, sempre, anche se il vettore è già ordinato. Gli scambi invece sono al massimo n − 1.
• Bubble sort: nel caso peggiore (vettore ordinato al contrario) fa anche lui circa n²/2 confronti e uno scambio per ogni confronto. Nel caso migliore (vettore già ordinato) fa una sola passata: n − 1 confronti e nessuno scambio.

Entrambi hanno complessità quadratica: se raddoppi n, i confronti diventano circa quattro volte tanti. Il programma seguente conta confronti e scambi dei tre algoritmi sugli stessi dati.

from random import randint

def selection_sort(a):
    confronti = 0
    scambi = 0
    n = len(a)
    for i in range(n - 1):
        indice_minimo = i
        for j in range(i + 1, n):
            confronti = confronti + 1
            if a[j] < a[indice_minimo]:
                indice_minimo = j
        if indice_minimo != i:
            a[i], a[indice_minimo] = a[indice_minimo], a[i]
            scambi = scambi + 1
    return confronti, scambi

def bubble_sort(a):
    confronti = 0
    scambi = 0
    n = len(a)
    for i in range(n):
        scambiato = False
        for j in range(n - i - 1):
            confronti = confronti + 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                scambi = scambi + 1
                scambiato = True
        if not scambiato:
            break
    return confronti, scambi

def bubble_sort_migliorato(a):
    confronti = 0
    scambi = 0
    scambio_avvenuto = True
    ultimo_scambio = len(a) - 1
    while scambio_avvenuto:
        scambio_avvenuto = False
        uscambio = 0
        for i in range(ultimo_scambio):
            confronti = confronti + 1
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                scambi = scambi + 1
                scambio_avvenuto = True
                uscambio = i + 1
        ultimo_scambio = uscambio
    return confronti, scambi

n = int(input('Quanti numeri vuoi ordinare? (ad esempio 100) '))
casuale = []
for k in range(n):
    casuale.append(randint(0, 100))
ordinata = casuale[:]
ordinata.sort()      # il metodo sort di Python, per preparare una lista ordinata
# Lista quasi ordinata: solo i primi due elementi sono invertiti
quasi = ordinata[:]
quasi[0], quasi[1] = quasi[1], quasi[0]

print(f'Riferimento n*n/2 = {n * n // 2}')
casi = [('casuale', casuale), ('già ordinata', ordinata), ('quasi ordinata', quasi)]
for nome, dati in casi:
    print(f'Lista {nome}: (confronti, scambi)')
    # dati[:] crea una copia: ogni algoritmo lavora sugli stessi valori di partenza
    print(f'  Selection sort:          {selection_sort(dati[:])}')
    print(f'  Bubble sort:             {bubble_sort(dati[:])}')
    print(f'  Bubble sort migliorato:  {bubble_sort_migliorato(dati[:])}')

Prova con 100 e poi con 200: sulla lista casuale i confronti diventano circa quattro volte tanti. Osserva anche gli altri due casi:

• sulla lista già ordinata il selection sort fa comunque tutti i confronti, i due bubble sort solo n − 1;
• sulla lista quasi ordinata il bubble sort migliorato fa circa n confronti, quello semplice circa 2n: la seconda passata del migliorato si ferma subito, perché l'ultimo scambio era all'inizio.

Ordinare senza spostare i dati: ordinamento sugli indici¶

Gli algoritmi visti finora sono in loco (in-place): spostano gli elementi dentro il vettore stesso. A volte però spostare i dati è scomodo o costoso: i record sono grandi, oppure vuoi conservare l'ordine originale.

In questi casi si ordina un vettore degli indici. All'inizio contiene 0, 1, 2, …, n−1. L'algoritmo confronta i dati a[indici[j]], ma scambia solo gli indici. Alla fine indici[0] è la posizione del più piccolo, indici[1] del secondo più piccolo, e così via. Il vettore dei dati non cambia.

Selection sort sugli indici con a = [15, 5, 1, 23, 3]:

a = [15, 5, 1, 23, 3]
n = len(a)
indici = []
for k in range(n):
    indici.append(k)

for i in range(n - 1):
    pos_minimo = i
    for j in range(i + 1, n):
        # Si confrontano i DATI, letti attraverso gli indici
        if a[indici[j]] < a[indici[pos_minimo]]:
            pos_minimo = j
    # Si scambiano solo gli INDICI
    temp = indici[i]
    indici[i] = indici[pos_minimo]
    indici[pos_minimo] = temp
    print(f'Passo {i}: indici = {indici}')

print('Vettore dei dati (non cambiato):', a)
print('Valori in ordine crescente:', end=' ')
for k in indici:
    print(a[k], end=' ')
print()

Indici su una lista di record¶

Lo stesso metodo permette di visualizzare gli studenti in ordine alfabetico lasciando la lista nell'ordine di inserimento.

studenti = [
    {"nome": "Alessandro", "cognome": "Manzoni", "eta": 14},
    {"nome": "Dante", "cognome": "Alighieri", "eta": 11},
    {"nome": "Giovanni", "cognome": "Boccaccio", "eta": 13},
]

indici = []
for k in range(len(studenti)):
    indici.append(k)

for i in range(len(indici) - 1):
    pos_minimo = i
    for j in range(i + 1, len(indici)):
        if studenti[indici[j]]["cognome"] < studenti[indici[pos_minimo]]["cognome"]:
            pos_minimo = j
    indici[i], indici[pos_minimo] = indici[pos_minimo], indici[i]

print('In ordine alfabetico:')
for k in indici:
    s = studenti[k]
    print(f'{s["cognome"]} {s["nome"]} - {s["eta"]} anni')
print('Primo studente nella lista originale:', studenti[0]["cognome"])

Riepilogo¶

Errori tipici¶

Esercizi¶

Esercizio 1 · Quanti confronti? Il vettore è [12, 4, 7, 30, 18, 2, 25]. Chiedi all'utente un numero da cercare e rispondi, con la ricerca sequenziale, se è presente e quanti confronti sono serviti. Ripeti la richiesta finché l'utente non inserisce un numero negativo.

# Scrivi qui la tua soluzione

def ricerca_sequenziale(a, x):
    trovato = False
    pos_trovato = -1
    confronti = 0
    i = 0
    while not trovato and i < len(a):
        confronti = confronti + 1
        if a[i] == x:
            trovato = True
            pos_trovato = i
        i = i + 1
    return trovato, pos_trovato, confronti

a = [12, 4, 7, 30, 18, 2, 25]
x = int(input('Numero da cercare (negativo per uscire): '))
while x >= 0:
    trovato, pos, confronti = ricerca_sequenziale(a, x)
    if trovato:
        print(f'{x} presente in posizione {pos} ({confronti} confronti)')
    else:
        print(f'{x} non presente ({confronti} confronti)')
    x = int(input('Numero da cercare (negativo per uscire): '))
print('Fine')

Esercizio 2 · Ordina e cerca. Chiedi all'utente un numero N compreso tra 20 e 100 (richiedilo finché non è valido). Genera N numeri interi pseudo-casuali tra 0 e 100 e mostrali. Ordinali in ordine crescente con il selection sort e mostrali di nuovo. Poi chiedi un numero da cercare e rispondi, con la ricerca binaria, se è presente. Ripeti finché l'utente non inserisce un numero negativo. Usa le funzioni.

# Scrivi qui la tua soluzione

from random import randint

def genera_vettore(n):
    vettore = []
    for k in range(n):
        vettore.append(randint(0, 100))
    return vettore

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        indice_minimo = i
        for j in range(i + 1, n):
            if a[j] < a[indice_minimo]:
                indice_minimo = j
        if indice_minimo != i:
            temp = a[i]
            a[i] = a[indice_minimo]
            a[indice_minimo] = temp

def ricerca_binaria(a, x):
    primo = 0
    ultimo = len(a) - 1
    trovato = False
    while primo <= ultimo and not trovato:
        medio = (primo + ultimo) // 2
        if a[medio] == x:
            trovato = True
        elif x > a[medio]:
            primo = medio + 1
        else:
            ultimo = medio - 1
    return trovato

def main():
    n = int(input('Quanti numeri (da 20 a 100)? '))
    while n < 20 or n > 100:
        n = int(input('Valore non valido. Quanti numeri (da 20 a 100)? '))
    vettore = genera_vettore(n)
    print('Vettore generato:', vettore)
    selection_sort(vettore)
    print('Vettore ordinato:', vettore)
    x = int(input('Numero da cercare (negativo per uscire): '))
    while x >= 0:
        if ricerca_binaria(vettore, x):
            print(f'{x} è presente')
        else:
            print(f'{x} non è presente')
        x = int(input('Numero da cercare (negativo per uscire): '))
    print('Fine')

main()

Esercizio 3 · Classe in ordine alfabetico. Chiedi all'utente i dati di alcuni studenti (nome, cognome, età), in ordine sparso. Dopo ogni studente chiedi se ce n'è un altro (s/n). Memorizza ogni studente in un dizionario dentro una lista. Ordina la lista per cognome con il bubble sort migliorato e mostra gli studenti, uno per riga, in questo formato:

Alighieri Dante – 11 anni
Boccaccio Giovanni – 13 anni
Manzoni Alessandro – 14 anni

# Scrivi qui la tua soluzione

def inserisci_studente():
    studente = {}
    studente["nome"] = input('Nome: ')
    studente["cognome"] = input('Cognome: ')
    studente["eta"] = int(input('Età: '))
    return studente

def ordina_studenti(lista):
    scambio_avvenuto = True
    ultimo_scambio = len(lista) - 1
    while scambio_avvenuto:
        scambio_avvenuto = False
        uscambio = 0
        for i in range(ultimo_scambio):
            if lista[i]["cognome"].lower() > lista[i + 1]["cognome"].lower():
                temp = lista[i]
                lista[i] = lista[i + 1]
                lista[i + 1] = temp
                scambio_avvenuto = True
                uscambio = i + 1
        ultimo_scambio = uscambio

def visualizza_studenti(lista):
    for s in lista:
        print(f'{s["cognome"]} {s["nome"]} – {s["eta"]} anni')

def main():
    classe = []
    altro = 's'
    while altro == 's':
        classe.append(inserisci_studente())
        altro = input('Vuoi inserire un altro studente? (s/n) ').lower()
    ordina_studenti(classe)
    visualizza_studenti(classe)

main()

Verifica¶