Ordinamento

Fondamenti di informatica Oggetti e JavaLuca Cabibbo

Luca Cabibbo – Fondamenti di informatica: Oggetti e Java

Copyright © 2004 – The McGraw-Hill Companies srl

Ordinamento1

Ordinamento

Capitolo 24marzo 2004



Ordinamento2

Ordinamento di un arrayProblema dell’ordinamento non decrescente di un array

sia dati un array di interi trasformare l’array dati in modo tale che gli elementi vi

compaiano in ordine non decrescente

-1 0 2 4 8 9 10 16 23 51

10 2 16 0 -1 51 4 23 9 8

ordinamento



Ordinamento3

Ordinamento di array e API di JavaCome si ordina un array?

package java.util classe Arrays metodi di classe void sort(T[] a)

import java.util.Arrays; ... int[] dati; // un array di interi

dati = new int[] { 1, 5, 0, 8, 5 }; /* ora dati vale { 1, 5, 0, 8, 5 } */

/* ordina dati */ Arrays.sort(dati); /* ora dati vale { 0, 1, 5, 5, 8 } */



Ordinamento4

Ordinamento per selezioneL’algoritmo di ordinamento per selezione (selection sort) è basato sulla seguente strategia iterativa

finché l’array non è ordinato seleziona l’elemento di valore minimo dell’array tra quelli

che non sono stati ancora ordinati disponi questo elemento nella sua posizione definitiva



Ordinamento5

Strategia dell’ordinamento per selezione

Per prima cosa, l’ordinamento per selezione determina l’elemento di valore minimo dell’array

l’elemento di valore -1 e indice 5 tale elemento deve essere collocato nella sua posizione

definitiva (posizione 0) va utilizzato uno scambio

16 2 51 10 0 -1

16 2 51 10 0 -1

-1 2 51 10 0 16



Ordinamento6

Scambio di una coppia di elementi dell’array /* Scambia gli elementi di indice i e j di dati. */ private static void scambia(int[] dati, int i, int j) { // pre: dati!=null && 0<= i,j <dati.length int temp; // variabile di supporto per lo scambio

/* scambia dati[i] con dati[j] */ temp = dati[i]; dati[i] = dati[j]; dati[j] = temp; }

16 2 51 10 0 -1

temp

2

13



Ordinamento7

Strategia dell’ordinamento per selezione

L’ordinamento per selezione prosegue determina il valore minimo tra gli elementi dell’array che non

sono ancora ordinati colloca questo elemento nella sua posizione definitiva

e così via, finché tutti gli elementi non sono stati ordinati

-1 2 51 10 0 16

-1 2 51 10 0 16

-1 0 51 10 2 16



Ordinamento8

Strategia dell’ordinamento per selezioneL’algoritmo di ordinamento per selezione

procede per fasi, chiamate passate gestisce una partizione degli elementi dell’array in due insiemi

elementi ordinati elementi non ordinati

Nell’ordinamento per selezione inizialmente, tutti gli elementi sono considerati non ordinati dopo la prima passata, il primo elemento viene ordinato per ordinare l’array si devono eseguire tante passate fino a

quando tutti gli elementi dell’array non risultano ordinati



Ordinamento9

Applicazione dell’ordinamento per selezione

16 2 51 10 0 -1

-1 2 51 10 0 16

-1 0 51 10 2 16

-1 0 2 10 51 16

-1 0 2 10 51 16

-1 0 2 10 16 51



Ordinamento10

Implementazione dell’ordinamento per selezione /* Ordina l'array dati in modo non decrescente. * Ordinamento per selezione. */ public static void selectionSort(int[] dati) { // pre: dati!=null int n; // lunghezza di dati int i; // indice per la scansione di dati int ordinati; // numero di elementi ordinati int imin; // indice dell'elemento di valore // minimo tra gli elementi // non ordinati

... segue ...



Ordinamento11

Implementazione dell’ordinamento per selezione /* ordina dati in modo non decrescente * (ordinamento per selezione) */ n = dati.length; /* esegue n-1 passate */ for (ordinati=0; ordinati<n-1; ordinati++) { /* gli elementi ordinati sono quelli di indice * tra 0 (compreso) e ordinati (escluso) */ /* cerca il minimo tra i non ordinati */ imin = ordinati; for (i=ordinati+1; i<n; i++) if (dati[i]<dati[imin]) imin = i; /* ordina l'elemento in imin */ scambia(dati, ordinati, imin); /* ora gli elementi ordinati sono quelli di * indice compreso tra 0 e ordinati (incluso) */ } }



