Gli algoritmi di ordinamento non basati sul confronto Zotti Paolo 62SI December 2001 email:...

Gli algoritmi di ordinamentoGli algoritmi di ordinamentonon basati sul confrontonon basati sul confrontoZotti Paolo 62SIZotti Paolo 62SIDecember 2001December 2001email: [email protected]: [email protected]

Struttura del Progetto IL PROGETTO E’ DIVISO IN 2 PARTIIL PROGETTO E’ DIVISO IN 2 PARTI:

RELAZIONE

SOFTWARE - Linguaggio C++

Struttura della relazione ARGOMENTI ATTINENTI ALL’ORDINAMENTOARGOMENTI ATTINENTI ALL’ORDINAMENTO

Introduzione all’ordinamento Complessità degli algoritmi di ordinamento I numeri casuali Le liste concatenate (semplici e doppie)

STUDIO DI 3 ALGORITMI DI ORDINAMENTO NON STUDIO DI 3 ALGORITMI DI ORDINAMENTO NON BASATI SUL CONFRONTO E LO SCAMBIOBASATI SUL CONFRONTO E LO SCAMBIO Counting Sort Radix Sort Bucket Sort

TESTING DEGLI ALGORITMITESTING DEGLI ALGORITMI Test sugli algoritmi di ordinamento Test sulla generazione di numeri casuali

Input:Insieme di dati disordinato

Ordinamento effettuato con: Counting Sort o

Radix Sort oBucket Sort

Cosa fa il software creato

Output:Insieme di dati ordinato

Calcolo del tempo

Struttura del software

ScenarioDiagramsScenario

DiagramsClassRand

StateDiagramsState

DiagramsClassBucket Sort

ComponentDiagramsComponent

DiagramsClassListe

Use CaseDiagramsUse Case

DiagramsClass

Counting Sort

StateDiagramsState

DiagramsClassRadix Sort

Il listato principale, Main, coordina tutto il programma

Main

Introduzione

Buon giorno sono il sign. Cormen, il mago degli algoritmi. Vi aiuterò a capire meglio il contenuto di questa relazione.Cominciamo subito con alcune definizioni basilari

Il tempo di calcolo

T ( n )

Il tempo occorrente ad ordinare un insieme di dati, si puo’ rappresentare attraverso una funzione. La funzione T(n).

n

Tempo

Quantità dei dati

Esatto! Il tempo di calcolo di una procedura è il costo complessivo delle operazioni elementari in funzione della dimensione n dei dati in ingresso.

Nel valutare il tempo di calcolo T(n), è difficile quantificare con esattezza il numero di operazioni elementari eseguite.

Questa difficoltà viene aggirata valutando il numero di operazioni in ordine di grandezza, cioè esprimendole come limitazioni della funzione T(n) al tendere all’infinito della dimensione n dei dati in ingresso.

La limitazione può essere:

O Limitazione superiore

Caso Peggiore

Limitazione sup. e inf.

equivalente

Limitazione inferiore

Caso Migliore

Il costo delle operazioni é valutato principalmente nel caso peggiore, perché presenta il vantaggio di garantire che l’algoritmo non richiederà mai per nessun dato in ingresso di dimensione n, un tempo maggiore.

Input OutputALGORITMO

Cosa è un algoritmo???

Qualsiasi procedura computazionale ben definita che prende alcuni valori, come input e produce alcuni valori, come output é chiamata algoritmo.

Un algoritmo é quindi una sequenza di passi computazionali che trasformano l'input nell'output.

Insieme di dati disordinato

ALGORITMODi ordinamento

Cosa è l’ordinamento? L'ordinamento, consiste nel disporre un gruppo di informazioni in ordine crescente o decrescente utilizzando un algoritmo di ordinamento.

Insieme di dati ordinato

Chiave dell’ordinamento

OccupazioneOccupazione

HobbyHobby

ResidenzaResidenza

ReligioneReligione

Nomel

Nome

Cognome

Data nascita

Chiave

Struttura di datiIn genere, quando si esegue un ordinamento, come chiave dell'ordinamento, cioè l'oggetto con cui si fa il confronto, viene utilizzata solo una parte delle informazioni disponibili.

La chiave é quella parte dei dati che determina la posizione relativa dei vari elementi. Pertanto nel confronto fra gli elementi, viene utilizzata solo la chiave ma, nello scambio dei dati, viene trasferita l'intera struttura.

Ora vi spiegherò gli algoritmi di ordinamento trattati in questa relazione.Sono tutti algoritmi che non basano il proprio funzionamento sul confronto e lo scambio di dati.

Passiamo allo studio del primo algoritmo di ordinamento: Counting Sort

Counting Sort: idea di base Counting Sort, si basa sull’ipotesi che ognuno degli “n” elementi

in input sia un intero nell’intervallo da 1 a “k” ove “k” è un numero non troppo grande.

