Counting Sort, e confronto con Quick Sort

Scuola Politecnica e delle Scienze di Base

Corso di Laurea Magistrale in Ingegneria Informatica

Elaborato di

Algoritmi e Strutture Dati:

Counting Sort

Anno Accademico 2020/2021

Martina Russo

matr. M63001128

Indice

Indice ................................................................................................................................................... II

………………………………………………………………………………………….3

Introduzione

Capitolo 1 : Analisi dei tempi di esecuzione…………………………………………………………4

1.1 Codice Java ...………………………………………………………………………………….5

……………………………………………………………………………….8

1.2 Grafici risultanti …………………………………………………………………...10

1.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 :

- per prima cosa, contiamo le occorrenze del vettore da ordinare , ovvero contiamo

quanti elementi pari ad i ci sono nel vettore da ordinare

- successivamente, possiamo fare un ulteriore elaborazione per individuare quanti

elementi minori o uguali ad i ci sono nel vettore da ordinare

- 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 pari

alla lunghezza del vettore da ordinare che rappresenterà il vettore ordinato, un vettore

che servirà