Algoritmi di Ordinamento

Panoramica degli Algoritmi

Algoritmo	Caso Medio	Caso Peggiore	Spazio	Stabile	Note
Bubble Sort	O(n²)	O(n²)	O(1)	Sì	Semplice, lento
Selection Sort	O(n²)	O(n²)	O(1)	No	Minimo n swap
Insertion Sort	O(n²)	O(n²)	O(1)	Sì	Ottimo per array quasi ordinati
Merge Sort	O(n log n)	O(n log n)	O(n)	Sì	Stabile, predicibile
Quick Sort	O(n log n)	O(n²)	O(log n)	No	Il più veloce in pratica
Counting Sort	O(n+k)	O(n+k)	O(k)	Sì	Solo interi in range piccolo
qsort (stdlib)	O(n log n)	—	—	No	Usa in produzione!

Regola pratica Per uso quotidiano usa sempre qsort() in C o std::sort() in C++. Studia gli altri algoritmi per capire la logica e prepararti ai colloqui tecnici.

1. Bubble Sort

Confronta coppie adiacenti e le scambia se sono nell'ordine sbagliato. Gli elementi "grandi" risalgono come bolle. Ad ogni passata, il massimo raggiunge la posizione corretta.

CBubble Sort — con ottimizzazione early exit

#include <stdio.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int scambiato = 0;  // Ottimizzazione: se nessuno scambio, già ordinato

        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                scambiato = 1;
            }
        }

        if (!scambiato) break;  // Array già ordinato → O(n) nel caso migliore
    }
}

// Versione generica con puntatore a funzione di confronto
void bubble_sort_gen(void *arr, int n, size_t elem_size,
                     int (*cmp)(const void*, const void*)) {
    char *a = arr;
    char tmp[elem_size];
    for (int i=0; i<n-1; i++)
        for (int j=0; j<n-i-1; j++)
            if (cmp(a+j*elem_size, a+(j+1)*elem_size) > 0) {
                memcpy(tmp,               a+j*elem_size,     elem_size);
                memcpy(a+j*elem_size,     a+(j+1)*elem_size, elem_size);
                memcpy(a+(j+1)*elem_size, tmp,               elem_size);
            }
}

void stampa(int arr[], int n) {
    for (int i=0; i<n; i++) printf("%3d", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = 7;

    printf("Prima:  "); stampa(arr, n);

    // Mostra ogni passata
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) { int t=arr[j]; arr[j]=arr[j+1]; arr[j+1]=t; }
        printf("Pass %d: ", i+1); stampa(arr, n);
    }
    return 0;
}

Output

Prima:   64 34 25 12 22 11 90
Pass 1:  34 25 12 22 11 64 90
Pass 2:  25 12 22 11 34 64 90
Pass 3:  12 22 11 25 34 64 90
Pass 4:  12 11 22 25 34 64 90
Pass 5:  11 12 22 25 34 64 90
Pass 6:  11 12 22 25 34 64 90

2. Selection Sort

Ad ogni passata, trova il minimo nella parte non ordinata e lo mette in posizione. Effettua esattamente n-1 swap (il minimo tra tutti i sort).

CSelection Sort

#include <stdio.h>

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        // Trova il minimo nella parte non ordinata [i, n-1]
        int idx_min = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[idx_min]) idx_min = j;
        }

        // Scambia il minimo con il primo elemento non ordinato
        if (idx_min != i) {
            int tmp = arr[i];
            arr[i] = arr[idx_min];
            arr[idx_min] = tmp;
        }
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = 5;

    printf("Prima: ");
    for(int i=0;i<n;i++) printf("%d ", arr[i]);
    printf("\n");

    for (int i = 0; i < n-1; i++) {
        int idx_min = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[idx_min]) idx_min = j;

        if (idx_min != i) {
            printf("Swap arr[%d]=%d con arr[%d]=%d\n", i, arr[i], idx_min, arr[idx_min]);
            int tmp = arr[i]; arr[i] = arr[idx_min]; arr[idx_min] = tmp;
        }
    }

    printf("Dopo: ");
    for(int i=0;i<n;i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

3. Insertion Sort

Come ordinare le carte da gioco: prendi ogni carta e inseriscila nella posizione giusta. Ottimale per array piccoli o quasi ordinati (O(n) nel caso migliore).

CInsertion Sort

#include <stdio.h>

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int chiave = arr[i];  // L'elemento da inserire
        int j = i - 1;

        // Sposta gli elementi maggiori di "chiave" di una posizione a destra
        while (j >= 0 && arr[j] > chiave) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = chiave;  // Inserisce "chiave" nella posizione corretta
    }
}