Si determina, per ogni elemento x in input, il numero di elementi minori di x. Questa informazione può essere usata per porre l’elemento x, direttamente nella sua esatta posizione nell’array di output. Per es., se vi sono 10 elementi minori di x, x va messo in undicesima posizione nell’array di output.

L’algoritmo deve gestire situazioni in cui alcuni elementi abbiano lo stesso valore, infatti non si vuole metterli tutti nella stessa posizione nell’array di output.

Counting Sort: proprietà E’ veloce perché fa delle ipotesi sull’input, infatti, E’ veloce perché fa delle ipotesi sull’input, infatti,

assume che l’input, consista di numeri interi in un assume che l’input, consista di numeri interi in un piccolo intervallo.piccolo intervallo.

Stabile Stabile Risorse occorrenti: 3 array Risorse occorrenti: 3 array

array A: array di dimensione n, contenente gli n numeri da ordinare:

array B: array di dimensione n, contenente la sequenza degli n numeri ordinata

Array C: array di dimensione k, temporaneo di lavoro, dove k é il massimo numero trovato in A

Cosa significa stabile???

Un algoritmo è stabile quando elementi con lo stesso valore, compaiono nell’array di input, nello stesso ordine in cui compaiono in quello di output.Cioè, lo spareggio tra due elementi con lo stesso valore avviene secondo la regola per cui qualunque numero compaia per primo nell’array di input, appare per primo nell’array di output.

Counting Sort: esempio

3 6 14 1

CC

43 4

0

11

00 0 00

AA

22 33 44 55 887766

11 22 33 44 55 66

Esecuzione di Counting Sort ssu un array di input A[ 8 ], dove ogni elemento di A é un intero positivo non più grande di k=6.

Temporaneo di lavoroTemporaneo di lavoro

0 0 00 0 00 0

11

BB

22 33 44 55 887766

inputinput outputoutput

Si dimensiona l’array C, con il massimo numero “k” in A

Counting Sort: prima fase

3 6 14 4 43 4

11

AA22 33 44 55 887766

inputinput

Scorrendo tutto l’array partendo da A [ 1 ] fino ad arrivare ad A [ 8 ]; se il valore di un elemento in input é “ i ”, si incrementa C[ i ]. Così, alla fine C[ i ] contiene il numero di elementi di input uguali ad i per ciascun intero i=1,2,…,k.

CC 0 01 0 00

11 22 33 44 55 66

CC 0 01 0 10

11 22 33 44 55 66

CC 0 11 0 10

11 22 33 44 55 66

CC 1 11 0 10

11 22 33 44 55 66

CC 1 12 0 10

11 22 33 44 55 66

CC 1 22 0 10

11 22 33 44 55 66

CC 1 32 0 10

11 22 33 44 55 66

CC 1 42 0 10

11 22 33 44 55 66

Seconda fase: somma cumulata

SSi determina per ciascun i = 1,2,…,k, quanti elementi dell'input sono minori o uguali ad i. Questo viene fatto i determina per ciascun i = 1,2,…,k, quanti elementi dell'input sono minori o uguali ad i. Questo viene fatto determinando la somma cumulata degli elementi dell'array C[ ]. determinando la somma cumulata degli elementi dell'array C[ ].

For x = 2 to 6For x = 2 to 6 C [ i ] = C [ i ] + C [ i-1 ] C [ i ] = C [ i ] + C [ i-1 ]

CC 1 42 0 10

11 22 33 44 55 66

prima

CC 1 73 7 81

11 22 33 44 55 66

dopo

Terza fase: sistemazione in B

0 0 00 0 00 0BB11 22 33 44 55 887766

inputinput3 6 14 1 43 4

11

AA22 33 44 55 887766

outputoutput

CC 1 73 7 81

11 22 33 44 55 66

Counting Sort: terza fase, prima iterazione

Partendo dall’ultima posizione di A, si prende il numero contenuto in A [ 8 ] = 4. Guardiamo cosa è contenuto in C [ 4 ] = 7. Sistemiamo il 4 in B [ 7 ]

0 0 00 4 00 0BB

11 22 33 44 55 887766

3 6 14 4 43 4

11

AA22 33 44 55 887766

OO

CC 1 73 7 81

11 22 33 44 55 66

Counting Sort: seconda iterazione

0 0 00 4 00 0BB

11 22 33 44 55 887766

3 6 14 4 43 4

11

AA22 33 44 55 887766

OO

CC 1 73 7 81

11 22 33 44 55 66

Qualcosa non funziona, così facendo perdiamo un dato.

Attenzione!

Dobbiamo gestire il caso in cui gli elementi contenuti in A, non siano tutti distinti.

3 6 14 4 43 4

11

AA22 33 44 55 887766

OOOO

Ripartiamo dall’inizio

0 0 00 4 00 0BB

