Sez. 2: Ordinamento La consultazione di banche dati è sempre più cruciale in tutte le applicazioni dell’Informatica


Download 445 b.
Sana10.01.2019
Hajmi445 b.


Sez. 2: Ordinamento

  • La consultazione di banche dati è sempre più cruciale in tutte le applicazioni dell’Informatica.

  • Se vogliamo consultare spesso un vettore t = di dati è conveniente tenere t ordinato.

  • Ciò motiva lo studio degli algoritmi di ordinamento.


Tempi di accesso ai dati a confronto (casi medi)



Tempi di accesso ai dati a confronto (cenni di spiegazione)

  • Sia t non ordinato. Per trovare un dato x in t dobbiamo passare gli elementi di t ad uno ad uno.

  • Questo richiede in media n/2 passi se x è in t, ed n passi se x non è in t (dobbiamo esaminare tutto t prima di essere sicuri che x non c’è).

  • Sia t ordinato. Possiamo cercare x nel punto medio tm di t. Se x = tm, siamo a posto; se x < tm, dobbiamo continuare la ricerca in ; altrimenti, in . Ripetendo questo procedimento, ad ogni passo la lunghezza del vettore in cui cercare si dimezza.

  • Nel caso peggiore occorrono log2(n) passi (occorrono log2(n) dimezzamenti per far scendere n ad 1).



Ordinamento: terminologia.

  • Chiave = la parte del dato d che serve per confrontare due dati nell’ordine.

    • Se d è la scheda di un’automobile, la chiave di d è la targa dell’auto (e l’ordine è quello ascii).
    • Se d è la scheda di una persona, la chiave di d è il nome della persona (e l’ordine è quello alfabetico).
    • Se d è la scheda di uno studente, la chiave di d è la matricola dello studente (e l’ordine è quello numerico).
  • Studieremo la complessità di in tempo, misurata in base a: il numero di confronti tra chiavi usato + il numero di spostamenti eseguiti sui dati.



Ordinamento: conclusioni

  • Abbiamo motivato lo studio degli algoritmi di ordinamento con ragioni di complessità.

  • Utilizzeremo ora di nuovo la complessità per confrontare vari algoritmi di ordinamento tra loro, e sceglierne il migliore.



Sez. 3: BubbleSort (ordinamento “a bolla”)

  • Il BubbleSort trasporta il massimo dei primi n elementi nella posizione n, poi il massimo tra i primi n-1 nella posizione n-1, e così via, finché il vettore è ordinato.

  • Il trasporto del massimo tra i primi i elementi nella posizione i avviene scorrendo il vettore un passo alla volta, e portandoci dietro l’elemento più grande tra quelli incontrati (che quindi risale di un passo alla volta, “come una bolla”, fino a raggiungere la posizione i).

  • Ciò si ottiene scambiando il primo elemento col secondo (a meno che il secondo sia maggiore), poi il secondo con il terzo (a meno che il terzo sia maggiore), e così via fino all’i-esimo.



Esempio di BubbleSort (su un vettore con chiavi numeriche, n=4)



Esempio di BubbleSort (continua)



Complessità del BubbleSort (in tempo)

  • Trasportare il massimo dei primi i elementi in posizione i richiede i-1 confronti (uno tra il primo ed il secondo, uno tra il secondo e il terzo, ... uno tra gli elementi i-1 ed i).

  • Il numero totale di confronti è (n-1) + (n-2) + ... = n(n-1)/2.

  • Ogni confronto può richiede o no uno scambio.

  • Il numero minimo, medio, massimo di scambi è quindi:

    • 0, n(n-1)/4, n(n-1)/2.
  • Confronti e scambi crescono rapidamente con n. Per n=mille occorrono 500 mila confronti e 250 mila scambi; per n=un milione occorrono 500 miliardi di confronti e 250 miliardi di scambi.



BubbleSort: conclusioni

  • L’analisi della complessità mostra che il BubbleSort non è adatto per banche dati molto grandi (n=un milione o più) oppure usate di continuo.

  • Tuttavia, il BubbleSort ha il vantaggio di essere molto semplice da realizzare.

  • Il BubbleSort si può quindi usare su piccole banche dati a cui accedo frequentemente, e che non modifico spesso.



Sez. 4: InsertSort (ordinamento “per inserzione”)

  • L’InsertSort comincia ordinando i primi due elementi.

  • Quindi inserisce il terzo elemento tra i primi due (ora ordinati) in modo da rispettare l’ordine.

  • Quindi inserisce il quarto tra i primi tre (ora ordinati) in modo da rispettare l’ordine.

  • E così via, fino ad inserire l’n-esimo elemento tra i primi n-1.



Esempio di InsertSort (su un vettore con chiavi numeriche, n=4)



Esempio di InsertSort (continua)



Complessità dell’InsertSort (in tempo)

  • Inserire un elemento x in una lista di i elementi già ordinati richiede di scorrere tali i elementi dal fondo verso l’inizio, fino a trovare l’elemento  x piú a destra. Questo richiede:

    • Confronti = 1, Spostamenti = 0 nel caso migliore (inserimento al fondo; es.: vettore già ordinato);
    • Confronti = i/2, Spostamenti = i/2 nel caso medio (inserimento a metà);
    • Confronti = i, Spostamenti = i nel caso pessimo (inserimento all’inizio; es.: vettore in ordine decresc.).
  • Totale InsertSort (somma dei precedenti per 1  i  n-1):

    • Confr. = n-1 (min), n(n-1)/4 (medio), n(n-1)/2 (max)
    • Spost. = 0 (min), n(n-1)/4 (medio), n(n-1)/2 (max)


InsertSort: conclusioni

  • L’InsertSort si rivela nettamente migliore del BubbleSort.

  • Infatti, in base allo studio di complessità, per ogni scambio richiesto dal BubbleSort, l’InsertSort richiede uno spostamento. Uno spostamento è 3 volte più veloce di uno scambio.

  • Tuttavia, anche per l’InsertSort, il tempo utilizzato cresce con il quadrato della dimensione del vettore da ordinare. Per n = 1,000,000 occorrono 250 miliardi di spostamenti.

  • Dunque anche l’InsertSort, benche sia da due a tre volte più veloce del BubbleSort, non è adatto per banche dati molto grandi oppure usate di continuo.




Do'stlaringiz bilan baham:


Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2017
ma'muriyatiga murojaat qiling