// Insertion sort con ricerca binaria per trovare la posizione (O(n log n) confronti, O(n²) spostamenti)
int binary_search_pos(int arr[], int chiave, int sx, int dx) {
    while (sx <= dx) {
        int mid = (sx+dx)/2;
        if (arr[mid] == chiave) return mid+1;
        if (arr[mid] < chiave) sx = mid+1;
        else dx = mid-1;
    }
    return sx;
}

void insertion_sort_binary(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int chiave = arr[i];
        int pos = binary_search_pos(arr, chiave, 0, i-1);
        for (int j = i; j > pos; j--) arr[j] = arr[j-1];
        arr[pos] = chiave;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = 5;

    printf("Prima: ");
    for(int i=0;i<n;i++) printf("%d ",arr[i]);

    insertion_sort(arr, n);

    printf("\nDopo:  ");
    for(int i=0;i<n;i++) printf("%d ",arr[i]);
    printf("\n");
    return 0;
}

4. Merge Sort — Divide et Impera

Divide l'array a metà ricorsivamente, poi unisce le metà ordinate. Garantisce O(n log n) in tutti i casi. Ideale per dati su disco o linked list.

CMerge Sort completo

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void merge(int arr[], int sx, int mid, int dx) {
    int n1 = mid - sx + 1;
    int n2 = dx - mid;

    int *L = malloc(n1 * sizeof(int));
    int *R = malloc(n2 * sizeof(int));

    // Copia nelle metà temporanee
    memcpy(L, arr + sx,     n1 * sizeof(int));
    memcpy(R, arr + mid + 1, n2 * sizeof(int));

    // Unisci le due metà ordinate
    int i = 0, j = 0, k = sx;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else               arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
}

void merge_sort(int arr[], int sx, int dx) {
    if (sx < dx) {
        int mid = sx + (dx - sx) / 2;  // Evita overflow rispetto a (sx+dx)/2
        merge_sort(arr, sx, mid);       // Ordina metà sinistra
        merge_sort(arr, mid+1, dx);     // Ordina metà destra
        merge(arr, sx, mid, dx);        // Unisci
    }
}

