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à