Algoritmi e Strutture Dati

O(n log n). L'algoritmo di ordinamento con heap sort

L'intero algoritmo di ordinamento che usa una coda prioritaria realizzata mediante heap viene eseguito in un tempo O(n log n). L'algoritmo heap sort ordina una sequenza S di n elementi (occupa spazio O(n)) in un tempo O(n log n), nell'ipotesi che due elementi di S possano essere confrontati in un tempo O(1).

Il tempo d'esecuzione O(n log n) di heap sort è significativamente migliore del tempo d'esecuzione degli algoritmi di ordinamento per selezione e per inserimento. Si ipotizza che il numero di chiavi, n, sia un numero intero tale che n = 2^h - 1, cioè assumiamo che lo heap sia un albero binario completo con tutti i livelli pieni, in modo che la sua altezza sia h = log(n+1) - 1.

Immaginandola in modo non ricorsivo, la costruzione di uno heap in modalità bottom-up consiste delle seguenti h + 1 = log(n + 1) fasi:

1. Nella prima fase costruiamo (n+1)/2 heap elementari, ciascuno dei quali memorizza una sola voce.
2. Nella seconda fase...

componiamo ^{(n + 1)}/4 heap, ciascuno dei quali memorizza tre voci, unendo coppie di heap elementari e aggiungendo a ciascuna coppia una nuova voce, che viene posta inizialmente nella radice e può essere, poi, scambiata con la voce memorizzata in uno dei suoi figli, per ripristinare la proprietà di ordinamento dello heap. Nella terza fase, componiamo ^{(n + 1)}/8 heap, ciascuno dei quali memorizza 7 voci, unendo coppie di heap aventi 3 voci ciascuno (costruiti nella fase precedente) e aggiungendo a ciascuna coppia una nuova voce, che viene posta inizialmente nella radice, ma può darsi che debba scendere verso il basso per ripristinare la proprietà di ordinamento, come determinato dalla procedura di down-heap. Nella generica, i-esima fase, con i, componiamo heap, ciascuno dei quali memorizza voci, unendo coppie di heap aventi voci ciascuno (costruiti nella fase precedente) e aggiungendo a ciascuna coppia una nuova voce che viene posta inizialmente nella radice, ma può darsi che debba scendere verso il basso per ripristinare la proprietà di ordinamento, come determinato dalla procedura di down-heap.

può darsi che debba scendere verso il basso per ripristinare la proprietà di ordinamento, come determinato dalla procedura di down-heap.h +1. Nell'ultima fase, componiamo lo heap conclusivo, che memorizza le n voci, unendo due heap aventi (n -1)/2 voci ciascuno (costruiti nella fase precedente) e aggiungendo una nuova voce, che viene posta inizialmente nella radice, ma può darsi che debba scendere verso il basso per ripristinare la proprietà di ordinamento, come determinato dalla procedura di down-heap.

La costruzione bottom-up di uno heap avente n entità richiede un tempo 0(n), nell'ipotesi che due chiavi possano essere confrontate tra loro in un tempo 0(1).

Merge Sort

lunedì 7 marzo 2022 13:00

Algoritmo teorico ricorsivo basato sulle seguenti fasi:

1. Dividi: Se la dimensione dei dati da elaborare è minore di una determinata soglia (diciamo, uno o due

1. Dividi: Se S è vuota o ha un solo elemento, restituisci immediatamente S, perché è una sequenza già ordinata. Altrimenti (S ha almeno due elementi), elimina tutti gli elementi da S e memorizzali in due sequenze, S1 e S2, ciascuna delle quali conterrà "circa" metà degli elementi di S: nello specifico, S1 contiene i primi elementi di S e S2 contiene i rimanenti elementi.
2. Conquista: Ordina ricorsivamente S1 e S2.
3. Combina: Memorizza nuovamente gli elementi in S fondendo le sequenze ordinate S1 e S2 in una sequenza ordinata.

E sono il numero di elementi di e, dato che le operazioni eseguite all'interno di ciascuna iterazione del ciclo while richiede un tempo O(1) e dato che durante ciascuna iterazione del ciclo, un elemento viene copiato in S, prelevandolo da o, non venendo più preso in esame dopo, il numero di iterazioni del ciclo è tempo d'esecuzione dell'algoritmo merge.

Possiamo visualizzare l'esecuzione dell'algoritmo merge-sort tramite un albero binario T, chiamato albero merge-sort:

• Ogni nodo v di T rappresenta una delle invocazioni ricorsive dell'algoritmo merge-sort e a v viene associata la sequenza S elaborata, appunto, dall'invocazione rappresentata da v.
• I figli del nodo v sono associati alle invocazioni ricorsive che elaborano le sotto-sequenze e di S.
• I nodi esterni di T sono, invece, associati ai singoli elementi di S, corrispondenti alle esecuzioni dell'algoritmo che non fanno uso di ulteriori invocazioni.

ricorsiveAlgoritmi e Strutture Dati Pagina 13• Ricorsione associata a un nodo v dell’albero merge-sort T: la fase di divisione viene eseguita in un tempo proporzionale alla dimensione della sequenza associata a v, creando copie delle due metà dellasequenza. La fase di merge richiede un tempo proporzionale alla dimensione della sequenza generata dalla fusione stessa. Se indichiamo con i la profondità del nodo v, il tempo speso nel nodo v è perché la dimensione della sequenza elaborata dall’invocazione ricorsiva associata al nodo v è proprio uguale a• T ha esattamente nodi di profondità i il tempo totale speso in tutti i nodi di T aventi profondità i è = O(n)• L’altezza di T è , quindi, dal momento che il tempo speso in ciascuno dei livelli di T è 0(n) e il numero di tali livelli è il costo complessivo dell'algoritmo èAlgoritmi e Strutture Dati Pagina 14Quick

Sortgiovedì 10 marzo 2022 11:00

L'idea di base è quella di applicare la tecnica dividi-e-conquista: si divide S in sotto-sequenze, si esegue una ricorsione per ordinare ciascuna sotto-sequenza e, poi, si combinano le sotto-sequenze ordinate mediante semplice concatenazione.

L'algoritmo quick-sort (ordinamento veloce) è costituito dalle tre fasi seguenti:

1. Dividi: Se S è vuota o ha un solo elemento, restituisci immediatamente S, perché è una sequenza già ordinata. Altrimenti (S ha almeno due elementi), seleziona un elemento x in S, che sarà chiamato pivot. Spesso la scelta del pivot cade sull'ultimo elemento di S. Elimina da S tutti i suoi elementi e memorizzali in una di queste tre sequenze:

   • L, che memorizza gli elementi di S che sono minori (less than, da cui la lettera L) di x
   • E, che memorizza gli elementi di S che sono uguali (equal) a x
   • G, che memorizza gli elementi di S che sono maggiori (greater than) di x

nodo v, definita come la dimensione della sequenza ricevuta come parametro dall'invocazione di quick-sort associata al nodo n + (n - 1) + … + 2 + 1•

Nel caso peggiore l'altezza di un albero quick-sort è n - 1 tempo d'esecuzione

Il caso migliore di quick-sort applicato a una sequenza di elementi distinti si verifica quando le sotto-sequenze L e G hanno approssimativamente la stessa dimensione: in quel caso l'albero ha altezza O(log n) il tempo d'esecuzione di quick-sort è 0(n log n)

Si ha una "good call" di funzione se L e G hanno dimensione minore di 3/4 di S

Si ha una "bad call" di funzione se L o G ha dimensione maggiore di 3/4 di S

Una chiamata di funzione è buona con probabilità di 1/2 dato che 1/2 dei possibili pivot causa una "good call"

Algoritmi e Strutture Dati Pagina 15

Dato che l'obiettivo della fase di partizionamento dell'algoritmo quick-sort è quello di dividere la

sequenza S in modo sufficientemente bilanciato, introduciamo casualità nell'algoritmo e scegliamo come pivot un elemento a caso della sequenza: invece di scegliere come pivot il primo o l'ultimo elemento di S, scegliamo un elemento di S a caso, senza modificare nessun altro aspetto dell'algoritmo. Questa variante di quick-sort è chiamata randomize quick-sort (cioè "quick-sort reso casuale" o probabilistico).

Il tempo d'esecuzione atteso dell'algoritmo quick-sort probabilistico applicato a una sequenza di n elementi è O(n log n). Questo calcolo del tempo atteso deriva dalla media eseguita su tutte le possibili scelte casuali fatte dall'algoritmo ed è indipendente da qualunque ipotesi sulla distribuzione dei dati nella sequenza da ordinare che viene fornita all'algoritmo.

Per un nodo con profondità i ci si aspetta che:

• i/2 chiamate siano buone
• La dimensione della sequenza di input per la

chiamata corrente sia• Per un nodo di profondità la dimensione di input sia 1

L'altezza attesa del quick-sort tree è O(logn)

Il costo dell'algoritmo per i nodi alla stessa altezza è O(n)

Il costo del quick-sort è O(nlogn)

Un algoritmo opera sul posto (in-place) se usa soltanto una piccola quantità di memoria aggiuntiva rispetto a quella necessaria per memorizzare i dati da elaborare e i dati da presentare in uscita.

Bisogna usare la sequenza ricevuta inizialmente per memorizzare le sotto-sequenze usate in tutte le invocazioni ricorsive.

L’algoritmo modifica la sequenza ricevuta usando scambi tra elementi e non crea sotto-sequenze in modo esplicito: una sotto-sequenza è rappresentata implicitamente da un intervallo di posizioni, specificato dall’indice più a sinistra, a, ed all’indice più a destra, b. La fase di divisione viene eseguita scandendo l’array

simultaneamente nei due sensi, usando le variabili locali left, che procede da sinistra a destra, e right, che procede a ritroso, scambiando tra loro le coppie di elementi che sono.