// Versione bottom-up (iterativa, evita la recursione)
void merge_sort_iter(int arr[], int n) {
    for (int size = 1; size < n; size *= 2) {
        for (int sx = 0; sx < n-1; sx += 2*size) {
            int mid = sx + size - 1;
            int dx  = (sx + 2*size - 1 < n-1) ? sx + 2*size - 1 : n-1;
            if (mid < dx) merge(arr, sx, mid, dx);
        }
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = 7;

    printf("Prima: ");
    for(int i=0;i<n;i++) printf("%d ",arr[i]);

    merge_sort(arr, 0, n-1);

    printf("\nDopo:  ");
    for(int i=0;i<n;i++) printf("%d ",arr[i]);
    printf("\n");
    return 0;
}

5. Quick Sort

Sceglie un pivot, sposta tutti gli elementi minori a sinistra e maggiori a destra, poi ordina ricorsivamente le due partizioni. In pratica è il più veloce, ma ha caso peggiore O(n²) con pivot scelto male.

CQuick Sort con pivot mediana-di-tre

#include <stdio.h>
#include <stdlib.h>

void scambia(int *a, int *b) { int t = *a; *a = *b; *b = t; }

// Sceglie il pivot come mediana tra primo, medio e ultimo elemento
int mediana_tre(int arr[], int sx, int dx) {
    int mid = sx + (dx - sx) / 2;
    if (arr[sx] > arr[mid])  scambia(&arr[sx], &arr[mid]);
    if (arr[sx] > arr[dx])   scambia(&arr[sx], &arr[dx]);
    if (arr[mid] > arr[dx])  scambia(&arr[mid], &arr[dx]);
    // Ora arr[sx] <= arr[mid] <= arr[dx]
    // Metti il pivot a destra-1 per la partizione
    scambia(&arr[mid], &arr[dx-1]);
    return arr[dx-1];  // Il pivot
}

int partition(int arr[], int sx, int dx) {
    int pivot = arr[dx];   // Pivot all'ultimo (versione semplice)
    int i = sx - 1;

    for (int j = sx; j < dx; j++) {
        if (arr[j] <= pivot) {
            i++;
            scambia(&arr[i], &arr[j]);
        }
    }
    scambia(&arr[i+1], &arr[dx]);
    return i + 1;  // Posizione finale del pivot
}

void quick_sort(int arr[], int sx, int dx) {
    if (sx < dx) {
        int p = partition(arr, sx, dx);
        quick_sort(arr, sx, p-1);   // Partizione sinistra
        quick_sort(arr, p+1, dx);   // Partizione destra
    }
}

// Quick Sort randomizzato (evita il caso peggiore O(n²))
void quick_sort_rand(int arr[], int sx, int dx) {
    if (sx < dx) {
        // Scegli pivot a caso e mettilo alla fine
        int idx = sx + rand() % (dx - sx + 1);
        scambia(&arr[idx], &arr[dx]);
        int p = partition(arr, sx, dx);
        quick_sort_rand(arr, sx, p-1);
        quick_sort_rand(arr, p+1, dx);
    }
}

int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = 7;

    printf("Prima: ");
    for(int i=0;i<n;i++) printf("%d ",arr[i]);

    quick_sort(arr, 0, n-1);

    printf("\nDopo:  ");
    for(int i=0;i<n;i++) printf("%d ",arr[i]);
    printf("\n");
    return 0;
}

6. Counting Sort — O(n+k)

Conta le occorrenze di ogni valore. Funziona solo con interi in un range noto. Più veloce di O(n log n) quando il range k è piccolo.

CCounting Sort

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void counting_sort(int arr[], int n, int max_val) {
    int *contatore = calloc(max_val + 1, sizeof(int));
    int *output    = malloc(n * sizeof(int));

    // Fase 1: conta le occorrenze
    for (int i = 0; i < n; i++) contatore[arr[i]]++;

    // Fase 2: accumula (rende contatore[i] = quanti elem <= i)
    for (int i = 1; i <= max_val; i++) contatore[i] += contatore[i-1];

    // Fase 3: costruisce l'output (da destra per mantenere la stabilità)
    for (int i = n-1; i >= 0; i--) {
        output[--contatore[arr[i]]] = arr[i];
    }

    // Copia il risultato
    memcpy(arr, output, n * sizeof(int));

    free(contatore);
    free(output);
}

// Radix Sort usando counting sort come subroutine
void counting_sort_exp(int arr[], int n, int exp) {
    int output[n], contatore[10] = {0};
    for (int i=0; i<n; i++) contatore[(arr[i]/exp)%10]++;
    for (int i=1; i<10; i++) contatore[i]+=contatore[i-1];
    for (int i=n-1; i>=0; i--) output[--contatore[(arr[i]/exp)%10]]=arr[i];
    memcpy(arr, output, n*sizeof(int));
}

