• Programmazione » ASP.NET » Tutorial ASP.NET

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;  elsemaxChild = root * 2 + 1;  if (inputArray[root] < inputArray[maxChild])  {SwapWithTemp(ref inputArray[root], ref inputArray[maxChild]);root = maxChild;  }  else  {completed = true;  }    }}