CC 1 63 7 81

11 22 33 44 55 887766

11 22 33 55 6644

PrimaPrima

DopoDopo

Per questo, decrementiamo C[4], in modo che alla prossima iterazione, nel caso di elementi non distinti, il numero si inserisca nell’array di output, nella sua corretta posizione.

3 6 14 4 43 4

11

AA22 33 44 55 887766

OO

CC 1 73 7 81

11 22 33 44 55 66

Counting Sort: terza fase, prima iterazione

Partendo dall’ultima posizione di A, si prende il numero contenuto in A [ 8 ] = 4. Guardiamo cosa è contenuto in C [ 4 ] = 7. Sistemiamo il 4 in B [ 7 ] Decrementiamo C [ 4 ]

0 0 00 4 00 0BB

11 22 33 44 55 887766

3 6 14 4 43 4

11

AA22 33 44 55 887766

OO

CC 1 73 7 81

11 22 33 44 55 66

CC 1 63 7 81

11 22 33 55 6644

DopoDopo

Counting Sort: terza fase, seconda iterazione

0 0 00 4 00 4BB

11 22 33 44 55 887766

3 6 14 4 43 4

11

AA22 33 44 55 887766

OO

CC 1 63 7 81

11 22 33 44 55 66

CC 1 53 7 81

11 22 33 55 6644

Counting Sort: terza fase, terza iterazione

0 0 00 4 04 4BB

11 22 33 44 55 887766

3 6 14 4 43 4

11

AA22 33 44 55 887766

OO

CC 1 53 7 81

11 22 33 44 55 66

CC 1 43 7 81

11 22 33 55 6644

DopoDopo

Situzione finale: array ordinato

1 1 33 4 64 4BB

11 22 33 44 55 887766

Continuando con queste iterazioni, alla fine otterremo un’array ordinato.

Tempo impiegato da Counting Sort

T= ( k+n )

Abbiamo calcolato attraverso formule matematiche, che il tempo è lineare e quindi che Il limite superiore e inferiore si equivalgono cioè che il tempo impiegato nel caso peggiore (array ordinato in modo decrescente) equivale al tempo impiegato nel caso migliore (array ordinato in modo crescente).Questa è una caratteristica degli algoritmi di ordinamento non basati sul confronto.Ora dobbiamo verificare con dei test se il tempo calcolato equivale al tempo realmente impiegato dall’algoritmo.

n

Tempo

La limitazione può essere:

O Limitazione superiore

Caso Peggiore

Limitazione sup. e inf.

equivalente

Limitazione inferiore

Caso Migliore

Test Counting Sort

Test Counting Sort

Scopo del test, verificare e dimostrare 2 ipotesi, la prima:Scopo del test, verificare e dimostrare 2 ipotesi, la prima: dato che questo algoritmo di ordinamento é basato sulla distribuzione e usa metodi, per ordinare l'insieme dei dati, non basati sul confronto e lo scambio, l'ordine dei numeri in input non dovrebbe influire sulle prestazioni dell'algoritmo;

Prima ipotesi dimostrata

CASUALE

DECRESCENTE

CRESCENTE

Quantità numeri

45002500500 1000 1500 3000 400035002000 5000 Inf.

Ordine dei numeri

time

L’ordine dei numeri non influisce sulle prestazioni dell’algoritmo.

Test Counting Sort

La seconda ipotesi da dimostrare è la seguente:La seconda ipotesi da dimostrare è la seguente:

il tempo necessario all'ordinamento cresca in modo lineare al crescere di n, dove n rappresenta la quantità dei numeri da ordinare.

Verifica della linearità

CASUALE

DECRESCENTE

CRESCENTE

Quantità numeri

45002500500 1000 1500 3000 400035002000 5000 Inf.

Ordine dei numeri

time

Il tempo cresce in modo lineare, all’aumentare della dimensione n dei dati in ingresso.

Passiamo allo studio del prossimo algoritmo di ordinamento: Radix Sort

Radix Sort

IDEA DI BASEIDEA DI BASE L‘idea, consiste nell'utilizzare un qualsiasi algoritmo di ordinamento, che ordini l'array usando come chiave di ordinamento la cifra meno significativa. Quando l'intero array è ordinato sulla cifra meno significativa, lo si ordina sulla seconda cifra meno significativa utilizzando un algoritmo stabile. Il processo continua finché i numeri sono stati ordinati su tutte le d cifre.A quel punto, i numeri sono completamente ordinati.

Radix SortOssia:

For X = 1 to N Usa un ordinamento stabile per ordinare l’intero array sulla cifra X

Proprietà, particolarità e risorse utilizzate

Risorse hardware occorrenti:Risorse hardware occorrenti: Quelle utilizzate dall’algoritmo di ordinamento intermedio

Particolarità:Particolarità: Radix Sort, ordina i numeri in modo contro intuitivo, cioè non naturale,