Ordinamento12

Complessità dell’ordinamento per selezione

Complessità asintotica dell’ordinamento per selezione rispetto alla lunghezza N dell’array da ordinare operazione dominante

il confronto dati[i]<dati[imin] caso peggiore

qualunque contando il numero complessivo di confronti, si può

concludere che

TselectionSort(N) = N2



Ordinamento13

Ordinamento a bolleAlgoritmo di ordinamento a bolle (bubble sort)

la strategia implementata dall’algoritmo è ancora basata su passate e su confronti e scambi

l’ordinamento a bolle confronta, durante ciascuna passata, tutte le coppie di elementi adiacenti tra gli elementi non ordinati dell’array



Ordinamento14

Una passata dell’ordinamento a bolle

10 2 0 16 51 -1

2 10 0 16 51 -1

2 0 10 16 51 -1

2 0 10 16 51 -1

2 0 10 16 51 -1

2 0 10 16 -1 51



Ordinamento15

Applicazione completa dell’ordinamento a bolle

10 2 0 16 51 -1

2 0 10 16 -1 51

0 2 10 -1 16 51

0 2 -1 10 16 51

0 -1 2 10 16 51

-1 0 2 10 16 51



Ordinamento16

Implementazione elementare dell’ordinamento a bolle

/* Ordina l'array dati in modo non decrescente. * Ordinamento a bolle -- versione elementare. */ public static void simpleBubbleSort(int[] dati) { // pre: dati!=null int n; // lunghezza di dati int i; // indice per la scansione di dati int ordinati; // numero di elementi ordinati

... segue ...



Ordinamento17

Implementazione elementare dell’ordinamento a bolle

/* ordina dati in modo non decrescente * (ordinamento a bolle -- versione elementare) */ n = dati.length; /* esegue n-1 passate */ for (ordinati=0; ordinati<n-1; ordinati++) { /* gli elementi ordinati sono quelli di indice * tra n-ordinati (compreso) e n (escluso) */ /* confronta ogni elemento non ordinato * con quello che lo precede * (ed eventualmente li scambia) */ for (i=1; i<n-ordinati; i++) if (dati[i]<dati[i-1]) scambia(dati, i, i-1); /* ora gli elementi ordinati sono quelli di * indice tra n-ordinati-1 (compreso) * e n (escluso) */ } }



Ordinamento18

Considerazioni per migliorare l’ordinamento a bolle

Una passata dell’ordinamento a bolle può portare nella posizione definitiva più di un elemento

0 2 16 -1 10 51

0 2 -1 10 16 51



Ordinamento19

Considerazioni per migliorare l’ordinamento a bolle

È possibile che in una passata dell’ordinamento a bolle non avvengano scambi

-1 0 2 10 16 51

-1 0 2 10 16 51



Ordinamento20

Applicazione dell’ordinamento a bolle

-1 2 16 0 10 51

-1 2 0 10 16 51

-1 0 2 10 16 51

-1 0 2 10 16 51



Ordinamento21

Implementazione dell’ordinamento a bolle /* Ordina l'array dati in modo non decrescente. * Ordinamento a bolle. */ public static void bubbleSort(int[] dati) { // pre: dati!=null int n; // lunghezza di dati int i; // indice per la scansione di dati int ordinati; // numero di elementi ordinati int ultimoScambio; // posizione in cui è avvenuto // l'ultimo scambio durante la // passata corrente /* ultimoScambio vale 0 se non sono stati ancora * eseguiti scambi durante la passata corrente */

... segue ...



Ordinamento22

Implementazione dell’ordinamento a bolle /* ordina dati in modo non decrescente * (ordinamento a bolle) */ n = dati.length; ordinati = 0; /* esegue passate finché dati non è ordinato */ while (ordinati<n-1) { /* gli elementi ordinati sono quelli di indice * tra n-ordinati (compreso) e n (escluso) */ /* confronta ogni elemento non ordinato * con quello che lo precede */ ultimoScambio = 0; for (i=1; i<n-ordinati; i++) if (dati[i]<dati[i-1]) { scambia(dati, i, i-1); ultimoScambio = i; } /* ora gli elementi ordinati sono quelli di * indice tra ultimoScambio e n */ ordinati = n-ultimoScambio; } }



