CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene...

19
CHE COS’è UN ALGORITMO di CHE COS’è UN ALGORITMO di ORDINAMENTO? ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un viene utilizzato per elencare gli elementi di un insieme secondo una sequenza stabilita da una insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue. In minore (o maggiore) di quello che lo segue. In assenza di altre specifiche, la relazione d'ordine assenza di altre specifiche, la relazione d'ordine viene sempre considerata totale (cioè tale da viene sempre considerata totale (cioè tale da rendere sempre possibile il confronto tra due rendere sempre possibile il confronto tra due elementi dell'insieme): le relazioni d'ordine elementi dell'insieme): le relazioni d'ordine parziale danno origine agli algoritmi di parziale danno origine agli algoritmi di ordinamento topologico. A seconda del verso della ordinamento topologico. A seconda del verso della relazione considerato, un ordinamento può essere relazione considerato, un ordinamento può essere

Transcript of CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene...

Page 1: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

CHE COS’è UN ALGORITMO di ORDINAMENTO?CHE COS’è UN ALGORITMO di ORDINAMENTO?Un algoritmo di ordinamento è un algoritmo che viene utilizzato per Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo una sequenza stabilita da una elencare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue. In assenza di altre specifiche, la relazione d'ordine quello che lo segue. In assenza di altre specifiche, la relazione d'ordine viene sempre considerata totale (cioè tale da rendere sempre possibile il viene sempre considerata totale (cioè tale da rendere sempre possibile il confronto tra due elementi dell'insieme): le relazioni d'ordine parziale confronto tra due elementi dell'insieme): le relazioni d'ordine parziale danno origine agli algoritmi di ordinamento topologico. A seconda del danno origine agli algoritmi di ordinamento topologico. A seconda del verso della relazione considerato, un ordinamento può essere ascendente o verso della relazione considerato, un ordinamento può essere ascendente o discendente.discendente.

Page 2: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

TIPI di ALGORITMI di TIPI di ALGORITMI di ORDINAMENTOORDINAMENTO

Selection sortSelection sort Insertion sortInsertion sort Bubble sortBubble sort Quick sortQuick sort Merge sortMerge sort Heap sortHeap sort Couting sortCouting sort Bucket sortBucket sort

Page 3: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

AlgoritmoAlgoritmo Caso Caso MiglioreMigliore

Caso Caso MedioMedio

Caso Caso PeggiorePeggiore

SELECTIONSORTSELECTIONSORT nn²² -- nn²²INSERTIONSOERTINSERTIONSOERT nn -- nn²²BUBBLESORTBUBBLESORT nn -- nn²²QUICKSORTQUICKSORT nlognlog22 n n nlognlog22 n n nn²²MERGESORTMERGESORT nlognlog22 n n nlognlog22 n n nlognlog22 n nHEAPSORTHEAPSORT nlognlog22 n n nlognlog22 n n nlognlog22 n nCOUTINGSORTCOUTINGSORT nn nn nnBUCKETSORTBUCKETSORT -- -- nn

Page 4: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

I primi 3 algoritmi analizzati – SELECTION SORT, INSERTION SORT e BUBBLE I primi 3 algoritmi analizzati – SELECTION SORT, INSERTION SORT e BUBBLE

SORT – sono estremamente elementari e consentono un’implementazione assai SORT – sono estremamente elementari e consentono un’implementazione assai semplice: semplice:

-  il costo da pagare alla semplicità di questi algoritmi sta ovviamente nell’elevata -  il costo da pagare alla semplicità di questi algoritmi sta ovviamente nell’elevata complessità computazionale,che inquesti casi è O(n2). complessità computazionale,che inquesti casi è O(n2).

L’algoritmo QUICKSORT consente di raggiungere una complessità di O(nlog2n) nel L’algoritmo QUICKSORT consente di raggiungere una complessità di O(nlog2n) nel caso medio, mentre nel caso più sfavorevole ritorna ad una complessità di O(n2). caso medio, mentre nel caso più sfavorevole ritorna ad una complessità di O(n2).

Gli algoritmi MERGESORT e HEAPSORT consentono di raggiungere una Gli algoritmi MERGESORT e HEAPSORT consentono di raggiungere una complessità di O(nlog2n) anche nel caso peggiore: complessità di O(nlog2n) anche nel caso peggiore:

-  è possibile dimostrare che il limite inferiore alla complessità computazionale del -  è possibile dimostrare che il limite inferiore alla complessità computazionale del problema dell’ordinamento mediante confronti (senza dunque poter sfruttare altre problema dell’ordinamento mediante confronti (senza dunque poter sfruttare altre informazioni sull’insieme da ordinare) è proprio pari a nlog2n, possiamo concludere informazioni sull’insieme da ordinare) è proprio pari a nlog2n, possiamo concludere che tali algoritmi sono ottimiche tali algoritmi sono ottimi

Gli algoritmi COUNTING SORT e BUCKET SORT sono invece basati su altri criteri Gli algoritmi COUNTING SORT e BUCKET SORT sono invece basati su altri criteri e strategie, diverse dal confronto fra i valori degli elementi dell’insieme da ordinare, e e strategie, diverse dal confronto fra i valori degli elementi dell’insieme da ordinare, e sfruttano pertanto altre informazioni sui dati in input: sfruttano pertanto altre informazioni sui dati in input:

-  Grazie a questo consentono di ridurre ulteriormente la complessità nel caso peggiore, -  Grazie a questo consentono di ridurre ulteriormente la complessità nel caso peggiore, arrivando ad una complessità lineare di (n). Sotto a tale soglia è impossibile arrivando ad una complessità lineare di (n). Sotto a tale soglia è impossibile scendere,dal momento che per ordinare un insieme di n elementi è necessario scendere,dal momento che per ordinare un insieme di n elementi è necessario esaminarli tutti almeno una volta. esaminarli tutti almeno una volta.

Ci possiamo concentrare soltanto nello studio della complessità nel caso peggiore, Ci possiamo concentrare soltanto nello studio della complessità nel caso peggiore, dal momento che è il parametro più conservativo per la valutazione dal momento che è il parametro più conservativo per la valutazione dell’ efficienza di un algoritmo. dell’ efficienza di un algoritmo.

Page 5: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Selection sort Selection sort Un algoritmo decisamente intuitivo ed estremamente semplice.Un algoritmo decisamente intuitivo ed estremamente semplice.

Nella pratica è utile quando l’insieme da ordinare è composto da pochi elementi e Nella pratica è utile quando l’insieme da ordinare è composto da pochi elementi e dunque anche un algoritmo non molto efficiente può essere utilizzato con il vantaggio dunque anche un algoritmo non molto efficiente può essere utilizzato con il vantaggio di non rendere troppo sofisticata la codifica del programma che lo implementa. di non rendere troppo sofisticata la codifica del programma che lo implementa.

L’idea di fondo su cui si basa l’algoritmo è quella di ripetere per n volte una procedura L’idea di fondo su cui si basa l’algoritmo è quella di ripetere per n volte una procedura in grado di selezionare alla i-esima iterazione l’elemento più piccolo nell’insieme e di in grado di selezionare alla i-esima iterazione l’elemento più piccolo nell’insieme e di scambiarlo con l’elemento che in quel momento occupa la posizione iscambiarlo con l’elemento che in quel momento occupa la posizione i

In altre parole: In altre parole: -  alla prima iterazione dell’algoritmo verrà selezionato l’elemento più -  alla prima iterazione dell’algoritmo verrà selezionato l’elemento più piccolo dell’intero insieme e sarà scambiato con quello che occupa la piccolo dell’intero insieme e sarà scambiato con quello che occupa la prima posizione; prima posizione; -  alla seconda iterazione è selezionato il secondo elemento più piccolo dell’insieme, -  alla seconda iterazione è selezionato il secondo elemento più piccolo dell’insieme,

ossia l’elemento più piccolo dell’insieme “ridotto” costituito dagli elementi ossia l’elemento più piccolo dell’insieme “ridotto” costituito dagli elementi {a2,a3,...,an}ed è scambiato con l’elemento che occupa la seconda posizione; {a2,a3,...,an}ed è scambiato con l’elemento che occupa la seconda posizione;

-  Si ripete fino ad aver collocato nella posizione corretta tutti gli n elementi-  Si ripete fino ad aver collocato nella posizione corretta tutti gli n elementi

Page 6: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Esempio “Selection Sort”Esempio “Selection Sort”void selectionsort(int[] a, int n) { void selectionsort(int[] a, int n) { int i=0; int i=0; for (i=0;i<n;i++) { for (i=0;i<n;i++) { int j=0; int j=0; for (j=i+1;j<n;j++) { for (j=i+1;j<n;j++) { if (a[j] < a[i]) { if (a[j] < a[i]) { int temp=a[j]; int temp=a[j]; a[j]=a[i]; a[j]=a[i]; a[i]=temp; a[i]=temp; } } } } } }

Page 7: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Insertion sortInsertion sort Ordinamento a inserimento, è un algoritmo relativamente semplice per Ordinamento a inserimento, è un algoritmo relativamente semplice per ordinare un array. ordinare un array.

Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. carte.

Algoritmo in place, cioè ordina l'array senza doverne creare una copia, risparmiando Algoritmo in place, cioè ordina l'array senza doverne creare una copia, risparmiando memoria. memoria.

Ad ogni istante (iterazione), il vettore è costituito da una parte iniziale ordinata (che Ad ogni istante (iterazione), il vettore è costituito da una parte iniziale ordinata (che aumenta di volta in volta) e da la parte rimanente che aumenta di volta in volta) e da la parte rimanente che

contiene i valori da ordinare. contiene i valori da ordinare.

Per ogni valore ancora da inserire, viene fatta una ricerca binaria nella Per ogni valore ancora da inserire, viene fatta una ricerca binaria nella parte ordinata del vettore e vengono spostati in avanti tutti gli elementi parte ordinata del vettore e vengono spostati in avanti tutti gli elementi per liberare la posizione per liberare la posizione

   Nella posizione liberata viene inserito il valoreNella posizione liberata viene inserito il valore

Page 8: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Esempio “Insertion Sort”Esempio “Insertion Sort”void insertion_sort(int[] A,int n) { void insertion_sort(int[] A,int n) { int i=0,j=0; int i=0,j=0; for (i=1;i<n;i++) { for (i=1;i<n;i++) { int x=a[i], s=1, d=i-1; int x=a[i], s=1, d=i-1; while (s<=d) { while (s<=d) { int m=(s+d)/2; int m=(s+d)/2; if (x<a[m]) d=m-1; if (x<a[m]) d=m-1; else s=m+1; else s=m+1; } } for (j=i-1,j>=s;j--) a[j+1]=a[j]; for (j=i-1,j>=s;j--) a[j+1]=a[j]; a[s]=x; a[s]=x; } } } }

Page 9: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Bubble sortBubble sort L’algoritmo BUBBLE SORT (ordinamento a bolle) so basa sull’idea di far emergere pian piano L’algoritmo BUBBLE SORT (ordinamento a bolle) so basa sull’idea di far emergere pian piano

gli elementi più piccoli verso l’inizio dell’insieme da ordinare facendo sprofondare gli elementi gli elementi più piccoli verso l’inizio dell’insieme da ordinare facendo sprofondare gli elementi maggiori verso il fondo:maggiori verso il fondo:

- un po’ come le bollicine in un bicchiere di spumante -> da qui il nome di ordinamento - un po’ come le bollicine in un bicchiere di spumante -> da qui il nome di ordinamento a bolle. a bolle.

La strategia adottata è quella di scorrere più colte la sequenza da ordinare, verificando ad ogni La strategia adottata è quella di scorrere più colte la sequenza da ordinare, verificando ad ogni passo l’ordinamento reciproco degli elementi contigui, ai e ai+1, ed eventualmente scambiando passo l’ordinamento reciproco degli elementi contigui, ai e ai+1, ed eventualmente scambiando la posizionela posizione

di quelle coppie di elementi non ordinate.di quelle coppie di elementi non ordinate.

Procedendo dall’inizio alla fine della sequenza, al termine di ogni scansione si è ottenuto che Procedendo dall’inizio alla fine della sequenza, al termine di ogni scansione si è ottenuto che l’elemento massimo è finito in fondo alla sequenza stessa, mentre gli elementi più piccoli hanno l’elemento massimo è finito in fondo alla sequenza stessa, mentre gli elementi più piccoli hanno cominciato acominciato a

spostarsi verso l’inizio della sequenza stessa.spostarsi verso l’inizio della sequenza stessa.

Dunque alla fine della prima scansione possiamo essere certi che l’elemento massimo ha Dunque alla fine della prima scansione possiamo essere certi che l’elemento massimo ha raggiunto la sua posizione corretta nell’ultima posizione della sequenza:raggiunto la sua posizione corretta nell’ultima posizione della sequenza:

- la scansione successiva potrà fermarsi senza considerare l’ultimo elemento dell’insieme - la scansione successiva potrà fermarsi senza considerare l’ultimo elemento dell’insieme e riuscendo così a collocare nella posizione corretta (la penultima) il secondo e riuscendo così a collocare nella posizione corretta (la penultima) il secondo elemento più grande dell’insieme;elemento più grande dell’insieme;

Si ripete fino ad aver completato l’ ordinamento dell’intera sequenzaSi ripete fino ad aver completato l’ ordinamento dell’intera sequenza

Page 10: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Esempio “Bubble Sort”Esempio “Bubble Sort” void bubblesort(int[] a, int n) { bool scambio=true; int ultimo=n-1,i=0; while (scambio) { scambio=false; for (i=0;i<ultimo;i++) { if (a[i]>a[i+1]) { int temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; scambio=true; } } ultimo--; }}

Page 11: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Quick SortQuick Sort Quicksort è un algoritmo di ordinamento ricorsivo in place che si basa sul Quicksort è un algoritmo di ordinamento ricorsivo in place che si basa sul

paradigma divide et impera.paradigma divide et impera.

La base del suo funzionamento è l’utilizzo ricorsivo della procedura La base del suo funzionamento è l’utilizzo ricorsivo della procedura partition:partition:

- preso un elemento da un array si pongono gli elementi minori a sinistra - preso un elemento da un array si pongono gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destrarispetto a questo e gli elementi maggiori a destra

- La stessa procedura poi è richiamata in modo ricorsivo sui due sotto - La stessa procedura poi è richiamata in modo ricorsivo sui due sotto insiemiinsiemi

Il Quicksort, termine che tradotto letteralmente in italiano indica Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, in generale, ordinamento rapido, è l'algoritmo di ordinamento che ha, in generale, prestazioni migliori tra quelli basati su confronto.prestazioni migliori tra quelli basati su confronto.

Page 12: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Approccio ricorsivoApproccio ricorsivo L’idea base può esprimersi agevolmente in termini ricorsivi.L’idea base può esprimersi agevolmente in termini ricorsivi. - Ad ogni stadio si effettua un ordinamento parziale di una - Ad ogni stadio si effettua un ordinamento parziale di una

sequenza di oggetti da ordinare. Assunto un elemento come sequenza di oggetti da ordinare. Assunto un elemento come perno dello stadio, si confrontano con esso gli altri elementi e perno dello stadio, si confrontano con esso gli altri elementi e si posizionano alla sua sinistra i minori e a destra i maggiori, si posizionano alla sua sinistra i minori e a destra i maggiori, senza tener conto del loro ordine. Dopo questo stadio si ha che senza tener conto del loro ordine. Dopo questo stadio si ha che il perno è nella sua posizioneil perno è nella sua posizione

definitiva.definitiva. - Successivamente si procede in modo ricorsivo - Successivamente si procede in modo ricorsivo

all'ordinamento parziale delle sottosequenze di elementi all'ordinamento parziale delle sottosequenze di elementi rimasti non ordinati, fino al loro esaurimento.rimasti non ordinati, fino al loro esaurimento.

Page 13: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Esempio “Quick Sort”Esempio “Quick Sort” void sort(int[] array, int begin, int end) {void sort(int[] array, int begin, int end) { int pivot, l, r;int pivot, l, r; if (end > begin) {if (end > begin) { pivot = array[begin];pivot = array[begin]; l = begin + 1;l = begin + 1; r = end+1;r = end+1; while (l < r) {while (l < r) { if (array[l] < pivot) l++;if (array[l] < pivot) l++; else {else { r--;r--; swap(array[l], array[r]);swap(array[l], array[r]); }}l--;l--; swap(array[begin], array[l]);swap(array[begin], array[l]); sort(array, begin, l);sort(array, begin, l); sort(array, r, end);sort(array, r, end); }}}}

Scambia x con y e viceversa.Scambia x con y e viceversa.Parametri passati per riferimento.Parametri passati per riferimento. void swap(int & x, int & y) {void swap(int & x, int & y) { int temp=x;int temp=x; x=y;x=y; y=temp;y=temp;}}

Page 14: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Merge SortMerge Sort Il merge sort è un algoritmo di ordinamento molto Il merge sort è un algoritmo di ordinamento molto

intuitivo e abbastanza rapido, che utilizza un processo intuitivo e abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.di risoluzione ricorsivo.

L’idea alla base del merge sort è il procedimento L’idea alla base del merge sort è il procedimento Divide et Impera, che consiste nella suddivisione del Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi via via più piccoli.problema in sottoproblemi via via più piccoli.

Il merge sort opera quindi dividendo l’insieme da Il merge sort opera quindi dividendo l’insieme da ordinare in due metà e procedendo all'ordinamento ordinare in due metà e procedendo all'ordinamento delle medesime ricorsivamente. Quando si sono delle medesime ricorsivamente. Quando si sono divise tutte le metà si procede alla loro fusione divise tutte le metà si procede alla loro fusione (merge appunto) costruendo un insieme ordinato.(merge appunto) costruendo un insieme ordinato.

Page 15: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Due fasiDue fasi Fase 1: divideFase 1: divide - L'insieme di elementi viene diviso in 2 metà. Se - L'insieme di elementi viene diviso in 2 metà. Se

l'insieme è composto da un numero dispari di l'insieme è composto da un numero dispari di elementi, viene diviso in 2 sottogruppi dei quali il elementi, viene diviso in 2 sottogruppi dei quali il primo ha un elemento in meno del secondo.primo ha un elemento in meno del secondo.

Fase 2: imperaFase 2: impera - Supponendo di avere due sequenze già ordinate. Per - Supponendo di avere due sequenze già ordinate. Per

unirle, l'algoritmo merge sort estrae ripetutamente il unirle, l'algoritmo merge sort estrae ripetutamente il minimo delle due sequenze in ingresso e lo pone in minimo delle due sequenze in ingresso e lo pone in una sequenza in uscita.una sequenza in uscita.

Page 16: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Esempio “Merge Sort”Esempio “Merge Sort” void merge (int[] a, int left, int center, int right)void merge (int[] a, int left, int center, int right) int i = left, j=center + 1,k=0; int[] b;int i = left, j=center + 1,k=0; int[] b; while ((i <= center) && (j <= right)) {while ((i <= center) && (j <= right)) { if (a[i] <= a[j]){if (a[i] <= a[j]){ b[k]=a[i];b[k]=a[i]; i=i + 1;i=i + 1; } } else {else { b[k] = a[j];b[k] = a[j]; j=j + 1;j=j + 1; }} k=k + 1;k=k + 1; }} for (k =left ;k<right;k++) {for (k =left ;k<right;k++) { a[k] = b[k - left];a[k] = b[k - left]; }}

void mergesort (int[] a, int left, int right) void mergesort (int[] a, int left, int right) {{int center;int center;if (left < right) {if (left < right) {center = (left + right) / 2;center = (left + right) / 2;mergesort(a, left, center);mergesort(a, left, center);mergesort(a, center+1, right);mergesort(a, center+1, right);merge(a, left, center, right);merge(a, left, center, right);}}

Page 17: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Heap SortHeap Sort L'L'algoritmoalgoritmo che ordina in senso crescente inizia creando uno  che ordina in senso crescente inizia creando uno heapheap

decrescente. Per ogni iterazione si copia la radice (primo elemento decrescente. Per ogni iterazione si copia la radice (primo elemento dell'array) in fondo all'array stesso, eseguendo uno scambio di elementi. dell'array) in fondo all'array stesso, eseguendo uno scambio di elementi. L'algoritmo poi ricostruisce uno heap di   elementi spostando verso il basso L'algoritmo poi ricostruisce uno heap di   elementi spostando verso il basso la nuova radice, e ricomincia con un altro scambio (tra il primo elemento la nuova radice, e ricomincia con un altro scambio (tra il primo elemento dell'array e quello in posizione  ), eseguendo un ciclo che considera array dell'array e quello in posizione  ), eseguendo un ciclo che considera array di dimensione progressivamente decrescente. di dimensione progressivamente decrescente.

Page 18: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Couting SortCouting Sort L'algoritmo conta il numero di occorrenze di ciascun valore L'algoritmo conta il numero di occorrenze di ciascun valore

presente nell'presente nell'arrayarray da ordinare, memorizzando questa  da ordinare, memorizzando questa informazione in un array temporaneo di dimensione pari informazione in un array temporaneo di dimensione pari all'intervallo di valori. Il numero di ripetizioni dei valori all'intervallo di valori. Il numero di ripetizioni dei valori inferiori indica la posizione del valore immediatamente inferiori indica la posizione del valore immediatamente successivo.successivo.

Si calcolano i valori massimo,  , e minimo,  , dell'array e si Si calcolano i valori massimo,  , e minimo,  , dell'array e si prepara un array ausiliario C di dimensione pari all'intervallo prepara un array ausiliario C di dimensione pari all'intervallo dei valori con C[i] che rappresenta la frequenza dell'elemento  dei valori con C[i] che rappresenta la frequenza dell'elemento   nell'array di partenza A. Si visita l'array A aumentando  nell'array di partenza A. Si visita l'array A aumentando l'elemento di C corrispondente. Dopo si visita l'array C in l'elemento di C corrispondente. Dopo si visita l'array C in ordine e si scrivono su A, C[i] copie del valore  .ordine e si scrivono su A, C[i] copie del valore  .

Page 19: CHE COS’è UN ALGORITMO di ORDINAMENTO? Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo.

Bucket SortBucket Sort Il Il Bucket sortBucket sort è un  è un algoritmo di ordinamentoalgoritmo di ordinamento per valori numerici che si  per valori numerici che si

assume siano distribuiti uniformemente in un intervallo semichiuso (0,1). assume siano distribuiti uniformemente in un intervallo semichiuso (0,1). La La complessitàcomplessitàdel bucket sort è lineare O(n+m) (ove m è il valore max del bucket sort è lineare O(n+m) (ove m è il valore max nell'array), questo è possibile in quanto l'algoritmo non è basato su nell'array), questo è possibile in quanto l'algoritmo non è basato su confronti.confronti.

L'intervallo dei valori, noto a priori, è diviso in intervalli più piccoli, L'intervallo dei valori, noto a priori, è diviso in intervalli più piccoli, detti detti bucketbucket (cesto). Ciascun valore dell' (cesto). Ciascun valore dell'arrayarray è quindi inserito nel bucket a  è quindi inserito nel bucket a cui appartiene, i valori all'interno di ogni bucket vengono ordinati e cui appartiene, i valori all'interno di ogni bucket vengono ordinati e l'algoritmo si conclude con la concatenazione dei valori contenuti nei l'algoritmo si conclude con la concatenazione dei valori contenuti nei bucket. bucket.