Esercitazione 11

Sperimentazione di algoritmi di ordinamento

1. Scrivere una funzione che crea e restituisce una lista di interi casuali in un certo intervallo, specificando come parametri la lunghezza della lista e l'intervallo di interi desiderato
2. Individuare il metodo della classe list che crea una copia di una lista
3. Implementare il quick sort
4. Implementare il merge sort
5. Implementare il bubble sort con flag per arresto in caso di raggiunto ordinamento
6. Sperimentare l'uso della funzione time.time_ns(), importando il modulo time, per misurare il tempo trascorso tra l'esecuzione di due istruzioni
7. Scrivere una funzione che, data una lista, restituisce il tempo impiegato per ordinarla usando il quick sort
8. Come sopra per merge sort, bubble sort e il metodo sort della classe list
9. Scrivere una funzione che, data una lista, restituisce il tempo impiegato per ordinarla usando il quick sort, merge sort, il bubble sort e il metodo sort della classe list. I metodi di ordinamento devono essere applicati a copie della stessa lista
10. Stampare una tabella con le seguenti colonne:
    lunghezza - T quick - T merge - T list.sort
    in cui la lunghezza è la sequenza 50, 100, 200, 400, 800, ..., raddoppiando ad ogni passo fino a un valore della lunghezza per il quale il tempo di esecuzione è ancora ragionevolmente breve
11. Modificare il quick sort e il merge sort, definendo come passo base il caso in cui la lunghezza della sequenza da ordinare è minore di k, ad esempio con k=5. Nel passo base ordinare utilizzando l'insertion sort (che deve essere scritto in modo da lavorare su una porzione di una sequenza, come il merge e il quick)
12. Sperimentare la modifica descritta al punto precedente su liste casuali lunghe, osservando come varia il tempo di esecuzione al variare della soglia k