Algoritmi di ordinamento in C# : Selection sorts

Vediamo come utilizzare l'algorimo Selection Sorts e l'algoritmo Heap Sort. Codici ed esempi.

Nella categoria del tipo selection sorts, abbiamo due algoritmi. Uno si chiama, come la categoria, Selection Sorts, l’altro è l’Heap Sort.

L’algoritmo Selection Sorts

È essenzialmente un algoritmo di confronto. Ha una complessità O(n2) che rende inefficiente l’ordinamento su elenchi di grandi dimensioni ed è generalmente peggiore dell’Insertion Sort e simili. L’algoritmo ha il pregio di essere noto per la sua semplicità e ha anche prestazioni migliori rispetto ad algoritmi complessi in determinate situazioni. L’ordinamento viene eseguito meglio del Bubble Sort in quasi tutti i casi.

Nel migliore dei casi - O(n2)
Caso medio - O(n2)
Caso peggiore - O(n2)
Stabilità - dipende dall’implementazione

private void SelectionSort(long[] inputArray)
{
    long index_of_min = 0;
    for (int iterator = 0; iterator < inputArray.Length - 1; iterator++)
    {
        index_of_min = iterator;
        for (int index = iterator+1; index < inputArray.Length; index++)
        {
            if (inputArray[index] < inputArray[index_of_min])
                index_of_min = index;
        }
        Swap(ref inputArray[iterator], ref inputArray[index_of_min]);
    }
}

Heap Sort

Si tratta di un algoritmo di ordinamento che si basa sul confronto. Anche se un po’ più lento ha una buona implementazione rispetto al Quick Sort e il vantaggio che nel peggiore dei casi ha una complessità n logn. L’Heap Sort è un algoritmo di posto, ma non è un ordinamento stabile. Lavora come suggerisce il suo nome. Si comincia con la costruzione di un gruppo fuori del set di dati, rimuovendo il più grande elemento e inserendolo alla fine in modo da ottenere un array ordinato. Dopo aver rimosso l’elemento più grande, ricostruisce il gruppo, elimina dai rimanenti il valore più grande, e lo pone alla fine dell’array ordinato. Questo si ripete fino a quando non ci sono più elementi nel gruppo e l’array ordinato si è riempito. L’implementazione richiede due array, uno per tenere il gruppo e l’altro per contenere gli elementi ordinati.

L’ Heap Sort inserisce gli elementi della lista di ingresso in una struttura dati detta heap. Il valore più grande (in un max-heap) viene estratto finché non ne rimane più alcun elemento. L’unico costo è quello dell’estrazione.

Nel migliore dei casi - O(n log n)
Caso medio - O(n log n)
Caso peggiore - O (n log n)
Stabilità - instabile

private void HeapSort(long[] inputArray)
{
    for (int index = (inputArray.Length / 2) - 1; index >= 0; index--)
        Heapify(inputArray, index, inputArray.Length);
    for (int index = inputArray.Length - 1; index >= 1; index--)
    {
        SwapWithTemp(ref inputArray[0], ref inputArray[index]);
        Heapify(inputArray, 0, index - 1);
    }
}

La funzione su mostrata richiama la funzione Heapify(), che costruisce una struttura di mucchio di dati utilizzando una delle proprietà dell’heap, che dice che se B è un nodo figlio di A e (A) ≥ (B), ciò implica che un elemento con il più grande valore è sempre il nodo radice (max-heap).

private void Heapify(long[] inputArray, int root, int bottom)
{
    bool completed = false;
    int maxChild;

    while((root*2 <= bottom) && (!completed))
    {
        if (root * 2 == bottom)
            maxChild = root * 2;
        else if (inputArray[root * 2] > inputArray[root * 2 + 1])
            maxChild = root * 2;
        else
            maxChild = root * 2 + 1;
        if (inputArray[root] < inputArray[maxChild])
        {
            SwapWithTemp(ref inputArray[root], ref inputArray[maxChild]);
            root = maxChild;
        }
        else
        {
            completed = true;
        }
    }
}