void radix_sort(int arr[], int n) {
    int max = arr[0];
    for (int i=1; i<n; i++) if (arr[i]>max) max=arr[i];
    for (int exp=1; max/exp>0; exp*=10)
        counting_sort_exp(arr, n, exp);
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1, 9, 5};
    int n = 9;
    printf("Prima: "); for(int i=0;i<n;i++) printf("%d ",arr[i]);
    counting_sort(arr, n, 9);
    printf("\nDopo:  "); for(int i=0;i<n;i++) printf("%d ",arr[i]);

    int arr2[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n2 = 8;
    printf("\n\nRadix Sort:\n");
    printf("Prima: "); for(int i=0;i<n2;i++) printf("%d ",arr2[i]);
    radix_sort(arr2, n2);
    printf("\nDopo:  "); for(int i=0;i<n2;i++) printf("%d ",arr2[i]);
    printf("\n");
    return 0;
}

7. qsort — La Funzione Standard

In produzione, usa sempre qsort() dalla stdlib: è ottimizzata e testata.

Cqsort — uso pratico

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Comparatori per qsort
int cmp_int_asc(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}
int cmp_int_desc(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}
int cmp_str(const void *a, const void *b) {
    return strcmp(*(char**)a, *(char**)b);
}

typedef struct {
    char nome[30];
    int  eta;
    double stipendio;
} Persona;

int cmp_persona_eta(const void *a, const void *b) {
    return ((Persona*)a)->eta - ((Persona*)b)->eta;
}
int cmp_persona_stipendio(const void *a, const void *b) {
    double diff = ((Persona*)b)->stipendio - ((Persona*)a)->stipendio;
    return (diff > 0) ? 1 : (diff < 0 ? -1 : 0);
}

int main() {
    int numeri[] = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    int n = 9;

    qsort(numeri, n, sizeof(int), cmp_int_asc);
    printf("Crescente: "); for(int i=0;i<n;i++) printf("%d ",numeri[i]);

    qsort(numeri, n, sizeof(int), cmp_int_desc);
    printf("\nDecrescente:"); for(int i=0;i<n;i++) printf("%d ",numeri[i]);

    char *parole[] = {"banana", "apple", "cherry", "date", "elderberry"};
    qsort(parole, 5, sizeof(char*), cmp_str);
    printf("\n\nParole ordinate: ");
    for(int i=0;i<5;i++) printf("%s ", parole[i]);

    Persona persone[] = {
        {"Mario", 35, 2500}, {"Anna", 28, 3200}, {"Luca", 42, 1800}
    };
    qsort(persone, 3, sizeof(Persona), cmp_persona_eta);
    printf("\n\nOrdinati per età:\n");
    for(int i=0;i<3;i++)
        printf("  %s (%d anni, %.0f€)\n", persone[i].nome, persone[i].eta, persone[i].stipendio);

    return 0;
}

🏋️ Esercizi

Implementa e usa gli algoritmi di ordinamento.

Ordina per criteri multipli

Facileqsort

Crea un array di struct Studente (nome, voto, età). Ordinalo tre volte usando qsort con comparatori diversi: per voto decrescente, poi per nome alfabetico, poi per età crescente. Stampa il risultato dopo ogni ordinamento.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct { char nome[30]; int voto, eta; } Studente;

int cmp_voto(const void *a, const void *b) { return ((Studente*)b)->voto - ((Studente*)a)->voto; }
int cmp_nome(const void *a, const void *b) { return strcmp(((Studente*)a)->nome, ((Studente*)b)->nome); }
int cmp_eta(const void *a, const void *b)  { return ((Studente*)a)->eta - ((Studente*)b)->eta; }

void stampa(Studente arr[], int n) {
    for(int i=0;i<n;i++)
        printf("  %-15s voto=%d eta=%d\n", arr[i].nome, arr[i].voto, arr[i].eta);
}

int main() {
    Studente s[] = {
        {"Marco",  28, 21}, {"Anna", 30, 19}, {"Giulia", 25, 22},
        {"Luca",   28, 20}, {"Sara", 30, 23}
    };
    int n = 5;

    printf("Per voto (desc):\n"); qsort(s,n,sizeof(Studente),cmp_voto); stampa(s,n);
    printf("\nPer nome:\n");       qsort(s,n,sizeof(Studente),cmp_nome); stampa(s,n);
    printf("\nPer eta:\n");        qsort(s,n,sizeof(Studente),cmp_eta);  stampa(s,n);
    return 0;
}