ordinando prima sulla cifra meno significativa, poi sulla seconda cifra meno significativa, e così via fino alla cifra più significativa.

Proprietà:Proprietà: Stabilità: Se l'algoritmo utilizzato per l'ordinamento intermedio é stabile,

cioè, ha la proprietà che numeri con lo stesso valore appaiono nell'array di output nello stesso ordine di ingresso, avremo alla fine un array ordinato. La stabilità dell’algoritmo di ordinamento intermedio è indispensabile.

Radix Sort: esempio

329

ARRAY ORIGINALEARRAY ORIGINALE

Esecuzione di Radix Sort ssu un array di input A [ 7 ], dove ogni elemento di A é un intero positivo.

457

657

839

436

720

355

Radix Sort

La prima operazione che deve eseguire La prima operazione che deve eseguire RadixSort, é quella di effettuare l'ordine, RadixSort, é quella di effettuare l'ordine, usando come chiave di ordinamento, la cifra usando come chiave di ordinamento, la cifra meno significativa dei numeri stessi. meno significativa dei numeri stessi.

Logicamente, ad ogni ordinamento sulla Logicamente, ad ogni ordinamento sulla chiave (cifra meno significativa), deve chiave (cifra meno significativa), deve corrispondere uno spostamento di tutta la corrispondere uno spostamento di tutta la struttura (il numero in esame). Per questo, é struttura (il numero in esame). Per questo, é importante che l'ordine intermedio venga importante che l'ordine intermedio venga eseguito da un algoritmo di ordinamento eseguito da un algoritmo di ordinamento stabile.stabile.

720

355

436

457

657

329

839

L’array al primo passaggio: i numeri risultano parzialmente ordinati. L’array al primo passaggio: i numeri risultano parzialmente ordinati.

329

457

657

839

436

720

355

O

Radix Sort

la seconda operazione che deve la seconda operazione che deve eseguire RadixSort é quella di effettuare eseguire RadixSort é quella di effettuare l'ordine, usando come chiave di l'ordine, usando come chiave di ordinamento, la seconda cifra meno ordinamento, la seconda cifra meno significativasignificativa

720

329

436

839

355

457

657

L’array al secondo passaggio: i numeri risultano L’array al secondo passaggio: i numeri risultano parzialmente ordinati. parzialmente ordinati.

720

355

436

457

657

329

839

O

Radix Sort

la terza operazione che deve eseguire la terza operazione che deve eseguire RadixSort é quella di effettuare l'ordine, RadixSort é quella di effettuare l'ordine, usando come chiave di ordinamento, la usando come chiave di ordinamento, la terza cifra meno significativaterza cifra meno significativa

720

329

436

839

355

457

657

L’array al terzo passaggio: i numeri risultano ordinati. L’array al terzo passaggio: i numeri risultano ordinati.

329

355

436

457

657

720

839

O

Possiamo calcolare in anticipo i cicli da effettuare??? Importante: in questo caso, dato che i numeri interi Importante: in questo caso, dato che i numeri interi presi in analisi, sono composti da 3 cifre ciascuno, presi in analisi, sono composti da 3 cifre ciascuno, sono sufficienti 3 passaggi per ottenere un ordine sono sufficienti 3 passaggi per ottenere un ordine definitivo.definitivo.

Quindi, in un array contenente n numeri interi Quindi, in un array contenente n numeri interi composti ognuno di d cifre, occorrono d passaggi per composti ognuno di d cifre, occorrono d passaggi per ordinare completamente il vettore.ordinare completamente il vettore.

Tempo impiegato da Radix Sort

IL TEMPO E’ LINEARE.Il limite superiore e inferiore si equivalgono.

n

Tempo

( d x n )

Test Radix Sort

Test Radix Sort

Scopo del test, verificare e dimostrare 2 ipotesi, la prima:Scopo del test, verificare e dimostrare 2 ipotesi, la prima: dato che questo algoritmo di ordinamento é basato sulla distribuzione e usa metodi, per ordinare l'insieme dei dati, non basati sul confronto e lo scambio, l'ordine dei numeri in input non dovrebbe influire sulle prestazioni dell'algoritmo;

L’ordine dei numeri non influisce sul tempo

CASUALE

DECRESCENTE

CRESCENTE

Quantità numeri

45002500500 1000 1500 3000 400035002000 5000 Inf.

Ordine dei numeri

time

Radix Sortin un range [ 0 / (2^10)-1 ] e [ 0 / (2^31)-1 ]

0

2

4

6

8

10

12

14

Quantita' numeri x 1000

Dec

imi d

i sec

ondo

Cas (2 3̂1)-1

Ord (2 3̂1)-1

Inv (2 3̂1)-1

Casi (2 1̂0)-1

Ord (2 1̂0)-1

