algorithm
Trier Pigeonhole

Pigeonhole Trier les informations de base

Pigeonhole Sort est un algorithme de tri adapté au tri des listes d'éléments dont le nombre d'éléments (n) et le nombre de valeurs de clé possibles (N) sont approximativement les mêmes. Il nécessite O (n + Range) temps où n est le nombre d'éléments dans le tableau en entrée et «Range» est le nombre de valeurs possibles dans le tableau.

Travailler (Pseudo Code) pour Pigeonhole Trier:

1. Recherchez les valeurs minimales et maximales dans le tableau. Laissez les valeurs minimum et maximum être «min» et «max» respectivement. Vous trouverez également la plage "max-min-1".
2. Mettre en place un tableau de «pigeonniers» initialement vides de la même taille que la gamme.
3. Visitez chaque élément du tableau et placez chaque élément dans son casier. Une entrée d'élément [i] est placée dans le trou à l'entrée de l'index [i] - min.
4. Commencez la boucle dans tout le tableau de casiers et réinsérez les éléments des trous non vides dans le tableau d'origine.

Le tri des pigeonniers est similaire au tri par comptage, donc voici une comparaison entre le tri des pigeonniers et le tri par comptage.

Exemple de Pigeonhole Trier:

Espace auxiliaire: O(n)
Complexité temporelle: O(n + N)

Implémentation 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;
    }
}