• Non ci sono risultati.

Algoritmi di ordinamento•Basilare in molteplici applicazioni•Esempio importante di algoritmi diversiper risolvere lo stesso problema•Metodi di ordinamento

N/A
N/A
Protected

Academic year: 2021

Condividi "Algoritmi di ordinamento•Basilare in molteplici applicazioni•Esempio importante di algoritmi diversiper risolvere lo stesso problema•Metodi di ordinamento"

Copied!
3
0
0

Testo completo

(1)

1

Elementi di Informatica 1

Algoritmi di ordinamento

• Basilare in molteplici applicazioni

• Esempio importante di algoritmi diversi per risolvere lo stesso problema

• Metodi di ordinamento interni: i dati risiedono nella memoria centrale (in un vettore; campo chiave)

• Confronto basato sull'efficienza

Elementi di Informatica 2

Selectionsort

• Ordinamento per selezione

• Si sceglie il minimo del vettore e lo si scambia con la posizione corretta

• Complessità: O(n

2

)

• I due cicli vengono sempre eseguiti, indipendentemente dalla configurazione dei dati

Elementi di Informatica 3

Bubblesort

• Basato sulla considerazione che:

ei≤ ei+1

• Confronta coppie adiacenti e eventualmente le scambia

• Dopo una scansione completa l'elemento minore (o maggiore) è nella posizione corretta

• Termina quando sono terminati gli scambi (se è già ordinato serve solo un passo per la verifica)

• Complessità: O(n2)

Elementi di Informatica 4

Mergesort

• Basato sulla fusione (merge) di due vettori ordinati:

– la fusione ha complessità O(n)

• E' intrinsecamente ricorsivo

• Vettore iterativamente diviso in 2 parti:

– ordinamento e fusione

• Complessità O(n log

2

n)

Elementi di Informatica 5

Mergesort

• Indipendente dalla configurazione in ingresso

• La ricorsione incrementa la complessità della gestione:

– è consigliabile usare un programma non- ricorsivo

• Per ogni programma ricorsivo esiste un programma non-ricorsivo più efficiente

Elementi di Informatica 6

Quicksort

• Si sceglie un elemento pivot e si suddivide il vettore in due: uno con el. minori, l'altro con el. maggiori o uguali del pivot

• Si procede iterativamente fino a vettori di 1 solo elemento

• La suddivisione ha complessità O(n)

• La complessità della parte ricorsiva

dipende dalla scelta del pivot

(2)

2

Elementi di Informatica 7

Quicksort

• Scegliendo come pivot l'elemento min o max, la complessità diventa O(n

2

)

• Scegliendo come pivot l'elemento centrale, la complessità è O(n log

2

n)

• Il caso peggiore succede raramente

• E' più probabile il caso migliore

• E' usato per la semplicità e l'efficienza

Elementi di Informatica 8

Limite inferiore della complessità

• Si considerano algoritmi la cui operazione fondamentale è il confronto tra elementi

• Problema:

– è ricondotto alla ricerca di una specifica permutazione di n oggetti

– esistono n! permutazioni diverse – tutte le permutazioni sono candidate – ogni passo dell'algoritmo serve per eliminare

dei candidati

Elementi di Informatica 9

Esempio

• La ricerca è rappresentabile

graficamente con un albero binario:

– la radice rappresenta tutte le permutazioni – ogni confronto suddivide le permutazioni

• La profondità dell'albero determina il numero massimo di confronti nel caso peggiore

Elementi di Informatica 10

Esempio

• Ordinare {a1, a2, a3}

• Albero di risoluzione

– 3! = 6 permutazioni (6 foglie) – albero con profondità 3

Elementi di Informatica 11

• L'albero deve avere n! foglie

• In generale un albero binario con profondità i ha al più 2

i

foglie

• Quindi per avere n! foglie, l'albero deve avere profondità p = log(n!)

p = log(n!) ~ log(n/e)n =n log(n) - n log(e) = O(n log(n))

• Il limite inferiore alla complessità è O(n log(n))

Limite inferiore della complessità

Elementi di Informatica 12

Binsort

• Fin'ora gli algoritmi erano basati su operazioni di confronto

• Il binsort utilizza operazioni di indirizzamento con indici

• Sfrutta la conoscenza dell'intervallo di

variabilità delle chiavi

(3)

3

Elementi di Informatica 13

Binsort

• Si suppone che gli n elementi del vettore abbiano chiavi [1..n]

• Si scandisce un vettore e si spostano gli elementi in un altro

• Ha complessità O(n)

Elementi di Informatica 14

Binsort

• Caso di più chiavi uguali:

– utilizzo di una lista

– al termine le liste vengono concatenate

• Complessità:

– inserimento O(n) – concatenazione O(n) – totale O(n)

Elementi di Informatica 15

Binsort

• E' il più efficiente se:

– si utilizzano chiavi numeriche

– l'intervallo di variabilità delle chiavi è noto – è possibile effettuare indirizzamenti con

indici

Elementi di Informatica 16

Considerazioni

sulla scelta di un algoritmo

• Le caratteristiche di un algoritmo sono:

– semplice, per facilitarne la comprensione, programmazione, e correzione

– efficiente, cioè richiede una quantità limitata di risorse per l'esecuzione

• Le due caratteristiche si riferiscono a:

– costo umano – costo di esecuzione

Elementi di Informatica 17

Considerazioni

sulla scelta di un algoritmo

• Non esistono regole per la scelta ottima

• Generalmente però:

– si sceglie la prima regola quando si deve eseguire poche volte su insiemi ridotti di dati – si sceglie la seconda se il programma viene

eseguito un grande numero di volte su insiemi estesi di dati

Elementi di Informatica 18

Considerazioni

• Implementazione efficiente dell'algoritmo

– sono state considerate solo le complessità – sono state eliminate le costanti moltiplicative

• Per scegliere l'implementazione migliore è necessario considerare tutto

– ad esempio, gli algoritmi ricorsivi sono generalmente molto pesanti

Riferimenti

Documenti correlati

L’insertion Sort è uno algoritmo di ordinamento molto efficiente per ordinare un piccolo numero di elementi. L’idea di ordinamento è simile al modo che un giocatore di bridge

L’insertion Sort è uno algoritmo di ordinamento molto efficiente per ordinare un piccolo numero di elementi.. L’idea di ordinamento è simile al modo che un giocatore di bridge

• ogni cammino dalla radice a una foglia è la sequenza di confronti necessaria a riordinare una delle possibili permutazioni di lunghezza n, che è diversa per ogni permutazione, e

• Dato un array i cui elementi contengono tutti una chiave di ordinamento e data una relazione d’ordine sul dominio delle chiavi, determinare una permutazione degli oggetti

 Dato un problema, come possiamo sapere se esiste un algoritmo che lo

 un insieme di passi/istruzioni che definiscono una sequenza di operazioni mediante le quali si risolve un problema (o una classe di problemi).

BubbleSort (letteralmente: ordinamento a bolla) è un semplice algoritmo di ordinamento basato sullo scambio di elementi adiacenti. Ogni coppia di elementi adiacenti viene comparata

 Come si vede l’esempio considerato rappresenta il caso migliore perché il vettore originario è stato decomposto in due vettori che hanno entrambi dimensione uguale e pari a