|
DIPARTIMENTO DI
INFORMATICA Università di Torino | |
Lezione di Venerdi' 01/03/02 - ultimo aggiornamento: 05/03/02Mergesort e QuicksortCHE COSA E' STATO FATTO A LEZIONE
La metodologia "Divide and Conquer" applicata al problema dell'ordinamentoLe spiegazioni relative si trovano in [KRUSE].
Mergesort (su liste)
Prima versioneLa procedura mergesort:
/*
AI: *pl contiene una lista L
AF: *pl contiene la lista ottenuta ordinando L in ordine non decrescente
*/
void mergesort (node **pl)
{
node * firsthalf;
node * secondhalf;
if ((*pl != NULL) && (*pl->next != NULL))
{
split(pl,&firsthalf,&secondhalf);
mergesort(&firsthalf);
mergesort(&secondhalf);
merge(&firsthalf,&secondhalf,pl);
}
}
fa uso della procedura ITERATIVA split (che ha complessita' in tempo lineare
nella lunghezza della lista *pl, e complessita' in spazio costante):
/*
AI: *pl contiene una lista L
AF: *pl contiene la lista vuota,
*pfirsthalf contiene i nodi in posizione pari di L,
*psecondhalf contiene i nodi in posizione dispari di L
*/
void split (node **pl, node **pfirsthalf, node **psecondhalf)
{
<< SCRIVERE QUESTA FUNZIONE PER ESERCIZIO >>
}
e
fa uso della procedura ITERATIVA merge (che ha complessita' in tempo lineare
nella somma delle lunghezza delle liste *pfirsthalf e *psecondhalf,
e complessita' in spazio costante):
/*
AI: *pfirsthalf e *psecondhalf contengono due liste L1 e L2
ordinate (in ordine non decrescente)
AF: *pfirsthalf e *psecondhalf contengono la lista vuota
*pl contiene la "fusione ordinata" di L1 e L2
*/
void merge (node **pfirsthalf, node **psecondhalf, node **pl)
{
<< SCRIVERE QUESTA FUNZIONE PER ESERCIZIO >>
}
Seconda versioneLa procedura mergesort:
/*
AI: *pl contiene una lista L
AF: *pl contiene la lista ottenta ordinando L in ordine non decrescente
*/
void mergesort (node **pl)
{
msN(pl, length(*pl));
}
fa uso della procedura ITERATIVA length (che ha complessita' in tempo lineare
nella lunghezza della lista *pl, e complessita' in spazio costante):
/*
AI: *pl contiene una lista L
AF: restituisce il numero di nodi di L
*/
int length (node *l)
{
int r = 0;
while (l != NULL)
{
r++;
l = l->next;
}
return r;
}
e "incapsula" la procedura:
/*
AI: *pl contiene una lista L di lunghezza n
AF: *pl contiene la lista ottenta ordinando L in ordine non decrescente
*/
void msN (node **pl, int n)
{
node * firsthalf;
node * secondhalf;
if (n > 1)
{
splitN(pl,&firsthalf,&secondhalf,n);
msN(&firsthalf,(n+1)/2);
msN(&secondhalf,n/2);
merge(&firsthalf,&secondhalf,pl);
}
}
che
fa uso della procedura ITERATIVA splitN (che ha complessita' in tempo lineare
nel parametro n (la lunghezza della lista *pl),
e complessita' in spazio costante):
/*
AI: *pl contiene una lista L di lunghezza n
AF: *pl contiene la lista vuota,
*pfirsthalf contiene i primi (n+1)/2 nodi di L,
*psecondhalf contiene i restanti n/2 nodi di L
*/
void splitN (node **pl, node **pfirsthalf, node **psecondhalf, int n)
{
int m = (n+1)/2;
node *s = *pl;
*pl = NULL;
*pfirsthalf = s;
*psecondhalf = NULL;
if (m > 0)
{
for r (i=1; i < m; i++) s = s->next;
/* s punta all'm-esimo nodo di L */
*psecondhalf = s->next;
s->next = NULL;
}
}
e
fa uso della procedura ITERATIVA merge (descritta in precedenza).
Quicksort (su array)La procedura quicksort:
/*
AI: a[low..high] e' inizializzato
AF: a[low..high] e' stato ordinato in ordine non decrescente
*/
void quicksort(int a[], int low, int high)
{
int pivotpos;
if (low < high)
{
pivotpos = partition(a,low,high);
/* a[low..pivotpos-1] < a[pivotpos] <= a[pivotpos+1,high] */
quicksort(a,low,pivotpos-1);
quicksort(a,pivotpos+1,high);
}
}
fa uso della procedura ITERATIVA partition
(che ha complessita' in tempo lineare in
high-low, e complessita' in spazio costante):
/*
AI: low < high e a[low..high] e' inizializzato
AF: restituise un indice p tale che:
low <= p <= high e
gli elementi di a[low..high] sono stati permutati in modo che:
a[low..p-1] < a[p] <= a[p+1,high]
*/
int partition (int a[], int low, int high)
{
swap(low,(low+high)/2,a); /* scelta del pivot */
int pivot = a[low];
int lastsmall = low; /* la partizione sinistra dell'array e' vuota */
/*
IC: pivot = a[low]
AND
low <= lastsmall <= high
AND
low+1 <= i<= high+1
AND
a[low+1..lastsmall] < pivot <= a[lastsmall+1..i-1]
*/
for (int i = low+1; i <= high; i++)
if (a[i] < pivot)
{
lastsmall++;
swap(lastsmall,i); /* sposta l'elemento < pivot nella partizione
sinistra dell'array */
}
/*
pivot = a[low]
AND
low <= lastsmall <= high
AND
a[low+1..lastsmall] < pivot <= a[lastsmall+1..high]
*/
swap(low,lastsmall,a);
/*
low <= lastsmall <= high
AND
a[low..lastsmall-1] < a[lastsmall] <= a[lastsmall+1..high]
*/
return lastsmall;
}
che a sua volta
fa uso della procedura swap che, per migliorare le prestazioni del
programma, puo' essere eliminata):
/*
AI: j,k sono indici di a
AF: a e' stato modificato scambiando a[j] e a[k]
*/
void swap (int j, int k, int a[])
{
int temp = a[j];
a[k] = a[j];
a[j] = temp;
}
COSA SI DEVE LEGGERE
|
/*
AI: *pl contiene una lista L
AF: *pl contiene la lista vuota,
*pfirsthalf contiene i nodi in posizione pari di L,
*psecondhalf contiene i nodi in posizione dispari di L
*/
void split (node **pl, node **pfirsthalf, node **psecondhalf)
sviluppata in precedenza facendo uso della seguente asserzione iniziale:
AI: *pl contiene una lista L con almeno 2 elementi
/*
AI: *pfirsthalf e *psecondhalf contengono due liste L1 e L2
ordinate (in ordine non decrescente)
AF: *pfirsthalf e *psecondhalf contengono la lista vuota
*pl contiene la "fusione ordinata" di L1 e L2
*/
void merge (node **pfirsthalf, node **psecondhalf, node **pl)
sviluppata in precedenza facendo uso della seguente asserzione iniziale:
AI: *pfirsthalf e *psecondhalf contengono due liste L1 e L2
non vuote e
ordinate (in ordine non decrescente)
/* AI: a[low..high] e' inizializzato AF: a[low..high] e' stato ordinato in ordine non decrescente */ void mergesortArray(int a[], int low, int high);(SUGGERIMENTO: nella procedura merge fare uso di un array ausiliario di capacita' (half-first+1)/2).
/* AI: *pl contiene una lista L AF: *pl contiene la lista ottenta ordinando L in ordine non decrescente */ void quicksortList (node **pl);
| Last update: Mar 06, 2002 | |