Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 10.Merge sort


Merge-sort

Un algoritmo di sort classico ha in genere una complessità di calcolo pari a O(N2).

Vediamo un algoritmo che, fondato sul criterio del DIVIDE ET IMPERA, ha una complessità più bassa.

Il merge-sort è fondato sul principio ricorsivo di ridurre il problema di partenza di un fattore 2 e nessun processo ricorsivo attivato viene fatto più di una volta.

Merge-sort (segue)

Dato un array A di dimensioni N, che si vuole ordinare, lo si suddivide in due sub-array ciascuno di dimensioni  N/2. I due sub-array così ottenuti vengono a loro volta divisi a metà. Il processo termina quando ogni sub-array prodotto contiene un solo elemento.

Si consideri l’esempio nella slide seguente.

Merge-sort (segue)


Merge-sort (segue)

Si parte con la richiesta di ordinare gli elementi dell’array compresi tra 0 e N, si riduce poi questo intervallo attraverso due variabili Lo e Hi fino a quando nel subarray non resta che un elemento. Questo è ovviamente ordinato e quindi si attiva la catena pop.

Per dividere i Subarrays usiamo una variabile locale Mid.
Questi Subarrays saranno prima ordinati (sorted) o poi fusi (merged).

CASO BASE si ha quando i due subarrays sono ridotti ad una sola variabile cioè sono banalmente ordinati.

Quando si arriva al Caso Base allora si attiva il processo di Merge tra i due arrays adiacenti rimasti.

Se invece siamo in presenza di subarrays con più di un elemento questo implica che il subarray deve essere ordinato.

Merge-sort (segue)

Lo pseudo codice per l’algoritmo di sort è il seguente:

void SortIt(int Lo,Hi, int AnArray[]);

usa i valori degli indici in input (Lo,Hi) per dividere AnArray in due subarray (inferiore e superiore).

if gli indici del subarray inferiore implicano un array ordinabile

SortIt(usa come indici quelli del subarray inferiore ,AnArray)

if gli indici del subarray superiore implicano un array ordinabile

SortIt(usa come indici quelli del subarray superiore ,AnArray)

Inizialmete avremo: SortIt(0, N-1, AnArray).

Di seguito si mostra l’albero ricorsivo per un array di 8 elementi.

Merge-sort (segue)


Merge-sort (segue)

Mostra codice Mostra codice

Merge-sort (segue)

Allegato: Mostra codice

N.B. Il codice allegato prevede l'uso del file header InsertArray.h introdotto nella lezione 7 diap.12.


Merge-sort (segue)


Svantaggi del Merge-Sort

Necessita di un vettore di appoggio.

Effettua gli spostamenti anche se il vettore di partenza è già ordinato.

Complessità del Merge-sort

I livelli dell’albero di sort sono log N. Ad ogni livello dell’albero si fa un merge di  N  elementi, quindi in totale la complessità è data da N*log2 N

I livelli dell'albero di sort sono log N. Ad ogni livello dell'albero si fa un merge di N elementi, quindi in totale la complessità è data da N*log2 N


Esercizio

Data una matrice quadrata A di interi, percorrendo la quale da sinistra a destra e dall’alto in basso si trovano tutti valori crescenti. Utilizzando l’algoritmo di ricerca binaria verificare che un preassegnato k appartiene alla diagonale principale fornendone le coordinate.

Es. Verificare se 36 soddisfa la richiesta

Es. Verificare se 36 soddisfa la richiesta


Esercizio

Dato un Array del tipo

FIGLIO PADRE MADRE

… m ……… u……….. r
… a ………. g ………. m
… g ………. c ………. n
… c ………. b ………. p
… u ………. l ……….. g

Scrivere un programma che con due funzioni ricorsive dica:

  1. Dato X chi è il padre e la madre di X.
  2. Dati X determini chi è il nonno e la nonna di Y.

Esercizio

Allegato: Mostra codice

Esercizio

Scrivere un algoritmo ricorsivo per il calcolo della funzione booleana tale che assegnati due array di caratteri Sl e S2 restituisca TRUE se il secondo è contenuto tutto o in parte nel primo. FALSE altrimenti.

Esempio:

Se Sl=’Smacchiare’ e S2=’Macchia’ allora la funzione vale TRUE.

Se Sl=’Mentecatto’ e S2=’tatto’ allora la funzione vale FALSE.

Esercizio

Date due matrici A(n×n) e B(n×n) di interi scrivere una funzione ricorsiva che fornisca la somma di tutti i numeri contenuti in A sottratti a quelli contenuti in B tali che la differenza non sia mai negativa.

Esercizio

Fornire una funzione ricorsiva tale che assegnato un vettore ordinato di numeri interi dica quanti e quali dei numeri in essa contenuti sono numeri di Fibonacci.

Es.
L1=[1,3,7,11,13, 19, 21, 33, 34]
I numeri di Fibonacci presenti nella lista sono 6 (1, 3, 13, 21, 34).

Esercizio

Data una matrice di interi N×N scrivere una funzione ricorsiva che valga TRUE se la somma degli elementi di ogni riga è minore della riga precedente e la somma degli elementi di ogni colonna è maggiore della somma della colonna precedente, FALSE altrimenti.


Esercizio

Data una matrice di interi NxN scrivere una funzione ricorsiva che valga TRUE se la somma degli elementi di ogni riga è minore della riga precedente e la somma degli elementi di ogni colonna è maggiore della somma della colonna precedente, FALSE altrimenti.

Mostra codice

I materiali di supporto della lezione

eserAvi

InsertArray.h

InsertArrayCh.h

insfinale

mergesort

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion