algorithm
Pigeonhole Sort

Pigeonhole Sorteer basisinformatie

Pigeonhole Sort is een sorteeralgoritme dat geschikt is voor het sorteren van lijsten met elementen waarbij het aantal elementen (n) en het aantal mogelijke sleutelwaarden (N) ongeveer hetzelfde zijn. Het vereist O (n + bereik) tijd waarbij n het aantal elementen in de invoerarray is en 'bereik' het aantal mogelijke waarden in de array is.

Werken (Pseudo-code) voor Pigeonhole Sorteren:

1. Vind minimum- en maximumwaarden in array. Laat de minimum- en maximumwaarden respectievelijk 'min' en 'max' zijn. Vind ook bereik als 'max-min-1'.
2. Stel een reeks aanvankelijk lege "hokjes" in, even groot als van het bereik.
3. Bezoek elk element van de reeks en plaats elk element in zijn vak. Een elementingang [i] wordt in de indexingang [i] - min. Geplaatst.
4. Begin de lus over de hele reeks met hokjes in volgorde en plaats de elementen van niet-lege gaten terug in de oorspronkelijke reeks.

Pigeonhole sort is vergelijkbaar met telsort, dus hier is een vergelijking tussen Pigeonhole Sort en telsort.

Voorbeeld van Pigeonhole Sort:

Extra ruimte: O(n)
Tijdcomplexiteit: O(n + N)

C # Implementatie

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