algorithm
Sortilegio di piccionaia

Pigeonhole Ordina informazioni di base

Pigeonhole Sort è un algoritmo di ordinamento che è adatto per ordinare elenchi di elementi in cui il numero di elementi (n) e il numero di possibili valori chiave (N) sono approssimativamente uguali. Richiede tempo O (n + intervallo) dove n è il numero di elementi nell'array di input e 'Intervallo' è il numero di possibili valori nell'array.

Working (Pseudo codice) per Pigeonhole Sort:

1. Trova i valori minimi e massimi nella matrice. Lascia che i valori minimo e massimo siano rispettivamente 'min' e 'max'. Inoltre trova l'intervallo come 'max-min-1'.
2. Configura una serie di "piccioni" inizialmente vuoti delle stesse dimensioni dell'intervallo.
3. Visita ogni elemento dell'array e poi metti ciascun elemento nella sua buca. Un ingresso elemento [i] viene inserito nel foro all'ingresso dell'indice [i] - min.
4. Avvia il ciclo su tutto l'array di pigeonhole in ordine e rimetti gli elementi da fori non vuoti nell'array originale.

L'ordinamento Pigeonhole è simile al tipo di conteggio, quindi ecco un confronto tra ordinamento Pigeonhole e ordinamento del conteggio.

Esempio di ordinamento Pigeonhole:

Spazio ausiliario: O(n)
Complessità del tempo: O(n + N)

Implementazione C #

public class PigeonholeSort
{
    private static void SortPigeonhole(int[] input, int n)
    {
        int min = input[0], max = input[n];
        for (int i = 1; i < n; i++)
        {
            if (input[i] < min) min = input[i];
            if (input[i] > max) max = input[i];
        }
        int range = max - min + 1;
        int[] holes = new int[range];

        for (int i = 0; i < n; i++)
        {
            holes[input[i] - min] = input[i];
        }
        int index = 0;

        for (int i = 0; i < range; i++)
        {
            foreach (var value in holes)
            {
                input[index++] = value;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortPigeonhole(input, input.Length);
        return input;
    }
}