Ordinamento e ricerca in Python

Se ti è stato dato un pezzo di carta con una lista di 1.000 nomi, e ti è stato chiesto di trovare un nome, ma questa lista non era in alcun ordine (ad esempio in ordine alfabetico), sarebbe molto frustrante, non è vero? Mettere in ordine la lista, anche se richiede molto tempo, rende molto più facile la ricerca del nome. Quindi, avere le cose in ordine è un desiderio naturale che noi esseri umani abbiamo, e la ricerca di questa lista richiederebbe chiaramente meno sforzi rispetto alla ricerca di una lista non ordinata.

Passiamo al mondo dei computer, in cui gli elenchi di cui si può richiedere la ricerca sono enormi e in cui le prestazioni potrebbero risentirne anche con i computer veloci. In questo caso, avendo un adatto ordinamento e ricerca l'algoritmo sarebbe una soluzione a tale problema. Mentre ordinamento si tratta di mettere un elenco di valori in ordine, ricerca è il processo per trovare la posizione di un valore all'interno di una lista.

Per chiarire quanto sia critico questo problema, lascia che ti mostri cosa Donald Knuth, un informatico americano, matematico e professore emerito alla Stanford University menzionato nel The Art of Computer Programming, vol.3, Sorting and Searching, pagina 3:

I produttori di computer degli anni '60 stimavano che oltre il 25% del tempo di esecuzione dei loro computer veniva speso per l'ordinamento, quando tutti i loro clienti venivano presi in considerazione. In effetti, c'erano molte installazioni in cui il compito di smistamento era responsabile di oltre la metà del tempo di elaborazione. Da queste statistiche, possiamo concludere che (i) ci sono molte importanti applicazioni di ordinamento, o (ii) molte persone ordinano quando non dovrebbero, o (iii) sono stati in uso algoritmi di ordinamento inefficienti.

In questo tutorial, descriverò in particolare il Selezione Ordina algoritmo (ordinamento) e il Ricerca lineare algoritmo (ricerca).

Algoritmo di selezione

Il Selezione Ordina l'algoritmo è basato sulla selezione successiva di valori minimi o massimi. Supponiamo di avere una lista che vogliamo ordinare in ordine ascendente (dai valori più piccoli a quelli più grandi). L'elemento più piccolo sarà all'inizio dell'elenco e l'elemento più grande sarà alla fine dell'elenco. 

Diciamo che l'elenco originale ha il seguente aspetto:

| 7 | 5 | 3,5 | 4 | 3.1 |

La prima cosa che facciamo è trovare il minimo valore nella lista, che è nel nostro caso 3.1. 

Dopo aver trovato il valore minimo, scambiare quel valore minimo con il primo elemento nell'elenco. Cioè, scambia 3.1 con 7. L'elenco sarà ora come segue:

| 3.1 | 5 | 3,5 | 4 | 7 |

Ora che siamo certi che il primo elemento si trova nella posizione corretta nell'elenco, ripetiamo il passaggio precedente (trovando il valore minimo) a partire dal secondo elemento nella lista. Possiamo scoprire che il valore minimo nella lista (a partire dal secondo elemento) è 3.5. Ora scambiamo così 3.5 con 5. L'elenco ora diventa come segue:

| 3.1 | 3,5 | 5 | 4 | 7 |

A questo punto, siamo certi che il primo elemento e il secondo elemento si trovano nelle loro posizioni corrette.

Ora controlliamo il valore minimo nel resto dell'elenco, a partire dal terzo elemento 5. Il valore minimo nel resto dell'elenco è 4, e ora lo scambiamo con 5. L'elenco diventa così il seguente:

| 3.1 | 3,5 | 4 | 5 | 7 |

Quindi ora siamo certi che il primo tre gli elementi sono nelle posizioni corrette e il processo continua in questo modo. 

Vediamo come l'algoritmo Selection Sort è implementato in Python (basato su Isai Damier):

def selectionSort (aList): per i in range (len (aList)): least = i per k nel range (i + 1, len (aList)): if aList [k] < aList[least]: least = k swap(aList, least, i) def swap(A, x, y): temp = A[x] A[x] = A[y] A[y] = temp

Proviamo l'algoritmo aggiungendo le seguenti dichiarazioni alla fine dello script sopra:

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5] selectionSort (my_list) stampa my_list

In questo caso, dovresti ottenere il seguente risultato:

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]

Algoritmo di ricerca lineare

Il Ricerca lineare al'algoritmo è un semplice algoritmo, in cui ogni elemento dell'elenco (a partire dal primo elemento) viene esaminato fino a quando viene trovato l'elemento richiesto oppure viene raggiunta la fine dell'elenco. 

L'algoritmo di ricerca lineare è implementato in Python come segue (basato su Python School):

def linearSearch (item, my_list): found = False position = 0 while position < len(my_list) and not found: if my_list[position] == item: found = True position = position + 1 return found

Proviamo il codice. Inserisci la seguente dichiarazione alla fine dello script Python sopra:

bag = ['libro', 'matita', 'penna', 'taccuino', 'temperino', 'gomma'] item = input ('Quale oggetto vuoi controllare nel sacchetto?') itemFound = linearSearch (articolo, borsa) se itemFound: stampa 'Sì, l'articolo è nel sacchetto' altro: stampa 'Oops, il tuo articolo sembra non essere nella borsa'

Quando entri nel ingresso, assicurati che sia tra virgolette singole o doppie (es. 'matita'). Se inserisci 'matita', per esempio, dovresti ottenere il seguente risultato:

Sì, l'oggetto è nella borsa

Considerando che, se si entra 'righello' come input, otterrai il seguente risultato:

Oops, il tuo articolo sembra non essere nella borsa

Come possiamo vedere, Python si dimostra di nuovo un linguaggio di programmazione che semplifica la programmazione di concetti algoritmici come abbiamo fatto qui, affrontando ordinamento e ricerca algoritmi.

È importante notare che esistono altri tipi di algoritmi di ordinamento e ricerca. Se vuoi approfondire questi algoritmi usando Python, puoi fare riferimento a questa pagina.