Ordinamento23

Complessità dell’ordinamento a bolleComplessità asintotica dell’ordinamento a bolle

rispetto alla lunghezza N dell’array da ordinare operazione dominante

il confronto dati[i]<dati[i-1] caso peggiore

l’array è ordinato in modo decrescente il numero complessivo di confronti è quadratico

TbubbleSort(N) = N2



Ordinamento24

Ordinamento per inserzioneAlgoritmo di ordinamento per inserzione (insertion sort)

gli elementi sono partizionati in due insiemi elementi relativamente ordinati elementi non relativamente ordinati

inizialmente viene considerato relativamente ordinato il primo elemento dell’array

ad ogni passata colloca il primo tra gli elementi non relativamente ordinati

tra quelli relativamente ordinati



Ordinamento25

Una passata dell’ordinamento per inserzioneEffetto di una passata dell’ordinamento per inserzione

Dinamica dell’inserimento

-1 10 16 0 51 2

-1 0 10 16 51 2

-1 10 16 0 51 2

2

1

3

4



Ordinamento26

Applicazione completa dell’ordinamento per inserzione

10 -1 16 0 51 2

-1 10 16 0 51 2

-1 10 16 0 51 2

-1 0 10 16 51 2

-1 0 10 16 51 2

-1 0 2 10 16 51



Ordinamento27