Inv (2 1̂0)-1


Test Radix Sort

Seconda ipotesi da dimostrare:Seconda ipotesi da dimostrare:


Verifica della linearità

CASUALE

DECRESCENTE

CRESCENTE

Quantità numeri

45002500500 1000 1500 3000 400035002000 5000 Inf.

Ordine dei numeri

time


0

2

4

6

8

10

12

14


Dec

imi d

i sec

ondo

Cas (2 3̂1)-1

Ord (2 3̂1)-1

Inv (2 3̂1)-1

Casi (2 1̂0)-1

Ord (2 1̂0)-1

Inv (2 1̂0)-1


Passiamo allo studio dell’ultimo algoritmo di ordinamento, cioè Bucket Sort

Bucket Sort

IDEA DI BASEIDEA DI BASE (1) (1)L'idea generale di Bucket Sort é quella di dividere un intervallo prefissato in n sotto intervalli di uguale dimensione, detti bucket (cestini), e quindi distribuire gli n elementi da ordinare nei rispettivi bucket.

Esempio: ordine delle carte da ramino

Cuori

fiori

picche

quadri

5

Il bucket cuori conterrà le carte di cuori

Il bucket quadri conterrà le carte di quadri

Il bucket fiori conterrà le carte di fiori

8

85

75

Il bucket picche conterrà le carte di picche

Bucket Sort

IDEA DI BASEIDEA DI BASE L'idea generale di Bucket Sort é quella di dividere un intervallo prefissato in n sotto intervalli di uguale dimensione, detti bucket (cestini), e quindi distribuire gli n elementi da ordinare nei rispettivi bucket. Sotto l'assunzione che gli elementi dell'input siano uniformemente distribuiti nell'intervallo specificato, non ci si aspetta che molti numeri cadano nello stesso bucket. Per produrre l'output, si ordinano semplicemente i numeri di ogni bucket, con un algoritmo di ordinamento e quindi, si elencano gli elementi di ogni bucket prendendoli in ordine.

Bucket SortCioè:1) For X = 1 to N (N= quantità numeri in input)1) For X = 1 to N (N= quantità numeri in input) trova in quale bucket va inserito l’elemento array[x] e inseriscicelotrova in quale bucket va inserito l’elemento array[x] e inseriscicelo2) For X = 1 to numero bucket2) For X = 1 to numero bucket ordina il bucket [X] con un algoritmo di ordinamentoordina il bucket [X] con un algoritmo di ordinamento3) Concatena insieme i bucket [1]…bucket [2]…3) Concatena insieme i bucket [1]…bucket [2]… …… ……bucket [numero dei bucket]bucket [numero dei bucket]

Bucket Sort

Risorse hardware occorrenti:Risorse hardware occorrenti: Il codice richiede un array, liste [ bucket ], di liste a doppio

concatenamento, dove ogni elemento di liste [ bucket ] rappresenta un bucket.

Proprietà:Proprietà: BucketSort assume che l'input sia generato da un processo casuale che

distribuisce gli elementi in modo uniforme sull'intervallo designato.

Bucket Sort: esempio

Esecuzione di Bucket Sort ssu un array di input A [ 8 ], dove ogni elemento di A é un double positivo. Supponiamo di dividere l'intervallo [0…1], in 10 sotto intervalli di uguale dimensione, e quindi

distribuire gli n elementi da ordinare nei bucket.

AA 0.78 0.17 0.35 0.26 0.72 0.94 0.21 0.12

Situazione iniziale

Prima operazione: distribuire I numeri Bucket 0

AA0.78

0.17

0.35

0.26

0.72

0.94

0.21

0.12

Bucket 1 0.12

0.17

Bucket 20.26

0.21

Bucket 30.35

Bucket 4

Bucket 5

Bucket 6

Bucket 7 0.78

0.72

Bucket 90.94

Bucket Sort

Secondo passaggio

La seconda operazione che deve eseguire Bucket Sort é quella di ordinare i numeri di ogni bucket, con un algoritmo di ordinamento “adatto”, in questo caso, visto che l'insieme numerico in input é composto da tipi double, si può utilizzare l’algoritmo di ordinamento Insert Sort.

Ordinare I numeri

0.17

0.26

0.78

0.12

0.21

Bucket 0Bucket 0

Bucket 1Bucket 1

Bucket 2Bucket 2

Bucket 3Bucket 3

Bucket 4Bucket 4

Bucket 5Bucket 5

Bucket 6Bucket 6

Bucket 7Bucket 7

Bucket 8Bucket 8

Bucket 9Bucket 9 0.94

0.72

0.35

Risultato dell’ordinamento in ogni bucket Bucket 0

Bucket 1 0.12

0.17

Bucket 20.21

0.26

Bucket 30.35

Bucket 4

Bucket 5

Bucket 6

Bucket 7 0.72

0.78