Implementa Merge Sort su stringhe

MedioMerge Sort

Adatta il Merge Sort per ordinare un array di stringhe in ordine alfabetico. Poi ordina per lunghezza crescente (e a parità di lunghezza, alfabeticamente). Testa con 10+ parole.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void merge_str(char **arr, int sx, int mid, int dx) {
    int n1=mid-sx+1, n2=dx-mid;
    char **L=malloc(n1*sizeof(char*)), **R=malloc(n2*sizeof(char*));
    for(int i=0;i<n1;i++) L[i]=arr[sx+i];
    for(int j=0;j<n2;j++) R[j]=arr[mid+1+j];
    int i=0,j=0,k=sx;
    while(i<n1&&j<n2) {
        int cmp = strlen(L[i])!=strlen(R[j])
            ? (int)strlen(L[i])-(int)strlen(R[j])
            : strcmp(L[i],R[j]);
        arr[k++] = (cmp<=0) ? L[i++] : R[j++];
    }
    while(i<n1) arr[k++]=L[i++];
    while(j<n2) arr[k++]=R[j++];
    free(L); free(R);
}

void merge_sort_str(char **arr, int sx, int dx) {
    if(sx<dx){int m=(sx+dx)/2; merge_sort_str(arr,sx,m); merge_sort_str(arr,m+1,dx); merge_str(arr,sx,m,dx);}
}

int main() {
    char *parole[] = {"banana","kiwi","apple","fig","cherry","date","elderberry","grape","lemon","mango"};
    int n=10;
    merge_sort_str(parole,0,n-1);
    for(int i=0;i<n;i++) printf("%-15s (%zu)\n", parole[i], strlen(parole[i]));
    return 0;
}

K-esimo elemento più piccolo

DifficileQuickSelect

Implementa l'algoritmo QuickSelect per trovare il k-esimo elemento più piccolo di un array in O(n) medio senza ordinare tutto. È come Quick Sort ma esplora solo la partizione che contiene k. Testa con k=1 (minimo), k=n (massimo), k=n/2 (mediana).

Dopo la partizione, se il pivot è in posizione p: se p==k restituisci arr[p]; se p>k ricerca in [sx, p-1]; altrimenti in [p+1, dx].

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void scambia(int *a, int *b) { int t=*a; *a=*b; *b=t; }

int partition(int arr[], int sx, int dx) {
    int pivot = arr[dx], i = sx-1;
    for(int j=sx;j<dx;j++) if(arr[j]<=pivot) scambia(&arr[++i],&arr[j]);
    scambia(&arr[i+1],&arr[dx]);
    return i+1;
}

// QuickSelect: trova il k-esimo più piccolo (0-indexed)
int quickselect(int arr[], int sx, int dx, int k) {
    if (sx == dx) return arr[sx];
    // Pivot casuale
    int idx = sx + rand()%(dx-sx+1);
    scambia(&arr[idx], &arr[dx]);
    int p = partition(arr, sx, dx);
    if (p == k)   return arr[p];
    if (p > k)    return quickselect(arr, sx, p-1, k);
    return quickselect(arr, p+1, dx, k);
}

int main() {
    srand(42);
    int arr[] = {7, 10, 4, 3, 20, 15, 1, 8, 12, 5};
    int n = 10;

    printf("Array: ");
    for(int i=0;i<n;i++) printf("%d ",arr[i]);
    printf("\n");

    int test[] = {1, 3, 5, 10};  // 1°, 3°, 5°, 10° più piccolo
    for(int i=0;i<4;i++) {
        int tmp[10];
        for(int j=0;j<n;j++) tmp[j]=arr[j];
        int k = test[i];
        int risultato = quickselect(tmp, 0, n-1, k-1);
        printf("%d° più piccolo: %d\n", k, risultato);
    }
    return 0;
}