Implementazione dell’ordinamento per inserzione /* Ordina l'array dati in modo non decrescente. * Ordinamento per inserzione. */ public static void insertionSort(int[] dati) { // pre: dati!=null int n; // lunghezza di dati int i; // indice per la scansione di dati int ordinati; // numero di elementi // "relativamente ordinati" int corrente; // elemento da "ordinare" boolean ins; // è possibile inserire corrente // tra gli "relativamente ordinati"

... segue ...



Ordinamento28

Implementazione dell’ordinamento per inserzione /* ordina dati in modo non decrescente * (ordinamento per inserzione) */ n = dati.length; /* esegue n-1 passate */ for (ordinati=1; ordinati<n; ordinati++) { /* gli elementi "relativamente ordinati" sono * quelli di indice tra 0 e ordinati */ /* viene "ordinato" il primo elemento * tra i "non relativamente ordinati" */ corrente = dati[ordinati]; ins = false; i = ordinati; while (!ins && i>0) if (corrente<dati[i-1]) { // sposta verso dx dati[i] = dati[i-1]; i--; } else ins = true; /* inserisce corrente tra i "rel. ordinati" */ dati[i] = corrente; /* ora gli elementi "rel. ordinati" sono quelli * di indice compreso tra 0 e ordinati */ } }



Ordinamento29

Complessità dell’ordinamento per inserzione

Complessità asintotica dell’ordinamento per inserzione rispetto alla lunghezza N dell’array da ordinare operazione dominante

il confronto corrente<dati[i-1] caso peggiore

l’array è ordinato in modo decrescente il numero complessivo di confronti è quadratico

TinsertionSort(N) = N2



Ordinamento30

Ordinamento per fusioneAlgoritmo di ordinamento per fusione (merge sort) per ordinare una sequenza

se la sequenza da ordinare contiene uno o due elementi, allora la sequenza viene ordinata direttamente

se invece la sequenza da ordinare contiene più di due elementi, allora

gli elementi della sequenza vengono partizionati in due sotto-sequenze

le due sotto-sequenze vengono ordinate separatamente le due sotto-sequenze ordinate vengono fuse in un’unica

sequenza ordinata



Ordinamento31

Strategia dell’ordinamento per fusione

85 24 63 45 17 31 96 50

85 24 63 45 17 31 96 50

24 45 63 85 17 31 50 96

17 24 31 45 50 63 85 96

decomposizione

ordinamento

fusione



Ordinamento32

Strategia ricorsiva dell’ordinamento per fusione

17 24 31 45 50 63 85 96

85 24 63 45 17 31 96 50

85 24 63 45

85 24 63 45 17 31 96 50

17 31 96 50

24 45 63 85 17 31 50 96

24 85 45 63 17 31 50 96

decomposizioni

ordinamenti(semplici)

fusioni



Ordinamento33

Implementazione dell’ordinamento per fusioneL’algoritmo di ordinamento per fusione può essere implementato utilizzando tre metodi

void mergeSort(int[] dati) mergeSortRic merge

Considerazioni per motivi di efficienza, i tre metodi utilizzano un array di

appoggio temp condiviso da tutte le attivazioni



Ordinamento34

Implementazione dell’ordinamento per fusione /* Ordinamento l'array dati in modo non decrescente. * Ordinamento per fusione. */ public static void mergeSort(int[] dati) { // pre: dati!=null int n; // lunghezza di dati

/* ordina dati in modo non decrescente */ n = dati.length; /* avvia la ricorsione: * ordina dati, * dall'elemento di posizione 0 (compreso) * a quello di posizione n (escluso) * usando un array di appoggio di lunghezza n */ mergeSortRic(dati, 0, n, new int[n]); }



Ordinamento35

Implementazione dell’ordinamento per fusione /* Ordina gli elementi di dati tra sinistra (incluso) e * destra (escluso) usando l'array di appoggio temp. */ private static void mergeSortRic(int[] dati, int sinistra, int destra, int[] temp) { int m; // numero di elementi da ordinare int centro; // indice dell'elemento centrale // della sottosequenza da ordinare /* ordina gli elementi di dati tra sinistra * (incluso) e destra (escluso) */ m = destra-sinistra; if (m==2) { // caso base, confronto e scambio if (dati[sinistra]>dati[destra-1]) scambia(dati, sinistra, destra-1); } else if (m>2) { // caso ricorsivo centro = (sinistra+destra)/2; mergeSortRic(dati, sinistra, centro, temp); mergeSortRic(dati, centro, destra, temp); merge(dati, sinistra, centro, destra, temp); } /* m<2 è un altro caso base, la sottosequenza è * già ordinata */ }



Ordinamento36

Complessità dell’ordinamento per fusioneComplessità asintotica dell’ordinamento per fusione

discussa in modo informale rispetto alla lunghezza N dell’array da ordinare attività dominante

fusione di sottosequenze ordinate caso peggiore

qualunque



Ordinamento37

Complessità dell’ordinamento per fusione

un certo numero di livelli di decomposizioni e fusioni in ciascun livello vengono fusi tutti gli elementi

il costo asintotico di ciascun livello di fusioni è N il numero di livelli è log2 N

TmergeSort(N) = N log N

17 24 31 45 50 63 85 96

24 45 63 85 17 31 50 96

24 85 45 63 17 31 50 96

fusioni



Ordinamento38

Ordinamento veloceL’algoritmo di ordinamento di array più usato in pratica è l’ordinamento veloce (quick sort)

58 65 67 45 31 16 96 50

50 16 31 45 58 67 96 65

45 16 31 50 65 67 96

31 16 45 65 96

16 31 45 50 58 65 67 96



Ordinamento39

Complessità dell’ordinamento veloceÈ stato dimostrato l’ordinamento veloce ha, nel caso peggiore, complessità asintotica quadratica rispetto alla lunghezza dell’array da ordinare

tuttavia, l’ordinamento veloce viene solitamente preferito all’ordinamento per fusione

perché?



Ordinamento40

Risultati sperimentaliTempi medi di esecuzione, in secondi

NAlgoritmo 1 000 10 000 100 000 1 000 000

bubble sortelementare

bubble sort

bubble sortbidirezionale

selection sort

insertion sort

merge sort

0.01 0.66 62.35 circa 100minuti

0.02 0.67 62.20 circa 100minuti

0.01 0.47 43.25 circa 70minuti

0.02 0.27 24.05 circa 40minuti

0.01 0.23 18.80 circa 30minuti

0.01 0.01 0.05 0.51

quick sort(API di Java) 0.01 0.02 0.05 0.35

Ordinamento

Documents

Transcript of Ordinamento