Redazione
a- a+

Algoritmi di ordinamento in C#: Insertion Sort

Vediamo come utilizzare l'algorimo Insertion Sorts e l'algoritmo Shell Sort. Codici ed esempi.

La categoria Insertion Sort contiene due algoritmi di ordinamento: l’Insertion Sort e lo Shell Sort.

Insertion Sort

Si tratta di un algoritmo di ordinamento semplice che è relativamente efficiente per liste piccole e soprattutto liste ordinate, e spesso viene utilizzato come parte di algoritmi più sofisticati. Funziona prendendo elementi dalla lista uno per uno e inserendoli nella loro corretta posizione in una nuova lista ordinata.

Shell Sort è una variante di Insertion Sort, più efficiente per liste grandi. L’inserimento è costoso e richiede lo spostamento di tutti gli elementi più uno.

  • Nel migliore dei casi - O(n)
  • Caso medio - O(n2)
  • Caso peggiore - O(n2)
  • Stabilità - stabile
private void InsertionSort(long[] inputArray)
{
    long j = 0 ;
    long temp = 0 ;
    for (int index = 1; index < inputArray.Length; index++)
    {
        j = index;
        temp = inputArray[index];
        while ((j > 0) && (inputArray[j - 1] > temp))
        {
            inputArray[j] = inputArray[j - 1];
            j = j - 1;
        }
        inputArray[j] = temp;
    }
}

Shell Sort

Migliora il Bubble Sort e l’Insertion Sort spostando fuori elementi per più di una posizione alla volta. Lo Shell Sort è una estensione dell’Insertion Sort, tenendo presenti due osservazioni:

1.     L’Insertion Sort è efficiente se l’input è già abbastanza ordinato.

2.     L’Insertion Sort è inefficiente, generalmente, in quanto muove i valori di una sola posizione per volta.

Lo Shell sort è simile all’Insertion Sort, ma funziona spostando i valori di più posizioni per volta man mano che risistema i valori, diminuendo gradualmente la dimensione del passo sino ad arrivare a uno. Alla fine, lo Shell Sort esegue un Insertion Sort, ma per allora i dati saranno già piuttosto ordinati. Consideriamo un valore piccolo posizionato inizialmente all’estremità errata di un array dati di lunghezza n. Usando l’Insertion Sort, ci vorranno circa n confronti e scambi per spostare questo valore lungo tutto l’array fino all’altra estremità. Con lo Shell Sort, si muoveranno i valori usando passi di grosse dimensioni, cosicché un valore piccolo andrà velocemente nella sua posizione finale con pochi confronti e scambi.

  • Nel migliore dei casi - O(n)
  • Caso medio - dipende dalla sequenza di gap
  • Caso peggiore - O (n2) o O (nlog n2) a seconda della sequenza di gap
  • Stabilità - instabile
private void ShellSort(long[] inputArray)
{
    long j, temp = 0;
    int increment = (inputArray.Length) / 2;
    while (increment > 0)
    {
        for (int index = 0; index < inputArray.Length; index++)
        {
            j = index;
            temp = inputArray[index];
            while ((j >= increment) && inputArray[j - increment] > temp)
            {
                inputArray[j] = inputArray[j - increment];
                j = j - increment;
            }
            inputArray[j] = temp;
        }
        if (increment / 2 != 0)
            increment = increment / 2;
        else if (increment == 1)
            increment = 0;
        else
            increment = 1;
    }
}

Merge Sorts

In questa categoria c’è un unico algoritmo chiamato proprio Merge Sort.

L’algoritmo sfrutta la facilità di fusione di liste già ordinate in una nuova lista ordinata. Si inizia mettendo a confronto due elementi alla volta (cioè, 1 con 2, poi 3 con 4 ...) e si scambiano tra loro se il primo deve venire dopo il secondo. Si unisce poi ognuna delle liste risultanti in elenchi di quattro, si fondono poi tali elenchi di quattro e così via, finché non si ottengono due liste unite nella lista finale ordinata. Nella maggior parte delle implementazioni è stabile, nel senso che conserva l’ordine di ingresso con un output ordinato. È un algoritmo del tipo divide et impera.

  • Nel migliore dei casi - O (n) o O (n log n)
  • Caso medio - O (n log n)
  • Caso peggiore - O (n log n)
  • Stabilità - dipende dall’implementazione
private void MergeSort(long[] inputArray)
{
    int left = 0;
    int right = inputArray.Length - 1;
    InternalMergeSort(inputArray, left, right);
}
private void InternalMergeSort(long[] inputArray, int left, int right)
{
    int mid = 0;
    if (left < right)
    {
        mid = (left + right) / 2;
        InternalMergeSort(inputArray, left, mid);
        InternalMergeSort(inputArray,(mid + 1), right);
        MergeSortedArray(inputArray, left, mid, right);
    }
}
private void MergeSortedArray(long[] inputArray, int left, int mid, int right)
{
    int index = 0;
    int total_elements = right-left+1; //BODMAS rule
    int right_start = mid + 1;
    int temp_location = left;
    long[] tempArray = new long[total_elements];

    while ((left <= mid) && right_start <= right)
    {
        if (inputArray[left] <= inputArray[right_start])
        {
            tempArray[index++] = inputArray[left++];
        }
        else
        {
            tempArray[index++] = inputArray[right_start++];
        }
    }
    if (left > mid)
    {
        for(int j = right_start; j <= right; j++)
            tempArray[index++] = inputArray[right_start++];
    }
    else
    {
        for(int j = left; j <= mid; j++)
            tempArray[index++] = inputArray[left++];
    }
    for (int i = 0, j = temp_location; i < total_elements; i++, j++)
    {
        inputArray[j] = tempArray[i];
    }
}



Ti potrebbe interessare anche

commenta la notizia

C'è 1 commento
Redazione
Ti interessano altri articoli su questo argomento?
Chiedi alla nostra Redazione!