Sorting: MERGESORTSorting: MERGESORT

Vogliamo ordinare lista (a1,…,an).

1. Dividi lista in 2 sottoliste aventi (quasi) la stessa

dimensione: (a1,a3,a5,…) e (a2,a4,…), (SPLIT)

2. Ordina le due liste separatamente (MERGESORT)

3. Fondi le due liste ottenute (ordinate) in una unica lista ordinata (MERGE)

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

Algoritmo dipende dalla rappresentazione delle liste

Usiamo LISTE A PUNTATORI:

ogni elemento della lista è una struttura typedef struct CELL *LISTstruct CELL{ int element /* elemento della lista*/ LIST next /* puntatore alla successiva

struttura (elemento)*/

}

(a1,a2,…,an) a1 a2 … an

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

-Trova il minimo tra il primo elemento di L1 e di L2,

rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

- LIST merge (LIST list1, LIST list2){ if (list1==NULL) return list2 else if (list2==NULL) return list1 else if (list1->element <= list2 -> element)

/* entrambe le liste non vuote ed il primo elemento di list1 è minore del primo di list2*/

{ list1->next=merge(list1->next, list2); return list1; } else /*entrambe le liste non vuote ed il primo

elemento di list2 è minore del primo di list1*/

{ list2->next=merge(list1, list2->next); return list2; } }

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

-Trova il minimo tra il primo elemento di L1 e di L2,

rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

- LIST merge (LIST list1, LIST list2){ if (list1==NULL) return list2 else if (list2==NULL) return list1 else if (list1->element <= list2->element)

/* entrambe le liste non vuote ed il primo elemento di list1 è minore del primo di list2*/

{ list1->next=merge(list1->next, list2); return list1; } else /*entrambe le liste non vuote ed il primo

elemento di list2 è minore del primo di list1*/

{ list2->next=merge(list1, list2->next); return list2; } }

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

-Trova il minimo tra il primo elemento di L1 e di L2,

rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

- LIST merge (LIST list1, LIST list2){ if (list1==NULL) return list2 else if (list2==NULL) return list1 else /* entrambe le liste non vuote*/ if (list1->element <= list2->element)

/* entrambe le liste non vuote ed il primo elemento di list1 è minore del primo di list2*/

{ list1->next=merge(list1->next, list2); return list1; } else /*entrambe le liste non vuote ed il primo

elemento di list2 è minore del primo di list1*/

{ list2->next=merge(list1, list2->next); return list2; } }

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

LIST merge (LIST list1, LIST list2) {if (list1==NULL) return list2else if (list2==NULL) return list1 else if ( list1->element <= list2->element ) {/* entrambe le liste non vuote ed il primo

elemento di list1 è minore del primo di list2*/ list1->next=merge(list1->next, list2); return list1;} else …} list1 a1 a2 … an

list2 b1 b2 … bn

a2 … an list1 a1 merge

b1 … bn

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7

list2 3 5 6 9

list1=merge(list1, list2) merge (2-4-7, 3-5-6-9)

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7

list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7

list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

= merge(, ) merge(4-7, 5-6-9)

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7

list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

= merge(, ) merge(4-7, 5-6-9)

= merge(, ) merge(7, 5-6-9)

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7

list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

= merge(, ) merge(4-7, 5-6-9)

= merge(, ) merge(7, 5-6-9)

= merge(, ) merge(7, 6-9)

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7

list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

= merge(, ) merge(4-7, 5-6-9)

= merge(, ) merge(7, 5-6-9)

= merge(, ) merge(7, 6-9)

= merge(, ) merge(7, 9)

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7

list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

= merge(, ) merge(4-7, 5-6-9)

= merge(, ) merge(7, 5-6-9)

= merge(, ) merge(7, 6-9)

= merge(, ) merge(7, 9)

= merge(NULL, )= merge( , 9) 9

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7 list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

= merge(, ) merge(4-7, 5-6-9)

= merge(, ) merge(7, 5-6-9)

= merge(, ) merge(7, 6-9)

= merge(, ) = merge(7, 9) 7

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7 list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

= merge(, ) merge(4-7, 5-6-9)

= merge(, ) merge(7, 5-6-9)

= merge(, )= merge(7, 6-9) 6

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7 list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

= merge(, ) merge(4-7, 5-6-9)

= merge(, ) = merge(7, 5-6-9) 5

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7 list2 3 5 6 9

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2) merge(4-7,3-5-6-9)

= merge(, ) = merge(4-7, 5-6-9) 4

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7 list2 3 5 6 9

list1=merge(list1, list2) merge (2-4-7, 3-5-6-9)

merge(list2)=list2 merge(4-7,3-5-6-9) list2 3

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

list1 2 4 7 list2 3 5 6 9

list1=merge(list1, list2) merge (2-4-7, 3-5-6-9) list1 2

SPLIT (di L in due liste ordinate LSPLIT (di L in due liste ordinate L11,L,L22))

LIST Split (LIST list){ List pSecondcell;if (list==NULL) return NULLelse if (list->Next==NULL) return NULL else {/* list contiene almeno 2 elementi*/ pScondcell=list->next; list->next = pSecondcell->next; pSecondcell->next=split(pSecondcell->next); return pSecondcell; }}

L=(a1,a2, a3, a4, …, an) L1 =(a1, a3, …) , L2 =(a2, a4, …)

SPLIT (di L in due liste ordinate L1,L2)SPLIT (di L in due liste ordinate L1,L2)

LIST Split (LIST list){ List pSecondcell; if (list==NULL) return NULL else if (list->Next==NULL) return NULL else {/* list contiene almeno 2 elementi*/ pScondcell=list->next; list->next = pSecondcell->next; pSecondcell->next=split(pSecondcell->next); return pSecondcell;}}

