Redazione
a- a+

Algoritmi di ordinamento in C# : Exchange Sort

Analizziamo l'algoritmo di ordinamento Exchange Sort. Codici ed esempi.

L’ordinamento in informatica è sicuramente una delle funzionalità più necessarie e importanti, questi algoritmi sono suddivisi in due grandi categorie: quelli basati sul confronto e quelli basati sul non-confronto.

Nella categoria basata sul confronto abbiamo diverse sottocategorie:

Il primo passo è quello di creare un set di dati campione (una matrice, nel nostro caso) con il quale testare i vari algoritmi che andremo a implementare in C#:

long[] inputArray = new long[1000];
Random rnd = new Random();
for (int i = 0; i < inputArray.Length; i++)
{
    inputArray[i] = rnd.Next();
}
private void Swap(ref long valOne, ref long valTwo)
{
    valOne = valOne + valTwo;
    valTwo = valOne - valTwo;
    valOne = valOne - valTwo;
}
private void SwapWithTemp(ref long valOne, ref long valTwo)
{
    long temp = valOne;
    valOne = valTwo;
    valTwo = temp;
}

Quello che abbiamo scritto è un codice di esempio di dati campioni creati in modo random. In quest’articolo prenderemo in considerazione la sottocategoria Exchange sorts. In questa sottocategoria i due algoritmi più comunemente utilizzati sono il -Bubble Sort- e il più veloce -Quick Sort-.

Il Bubble Sort è un algoritmo iterativo di ordinamento degli elementi di un array molto usato soprattutto in ambito didattico, per fare apprendere le logiche e le basi della programmazione. Il suo nome deriva dal fatto che gli elementi vengono ordinati secondo una logica che li estrae dall’insieme mettendoli in cima al vettore con un’analogia grafica come quella delle bollicine che salgono in un bicchiere di spumante. Dato un numero n di elementi di qualsiasi tipo, ma tali che esista una relazione di ordinamento tra di loro, l’algoritmo del bubble sort consente di ordinarli in modo crescente o decrescente. Del bubble sort solitamente vi sono svariati esempi la nostra è una versione implementata in C#.  L’algoritmo inizia dall’inizio del set di dati. Mette a confronto i primi due elementi e se il primo è maggiore del secondo li scambia. Si continua a fare questo per ogni coppia di elementi adiacenti fino alla fine del set di dati. Finita l’iterazione si ricomincia con i primi due elementi, ripetendo fino a quando non si verifica più alcun “swap”. Questo algoritmo è altamente inefficiente ed è raramente utilizzato.

  • Miglior caso - O(n)
  • Caso medio - O(n2)
  • Peggior caso - O(n2)
  • Stabilità - stabile
private void BubbleSort(long[] inputArray)
{
    for (int iterazione = 0; iterazione < inputArray.Length; iterazione++)
    {
        for (int index = 0; index < inputArray.Length - 1; index++)
        {
            if (inputArray[index] > inputArray[index + 1])
            {
                Swap(ref inputArray[index], ref inputArray[index+1]);
            }
        }
    }
}

Il secondo algoritmo di questa sottocategoria è il “Quick Sort” o ordinamento veloce. Si tratta di un algoritmo divide et impera che si basa su un’operazione di partizione, cioè partizionare un array, scegliere un elemento chiamato pivot, spostare tutti gli elementi più piccoli davanti al pivot, e spostare tutti gli elementi più grandi dopo il pivot. Questo può essere fatto in modo efficiente in tempo lineare e quasi istantaneamente. Successivamente e in modo ricorsivo si passa a ordinare le sottoliste degli elementi minori e maggiori del pivot.

  • Miglior caso - O(n log n)
  • Caso medio - O(n log n)
  • Peggior caso - O(n2)
  • Stabilità – dipende dalla scelta del pivot
private void QuickSort(long[] inputArray)
{
    int left = 0;
    int right = inputArray.Length - 1;
    InternalQuickSort(inputArray, left, right);
}

<summary>
// Algoritmo di ordinamento ricorsivo basato sul quick sort
// usando il divide et impera. L’ordinamento è basato sull’elemento pivot
</summary>
<param name="inputArray"></param>
<param name="left"></param>
<param name="right"></param>
private void InternalQuickSort(long[] inputArray, int left, int right)
{
    int pivotNewIndex = Partition(inputArray, left, right);
    long pivot = inputArray[(left + right) / 2];
    if (left < pivotNewIndex-1)
        InternalQuickSort(inputArray, left, pivotNewIndex - 1);
    if (pivotNewIndex < right)
        InternalQuickSort(inputArray, pivotNewIndex, right);
}

//Questa operazione ritorna un nuovo pivot ognivolta che viene chiamata //ricorsivamente ed effettua uno swap degli elementi dell’array basandosi su //confronto con il valore del pivot
private int Partition(long[] inputArray, int left, int right)
{
    int i = left, j = right;
    long pivot = inputArray[(left + right) / 2];

    while (i <= j)
    {
        while (inputArray[i] < pivot)
            i++;
        while (inputArray[j] < pivot)
            j--;
        if (i <= j)
        {
            SwapWithTemp(ref inputArray[i], ref inputArray[j]);
            i++; j--;
        }
    }
    return i;
}



Ti potrebbe interessare anche

commenta la notizia

C'è 1 commento
Lorenzo
Hai qualche domanda da fare?