counting sort

Counting Sort

Cos'è Counting Sort?

Counting Sort è un algoritmo di ordinamento non comparativo che ordina un insieme di oggetti secondo un valore numerico chiave. Si caratterizza per la sua efficienza in determinate situazioni, in particolare quando gli elementi dell'array hanno un range limitato.

Funzionamento di Counting Sort

Counting Sort funziona contando il numero di occorrenze di ciascun elemento e utilizzando queste informazioni per posizionare correttamente gli elementi nell'array ordinato. Si crea un array di conteggio che tiene traccia del numero di occorrenze di ciascun elemento.

Esempio pratico:

Supponiamo di avere l'array seguente da ordinare utilizzando Counting Sort: [4,2,2,8,3,3,1] Passo 1: inizialmente troveremo il numero massimo e il numero minimo all'interno dell'array [1,8] Passo 2: Inizializzazione dell'Array di Conteggio Iniziamo creando un array di conteggio per tenere traccia del numero di occorrenze di ciascun elemento nell'array originale. Per questo esempio, consideriamo che il range dei numeri sia compreso tra il minimo e il massimo: count=[0,0,0,0,0,0,0,0] Passo 3: Conteggio delle Occorrenze Scorriamo l'array originale e incrementiamo il contatore corrispondente per ciascun elemento: count=[1,2,2,1,0,0,0,1] Passo 4: Costruzione dell'Array Ordinato Ora, utilizziamo l'array di conteggio per ricostruire l'array ordinato. Scorriamo l'array di conteggio e posizioniamo gli elementi nell'array ordinato: sorted=[1,2,2,3,3,4,8] Passo 5: Output L'array ordinato ottenuto utilizzando Counting Sort è: [1,2,2,3,3,4,8]

Programma in C

#include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { int ArrA[1000], ArrC[1000] = {0}; int max = 0, min = 10000, i, j, count = 0, x = 0; printf("Inserisci 10 elementi: "); for (i = 0; i < 10; i++) { scanf("%d", &ArrA[i]); if (ArrA[i] > max) { max = ArrA[i]; } if (ArrA[i] < min) { min = ArrA[i]; } } printf("L'intervallo e'[%d , %d]\n", min, max); for (i = min; i <= max; i++) { count = 0; for (j = 0; j < 10; j++) { if (ArrA[j] == i) { count++; } } ArrC[x] = count; x++; } for (i = min; i <= max; i++) { if (ArrC[i-min] != 0) { for (j = 0; j < ArrC[i-min]; j++) { printf("%d ", i); } } } return (EXIT_SUCCESS); }