list a1 a2 a3 … an

SPLIT (di L in due liste ordinate L1,L2)SPLIT (di L in due liste ordinate L1,L2)

LIST Split (LIST list){ List pSecondcell; if (list==NULL) return NULL else if (list->Next==NULL) return NULL else {/* list contiene almeno 2 elementi*/ pScondcell=list->next; list->next = pSecondcell->next; pSecondcell->next=split(pSecondcell->next); return pSecondcell;}}

list a1 a2 a3 … an

pSecondcell

SPLIT (di L in due liste ordinate L1,L2)SPLIT (di L in due liste ordinate L1,L2)

LIST Split (LIST list){ List pSecondcell; if (list==NULL) return NULL else if (list->Next==NULL) return NULL else {/* list contiene almeno 2 elementi*/ pScondcell=list->next; list->next = pSecondcell->next; pSecondcell->next=split(pSecondcell->next); return pSecondcell;}}

list a1 a2 a3 … an

pSecondcell

SPLIT (di L in due liste ordinate L1,L2)SPLIT (di L in due liste ordinate L1,L2)

LIST Split (LIST list){ List pSecondcell; if (list==NULL) return NULL else if (list->Next==NULL) return NULL else {/* list contiene almeno 2 elementi*/ pScondcell=list->next; list->next = pSecondcell->next; pSecondcell->next=split(pSecondcell->next); return pSecondcell;}}

list a1 a2 a3 … an

Split di

pSecondcell

MERGESORTMERGESORT

BASE: Se la lista contiene 0 o 1 elemento, stop Ind.: Split di (a1,a2,…) in (a1,a3,…) e (a2,a4,…) Mergesort delle due liste separatamente Merge delle 2 liste ordinate

MERGESORTMERGESORT

LIST Mergesort (LIST list){ List SecondList;if (list==NULL) return NULLelse if (list->next==NULL) return list else {/* list contiene almeno 2 elementi (da ordinare)*/ SecondList=split(list); return merge(mergesort(list),mergesort(ScondList)); }}

BASE: Se la lista contiene 0 o 1 elemento, stop Ind.: Split di (a1,a2,…) in (a1,a3,…) e (a2,a4,…) Mergesort delle due liste separatamente Merge delle 2 liste ordinate

R.T. della funzione SPLITR.T. della funzione SPLIT

LIST Split (LIST list){ List pSecondcell; if (list==NULL) return NULL else if (list->Next==NULL) return NULL else {/* list contiene almeno 2 elementi*/ pScondcell=list->next; list->next = pSecondcell->next; pSecondcell->next=split(pSecondcell->next); return pSecondcell;}}

Sia n=|list|. Si ha la relazione di ricorrenza T(0)=T(1)=O(1)

T(n)=c+T(n-2), per n>1

Quindi T(n)=O(n)

R.T. del MERGER.T. del MERGE

LIST merge (LIST list1, LIST list2){ if (list1==NULL) return list2 else if (list2==NULL) return list1 else if (list1->element <= list2 -> element)

{ list1->next=merge(list1->next, list2); return list1; } else { list2->next=merge(list1, list2->next); return list2;} }

Siano n1=|list1|, n2=|list2|, n=n1+n2. Si ha la relazione di ricorrenza T(0)=T(1)=O(1) (almeno 1 lista vuota)

T(n)=c+T(n-1), per n>1

Quindi T(n)=O(n)

R.T. MERGESORTR.T. MERGESORT

LIST Mergesort (LIST list){List SecondList; if (list==NULL) return NULL else if (list->next==NULL) return list else /* list contiene almeno 2 elementi (da

ordinare)*/ {SecondList=split(list); return

merge(mergesort(list),mergesort(ScondList));}}

Sia n=|list|. Si ha la relazione di ricorrenza T(0)=T(1)=O(1) (list contiene 0 o 1 elemento)

T(n)=O(n) + O(n) +T(n/2) +T(n/2) =O(n) + 2 T(n/2), per n>1

Quindi T(n)=O(n log n)

R.T. MERGESORTR.T. MERGESORT

T(0)=T(1)=O(1) T(n)=c n + 2 T(n/2), per n>1

Si assuma per semplicità che n=2m (cioè m=log n)

T(2m)=c 2m + 2 T(2m-1) =c 2m + 2 (c 2m-1 + 2 T(2m-2))= c 2m + c 2m +4

T(2m-2) = 2c 2m + 4 T(2m-2) = 2c 2m +4 (c 2m-2 + 2 T(2m-3))=2c 2m + c

2m+8T(2m-3) = 3c 2m + 8 T(2m-3) …… = i c 2m + 2i T(2m-i)

Scegliendo i=m=log n si ha T(n)= T(2m) = m c 2m + 2m T(20)= m c n + n a= = c n log n + a n = O(n log n)

Correttezza MERGESORTCorrettezza MERGESORTLIST Mergesort (LIST list){List SecondList; if (list==NULL) return NULL else if (list->next==NULL) return list else /* list contiene almeno 2 elementi (da ordinare)*/ {SecondList=split(list); return merge(mergesort(list),mergesort(ScondList));}}

Assumiamo correttezza delle funz.split e merge (esercizio)

Per induzione completa su n=|list|.Base. Se n=0 o n=1, restituisce lista inalterata, ok.

Passo (n>1). Assumiamo per i.i. mergesort(list), mergesort(ScondList) restituiscono liste input ordinate.

Quindi Split divide gli elementi lista input con n elementi tra list e Secondlist; mergesort(list),mergesort(ScondList) ordina le liste;

Merge fonde le liste restituendo in output una lista ordinata contenete gli stessi n elementi della lista input.