Ordinare un vettore significa disporre i suoi elementi secondo un criterio, per esempio in ordine crescente. Confrontiamo tre algoritmi classici presenti in Fondamenti di programmazione 1: Bubble Sort, Selection Sort e Insertion Sort. Tutti gli esempi seguenti sono in C#.

1. Bubble Sort: scambi tra vicini

In ogni passata si confrontano elementi adiacenti e si scambiano quando sono nell’ordine sbagliato. Al termine di una passata, il massimo della parte ancora da ordinare si trova nella posizione finale.

int[] v = { 5, 2, 4, 1 };
for (int fine = v.Length - 1; fine > 0; fine--)
{
    bool scambiato = false;
    for (int i = 0; i < fine; i++)
    {
        if (v[i] > v[i + 1])
        {
            int tmp = v[i];
            v[i] = v[i + 1];
            v[i + 1] = tmp;
            scambiato = true;
        }
    }
    if (!scambiato) break;
}
Console.WriteLine(string.Join(", ", v)); // 1, 2, 4, 5

2. Selection Sort: selezionare il minimo

Si cerca il valore più piccolo nella parte non ordinata, poi lo si scambia con il primo elemento della stessa parte. Dopo la prima passata il minimo è definitivamente al suo posto.

int[] v = { 5, 2, 4, 1 };
for (int i = 0; i < v.Length - 1; i++)
{
    int indiceMin = i;
    for (int j = i + 1; j < v.Length; j++)
    {
        if (v[j] < v[indiceMin]) indiceMin = j;
    }
    int tmp = v[i];
    v[i] = v[indiceMin];
    v[indiceMin] = tmp;
}
Console.WriteLine(string.Join(", ", v));

3. Insertion Sort: inserire nella posizione giusta

Si assume ordinata la parte sinistra del vettore; l’elemento corrente viene inserito nella posizione corretta spostando verso destra gli elementi più grandi.

int[] v = { 5, 2, 4, 1 };
for (int i = 1; i < v.Length; i++)
{
    int chiave = v[i];
    int j = i - 1;
    while (j >= 0 && v[j] > chiave)
    {
        v[j + 1] = v[j];
        j--;
    }
    v[j + 1] = chiave;
}
Console.WriteLine(string.Join(", ", v));

Confronto degli algoritmi

Con una versione di Bubble Sort che interrompe l’esecuzione quando non ci sono scambi, un vettore già ordinato viene riconosciuto in una passata. Insertion Sort è efficiente sui dati quasi ordinati; Selection Sort effettua pochi scambi. La scelta dipende dal contesto.

Traccia manuale

Parti da [5, 2, 4, 1]. Nel Bubble Sort, dopo la prima passata si ottiene [2, 4, 1, 5]: l’ultimo valore è già definitivo. Completa le passate successive su carta prima di eseguire il codice.

Esercizi

• Traccia le prime due passate di Bubble Sort su [7, 1, 5, 2].
• Modifica Selection Sort per l’ordine decrescente.
• Verifica Insertion Sort su un vettore già ordinato e su uno in ordine inverso.
• Spiega perché non basta scambiare due valori senza una variabile temporanea o una strategia equivalente.

Nel percorso: ← Vettori · Indice del corso · Ricerca →