Esercizi lezione 3 - Costo Algoritmi Sorting

[rimaout]

[notedo]

Ci sono due modi per approcciare questi esercizi, il primo è quello di capire quante volte vengono eseguite le istruzioni nei cicli, il secondo è quello di capire cosa succede complessivamente all'interno del programma:

Primo modo (più meccanico):

• InsertionSort: consideriamo il caso peggiore, ad esempio un array formato così [5,4,3,2,1], abbiamo che il primo ciclo for viene eseguito n volte quindi ha Θ(n), il secondo ciclo for dipende da i che dipende da j, infatti i = j-1. j all'ultimo ciclo arriva a n quind i = n-1, possiamo concludere quindi che il secondo ciclo verrà eseguito n-1 volte che è Θ(n). La complessità del nostro ciclo è quindi Θ(n)*Θ(n) = Θ(n^2)
• SelectionSort: il ragionamento è pressoché lo stesso dell'InsertionSort
• BubbleSort: il ragionamento è pressoché lo stesso dell'InsertionSort

Secondo modo (più ragionato):

• InsertionSort: analizziamo il caso peggiore. Quello che il nostro programma fa è controllare se un numero è maggiore di un altro, e in caso scambiare i due valori, utilizziamo j come chiave per spostarci nei vari valori dell'array
• SelectionSort: il ragionamento è pressoché lo stesso, capisco cosa faccio e mi muovo di conseguenza, ovviamente essendo tutti ordinamenti il meccanismo dietro è sempre quello degli scambi
• BubbleSort: il ragionamento è pressoché lo stesso dell'InsertionSort