Bucket 90.94

Secondo passaggio: ordinare ogni Bucket con un algoritmo di ordinamento basato sul confronto

0.12

0.21

0.72

0.17

0.26

Bucket 0Bucket 0

Bucket 1Bucket 1

Bucket 2Bucket 2

Bucket 3Bucket 3

Bucket 4Bucket 4

Bucket 5Bucket 5

Bucket 6Bucket 6

Bucket 7Bucket 7

Bucket 8Bucket 8

Bucket 9Bucket 9 0.94

0.78

0.35

Bucket Sort: terzo passaggio

La terza ed ultima operazione da eseguire, é quella di concatenare insieme le liste (bucket) liste[0], liste[1], ..., liste[n-1] in quest'ordine copiando gli elementi nell'array originale ordinati[ ], ottenendo il seguente risultato:

Array ordinato

BB 0.12 0.17 0.21 0.26 0.35 0.72 0.78 0.94

Seconda operazione: ordinare I numeri in ogni bucket

Bucket 1 0.12

0.17

Bucket 20.21

0.26

Bucket 30.35

Bucket 7 0.72

0.78

Bucket 90.94

BB 0.12 0.17 0.21 0.26 0.35 0.72 0.78 0.94

Test Bucket Sort

Precisazioni Per non uscire dall’argomento della relazione, cioè, gli algoritmi non basati sul confronto e lo scambio, e per sperimentare il comportamento di Bucket Sort con un algoritmo di ordinamento non basato sul confronto, ho deciso di usare come algoritmo di ordinamento intermedio, Radix Sort.Il range dei numeri in input è [0…(2^31)-1]Questo intervallo è stato diviso in 214.748 bucket

Verificare e dimostrare che: dato che questo algoritmo di ordinamento é basato sulla distribuzione e usa metodi, per ordinare l'insieme dei dati, non basati sul confronto e lo scambio, l'ordine dei numeri in input non dovrebbe influire sulle prestazioni dell'algoritmo;

L’ordine dei numeri non influisce sul tempo

CASUALE

DECRESCENTE

CRESCENTE

Quantità numeri

45002500500 1000 1500 3000 400035002000 5000 Inf.

Ordine dei numeri

time

Bucket Sort con Radix Sort in un range [ 0 / (2^31)-1 ]

0

50

100

150

200

250


Sec

ondi

Casuali

Ordinati

Inversi


Era ovvio!!! Se l'algoritmo usato per l'ordinamento intermedio non è influenzato dall’ordine dei numeri in input, é ovvio che anche Bucket Sort non ne viene influenzato semplicemente perché questo algoritmo, non fa altro che ordinare ogni bucket con l’algoritmo di ordinamento intermedio Radix Sort.

Verificare e dimostrare che:


IL TEMPO E’ LINEARE

CASUALE

DECRESCENTE

CRESCENTE

Quantità numeri

45002500500 1000 1500 3000 400035002000 5000 Inf.

Ordine dei numeri

time


0

50

100

150

200

250


Sec

ondi

Casuali

Ordinati

Inversi


LOGICO!

Il risultato era quello che ci si aspettava, infatti Bucket Sort non fa altro che ordinare i numeri presenti in ogni bucket, usando l'algoritmo Radix Sort che ha un tempo di ordinamento lineare.

Da notare, il notevole incremento temporale rispetto a Radix Sort, causato dalla gestione delle liste che rappresentano i bucket.


0

2

4

6

8

10

12

14


De

cim

i d

i s

ec

on

do

Cas (2 3̂1)-1

Ord (2 3̂1)-1

Inv (2 3̂1)-1

Casi (2 1̂0)-1

Ord (2 1̂0)-1

Inv (2 1̂0)-1

Differenza con Radix Sort


0

50

100

150

200

250


Se

co

nd

i

Casuali

Ordinati

Inversi

Secondo Test Bucket Sort

Premessa

Si consideri il comportamento di un qualsiasi algoritmo di ordinamento Si consideri il comportamento di un qualsiasi algoritmo di ordinamento basato sul confronto. Il tempo impiegato da questo algoritmo dipende basato sul confronto. Il tempo impiegato da questo algoritmo dipende pesantemente dall'ordine con cui i numeri sono memorizzati nei cestini pesantemente dall'ordine con cui i numeri sono memorizzati nei cestini e dalla quantità numerica presente in ognuno di essi. e dalla quantità numerica presente in ognuno di essi.

Nel caso peggiore (ordine inverso), assumendo che ci siano n Nel caso peggiore (ordine inverso), assumendo che ci siano n elementi nel bucket dobbiamo scorrere n-1 elementi. Per ogni elementi nel bucket dobbiamo scorrere n-1 elementi. Per ogni elemento occorre esaminare e spostare altri n-1 elementi, per cui elemento occorre esaminare e spostare altri n-1 elementi, per cui risulta una complessità O(n^2), cioè il tempo non cresce in modo risulta una complessità O(n^2), cioè il tempo non cresce in modo lineare ma esponenziale.lineare ma esponenziale.

