algorithm
Pigeonhole Sort

Pigeonhole Sortera grundläggande information

Pigeonhole Sort är en sorteringsalgoritm som är lämplig för sortering av listor över element där antalet element (n) och antalet möjliga nyckelvärden (N) är ungefär samma. Det kräver O (n + Range) -tid där n är antalet element i inmatningsfältet och 'Range' är antalet möjliga värden i array.

Arbetar (Pseudokod) för Pigeonhole Sortera:

1. Hitta minimi- och maximivärden i array. Låt minimi- och maxvärdena vara 'min' respektive 'max'. Hitta även intervallet som 'max-min-1'.
2. Ställ in en matris med ursprungligen tomma "duvahål" i samma storlek som i sortimentet.
3. Besök varje element i matrisen och lägg sedan varje element i sin duva. En elementingång [i] läggs i hålet vid indexingången [i] - min.
4. Starta slingan över duvorhålsfältet i ordning och sätt tillbaka elementen från icke-tomma hål i den ursprungliga matrisen.

Pigeonhole Sortering liknar räknasortering, så här är en jämförelse mellan Pigeonhole Sortering och räkningssortering.

Exempel på Pigeonhole Sort:

Space Auxiliary: O(n)
Tidskomplexitet: O(n + N)

C # Implementering

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;
    }
}