Algoritmi di sorting

comunque la l’elemen

prima volta to è a

vedo gli N posto

elementi, poi Altro

(N-1) etc… pregio:

se

l’array è

allocato

in modo

contiguo

sfrutto la

località

degli

accessi

Insertionsor Prende in Se l’array è Se il vettore è Sì Pregio:

t ordine ordinato già ordinato richiede

ciascun faccio (N-1) allora il costo O(N) se

elemento e lo confronti, non è O(N). gli

confronta con ho slittamenti elementi

Se il vettore

i precedenti, ne inserzioni sono già

non è

mettendolo ordinati

ordinato ho:

nella caso

posizione ·2 miglior

corretta e e: (N-1)

shiftando confron

rigidamente ti e 0

gli altri scambi

elementi in

·3

verso destra media:

N /4

2

confron

ti e

N /4

2

scambi

Caso

·4 peggior

e: N /2

2

confron

ti e

N /2

2

scambi

Quindi se non

è ordinato ho

O(N )

2

Richiedono tutti nel caso peggiore e ordinano tutti in place.

L’unico un po' migliore è insertionsort che richiede O(N) se è già

ordinato

Se noi esaminiamo il comportamento di un programma, che è

l’implementazione di un algoritmo, e lo caratterizziamo in termini di

una variabile N che rappresenta la cardinalità dell’insieme, scopriamo

che il tempo è descrivibile come un polinomio in funzione di N:

Noi potremmo avere una situazione in cui, tre programmi, che

implementano lo stesso algoritmo in modo diverso, hanno tempi

diversi.

K0 è il tempo di setup, cioè il tempo prima che il programma si metta a

fare qualcosa di utile. Programmi diversi che implementano lo stesso

algoritmo hanno tempo iniziale diverso, alcuni sono più veloci all’inizio

ma poi tendono a peggiorare rapidamente il loro comportamento.

Comunque nei tre casi per N molto grande i tre programmi diventano

tutti e tre pessimi perché il loro costo asintoticamente è O(N^2).

Quindi la vera differenza non la fa quanto ci mettono ad iniziare.

Se però N è piccolo, allora sceglieremo il programma che parte più

velocemente.

Algoritmo Funzionamen Passi Costo In place Pregi e

to difetti

mergesort Usa un L’operazio O(N*log(N) no Pregio: è il

metodo ne di ) più

ricorsivo merge è efficiente

fatta circa

Parto log(N)

dall’array volte

originale, lo

divido in due

sotto-array e

li ordino,

però per

ordinarli li

divido a loro

volta in due

sotto-array e

li ordino, per

ordinali li

divido a loro

volta etc…

continuo così

finché non

ho ottenuto

più sotto-

array di

dimensione

2

Advanced sorting:

algoritmo Funzionament Passi Costo In-place Pregi e

o difetti

Shellsort Si basa Se h è il gap O(N /h) si Va bene

2

sull’insertion non ho per

Se h=N/2

sort. Viene ordinato N strutture

la

scelto un gap elementi ma di medie

complessit

(passo) e si N/h dimension

à è O(N)

ordinano gli elementi i. E’ una

Non si è

elementi per h volte, via di

riusciti a

distanziati di è come se mezzo tra

studiare

quel passo stessimo gli

teoricamen

partendo ordinando h algoritmi

te la sua

dall’elemento sottosequen come