Con una tale complessità, é conveniente che la presenza numerica in Con una tale complessità, é conveniente che la presenza numerica in ogni cestino sia la più bassa possibile quindi maggiore è ogni cestino sia la più bassa possibile quindi maggiore è Il numero dei cestini minore sarà la presenza numerica in ognuno di essi e di conseguenza minore sarà il tempo di calcolo.

Questo è lo scopo della distribuzione di Bucket Sort

Insert Sort

casuali

SCOPERTA

Visto che Radix Sort ha un tempo lineare la distribuzione diventa assurda perché non ci interessa più che la distribuzione numerica in ogni cestino sia la più bassa possibileIl tempo è e resterà sempre lineare.

La conseguenza di questa affermazione é che Bucket Sort, in questo caso, deve essere implementato con 1 solo cestino. A questo punto é solo una perdita di tempo sistemare i numeri nel cestino per poi ordinarli con Radix Sort, é più intelligente farli ordinare direttamente da Radix Sort.

Verificare e dimostrare che: implementare l'algoritmo Bucket Sort usando per l'ordinamento intermedio un algoritmo non basato sul confronto è assurdo. Nessun testo analizzato, contiene spiegazioni riguardo alla fondamentale importanza di usare per l’ordinamento intermedio un algoritmo basato sul confronto e al contrario, dell’assurdità di usarne uno non basato sul confronto

L’esperimento consiste nell’ordinare le stesse quantità numeriche, prima utilizzando un solo bucket e poi utilizzandoli tutti, osservando se il tempo è lo stesso.

Invece usando Radix Sort

Quantità numeri

45002500500 1000 1500 3000 400035002000 5000 Inf.

time


0

100

200

300

400

500

600

700

800

900


Sec

ondi

1 Cestino

214748 Cestini

Il notevole incremento temporale è causato dalla gestione delle liste( bucket).

Il tempo è sprecato in questa fase Bucket 0

Bucket 1 0.12

0.17

Bucket 20.21

0.26

Bucket 30.35

Bucket 4

Bucket 5

Bucket 6

Bucket 7 0.72

0.78

Bucket 90.94

Analisi teoricaEscludendo il tempo utilizzato nella gestione delle liste e nella distribuzione degli n numeri nei cestini, le prestazioni devono essere equivalenti sia nel caso che si utilizzi 1 solo cestino, sia che si utilizzino tutti i cestini.L’ipotesi è dimostrata.

Importante

Note:Note: Questo non significa che Bucket Sort è inutile, infatti é nato per

ordinare sequenze numeriche in virgola mobile. Usando questo tipo di dati, non é possibile implementare per l'ordinamento intermedio, algoritmi come Counting Sort o Radix Sort, ma diventa necessario rivolgersi ad algoritmi che basano il loro funzionamento sul confronto e lo scambio. Infatti, implementando Bucket Sort con un algoritmo di questo tipo, il numero dei cestini influisce in maniera determinante sul tempo di calcolo perché maggiore é il numero dei cestini, minore sarà la distribuzione numerica in ognuno di essi e di conseguenza, minore sarà il tempo di calcolo.

Test Bucket Sort

A titolo di curiosità si osservi il prossimo grafico, che presenta Bucket A titolo di curiosità si osservi il prossimo grafico, che presenta Bucket Sort implementato con l'algoritmo di ordinamento intermedio Insert Sort implementato con l'algoritmo di ordinamento intermedio Insert Sort. Per l'ordinamento di un insieme di numeri fino a circa 1 milione i Sort. Per l'ordinamento di un insieme di numeri fino a circa 1 milione i tempi sono molto vicini allo zero, ma superando il milione di elementi il tempi sono molto vicini allo zero, ma superando il milione di elementi il tempo di calcolo esplode. Infatti, quando la quantità di numeri é tempo di calcolo esplode. Infatti, quando la quantità di numeri é relativamente bassa, la distribuzione numerica in ogni cestino é di relativamente bassa, la distribuzione numerica in ogni cestino é di conseguenza molto bassa e Insert Sort deve eseguire un numero conseguenza molto bassa e Insert Sort deve eseguire un numero bassissimo di confronti e scambi. bassissimo di confronti e scambi.

Quando la quantità di numeri presenti in ogni cestino comincia ad Quando la quantità di numeri presenti in ogni cestino comincia ad aumentare notevolmente, il tempo occorrente all'ordinamento cresce aumentare notevolmente, il tempo occorrente all'ordinamento cresce in modo esponenziale. in modo esponenziale.

Grafico

I numeri casuali

Il prossimo test viene effettuato per dimostrare che le sequenze numeriche create dal generatore di numeri casuali, siano effettivamente…..casuali. (forse!!!)

