Counting Sort, e confronto con Quick Sort

Indice

................................................................................................................................................... II…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………&hell

...………………………………………………………………………………….5……………………………………………………………………………….81.2 Grafici risultanti …………………………………………………………………...101.3 Confronto con Quick Sort Counting Sort

Introduzione

Counting Sort è un algoritmo di ordinamento che non si basa sul confronto. Questo cosa comporta? Comporta che per effettuare l’ordinamento, tale algoritmo effettua delle assunzioni sui valori da ordinare;

Infatti esso considera che i valori sono interi e compresi in un intervallo da 0 a k (ovvero sono contenuti in un intervallo limitato).

Come possiamo ordinare gli elementi sapendo che sono interi e compresi in un intervallo limitato? L'idea è quella di fare praticamente 3 operazioni:

1. Per prima cosa, contiamo le occorrenze del vettore da ordinare, ovvero contiamo quanti elementi pari ad i ci sono nel vettore da ordinare.
2. Successivamente, possiamo fare un ulteriore elaborazione per individuare quanti elementi minori o uguali ad i ci sono nel vettore da ordinare.
3. Infine, attraverso quest'ultima informazione possiamo ricavare in che posizione deve essere ciascun elemento.

Quest'algoritmo non ordina sul posto: abbiamo bisogno di mantenere un vettore parialla lunghezza del vettore da ordinare che rappresenterà il vettore ordinato, un vettore che servirà a mantenere il numero di occorrenze dei valori ammessi e il vettore di partenza, per un totale di 3 vettori.

1. Capitolo 1: Analisi dei tempi di esecuzione

Per completezza, riportiamo lo pseudo-codice che descrive l'algoritmo in questione:

dall'ultimo elemento nel riempimento di B? Che differenza c'è

Perché partiamo primo all'ultimo o viceversa?

Nel procedere dal

In realtà non c'è una differenza in termini di complessità: se i valori sono semplici

La differenza non c'è per nulla.

Elementi non strutturati,

Se i valori non fossero dati semplici, ma dati strutturati, il campo che noi è una chiave che rappresenta quell'elemento

Visualizziamo: questa è una proprietà chiamata "proprietà: dati due o più

Degli algoritmi di ordinamento di stabilità"

Elementi uguali nel vettore da ordinare, questi elementi si trovano nella stessa

Posizione relativa tra di loro.

4. Volendo andare ad effettuare l'analisi dei tempi di esecuzione di tale algoritmo, andiamo ad analizzare lo pseudo

codice : in esso, andiamo ad effettuare esattamente 4 cicli for :

• il primo, viene ripetuto k+1 volte
• il secondo, viene ripetuto n volte
• il terzo, viene ripetuto k volte
• il quarto, viene ripetuto n volte

Di conseguenza abbiamo che, i tempi di esecuzione del nostro algoritmo dipendono da due fattori, kϴ(k+n).

ed e, più in particolare, risultano essere un

Possiamo distinguere, però due casi differenti :

1. ϴ(n),1) k<n , abbiamo che n domina su k e di conseguenza otteniamo un il che significa che il tempo di esecuzione del nostro algoritmo è lineare rispetto alle dimensioni della sequenza da ordinare.
2. ϴ(k),2) k>n , abbiamo che k domina su n e di conseguenza otteniamo un il che significa che il tempo di esecuzione del nostro algoritmo non dipende dalle dimensioni della sequenza da ordinare.

In quest’elaborato sono stati allora implementati entrambi i casi. Counting Sort è stato implementato attraverso il linguaggio Java : sono stati testati vettori

La dimensione varia da un minimo di 100 ad un massimo di 100000 e per ognuno di essi sono state effettuate 100 misurazioni differenti, in cui i tempi di esecuzione sono stati mediati per ottenere dei valori più realistici.

Alla fine dell'esecuzione, questi valori vengono salvati in due file differenti, uno per ogni caso, in modo da poter essere esportati su strumenti come Matlab.

Considerando il primo caso, k<n, sono stati inseriti valori di k che variano tra 0 e 99, essendo la dimensione minima del vettore pari a 100; infatti in questo modo risulta essere sempre verificato che k<n.

Considerando il secondo caso, k>n, invece, ogni volta il valore di k viene scelto in un intervallo (0,2n) e per questo ad ogni iterazione abbiamo sempre la nostra ipotesi verificata.

1.1 Codice Java

Codice Counting Sort : 5

Codice Java per caso k<n : 6

Codice Java per caso k>n : 7

1.2 Grafici risultanti

Si può ben vedere come il caso in cui k<n (blu), risulta avere tempi

decisamente inferiori rispetto al caso in cui k>n (rosso).

Considerando il caso in cui k<n, l’andamento è approssimabile con la seguente retta: ϴ(n),

Poiché abbiamo detto che, in questo caso il tempo di esecuzione è un allora possiamo scrivere che:

Risolvendo queste due disequazioni, si ottiene che:

Per questo motivo sono stati scelti, c = 2.5, c = 0.1 e n = 442.2 1 0

Possiamo vedere come il nostro tempo di esecuzione (retta blu) è compreso tra due rette, calcolate nel modo appena descritto.