Numeri casuali

Scopo del test, verificare e dimostrare che:Scopo del test, verificare e dimostrare che: Il primo esperimento, é stato eseguito per verificare che il

generatore di numeri casuali crei un insieme di numeri interi, effettivamente distribuiti nell'intervallo [0..2 ^(31-1)]

Il generatore crea 20.000.000 di numeri e li riversa nei 214.748 bucket che utilizza l’algoritmo BucketSort;

viene contata la quantità di numeri presente in ogni cestino. l'operazione viene ripetuta altre 2 volte. viene calcolata la media in ogni cestino, riportata sul grafico. Se il generatore di numeri casuali, crea numeri interi

uniformemente distribuiti nell'intervallo prefissato, nei cestini dovremmo trovare quantità piu o meno uguali di numeri.

GraficoPresenza Numerica Nei Cestini

0

20

40

60

80

100

120

1404

76

64

15

32

4

22

98

4

30

64

4

38

30

4

45

96

4

53

62

4

61

28

4

68

94

4

76

60

4

84

26

4

91

92

4

99

58

4

1E

+0

5

Numero del Cestino

Pre

se

nze Presenze

Bucket Sort Insert sort Quick Sort

Un algoritmo "efficiente" deve svolgere il suo compito in un tempo accettabile utilizzando le risorse a

disposizione senza sprechi.

Radix Sort Counting Sort

Quindi uso intelligente delle risorse

Conclusioni

Architetture e algoritmi

Intel 286

Radix Sort

Insert Sort

Algoritmi ideati per risolvere lo stesso problema, Algoritmi ideati per risolvere lo stesso problema, spesso differiscono vistosamente per quanto spesso differiscono vistosamente per quanto riguarda la loro efficienza e queste differenze riguarda la loro efficienza e queste differenze possono essere più significative della differenza possono essere più significative della differenza tra un calcolatore molto lento e un tra un calcolatore molto lento e un supercomputer. supercomputer.

Infatti, se proviamo ad ordinare 10.000.000 di Infatti, se proviamo ad ordinare 10.000.000 di numeri ordinati in modo decrescente, con Radix numeri ordinati in modo decrescente, con Radix Sort, su un computer dotato di processore intel Sort, su un computer dotato di processore intel 286, otterremo un tempo di ordinamento 286, otterremo un tempo di ordinamento estremamente basso, rispetto ad un estremamente basso, rispetto ad un ordinamento della stessa sequenza numerica, ordinamento della stessa sequenza numerica, effettuato sul computer dell’Interprise, usando effettuato sul computer dell’Interprise, usando

Insert Sort.Insert Sort.

Galaxy 10086

Questo non significa che Insert Sort, è un algoritmo di scarsa utilità.Infatti con questo algoritmo si possono ordinare i numeri in virgola mobile, cosa non possibile con gli algoritmi analizzati in questa relazione.Ogni algoritmo ha il suo campo di applicazione

Algoritmi efficienti e hardware veloce

L'esempio precedente vuole dimostrare che:progettare algoritmi efficienti é importante quanto progettare sistemi hardware sempre più veloci;usare algoritmi specifici in base al problema da risolvere significa usare in modo intelligente le risorse e abbassare notevolmente i tempi di calcolo.

“Sono due tessere dello stesso mosaico”

Efficienza Miglior efficienza

The Best

Quale algoritmo di ordinamento si é dimostrato il più Quale algoritmo di ordinamento si é dimostrato il più efficiente in termini di utilizzo:efficiente in termini di utilizzo:

delle risorse ?

…e del tempo ?

Sono tutti ottimi

• Tutti gli algoritmi analizzati in questa ricerca sono degli ottimi "algoritmi di ordinamento", progettati in modo intelligente. Ognuno di questi è ottimo se usato in modo specifico.

Bucket SortRadix Sort

Counting SortRadix Sort Counting SortBucket Sort

Uso Intelligente degli algoritmi

Counting Sort

La scelta dell’algoritmo dipende dal lavoro che si

deve eseguire.

Sono il più veloce, ma la mia limitazione di range mi penalizza pesantemente, quindi usatemi quando dovete ordinare numeri appartenenti ad un intervallo limitato, per es 0…2^10

Sono un po’ meno veloce di Counting Sort ma lavoro in qualsiasi Range

Radix Sort

• IDEA: Avere a disposizione un’ampia varietà

di algoritmi da usare in modo appropriato a seconda del problema da risolvere

Io devo lavorare solo con elementi in virgola mobile

Bucket Sort

THE END

Gli algoritmi di ordinamento non basati sul confronto Zotti Paolo 62SI December 2001 email:...

Documents

Transcript of Gli algoritmi di ordinamento non basati sul confronto Zotti Paolo 62SI December 2001 email:...