algorithm
Pigeonhole Sort

Pigeonhole Sort Grundlegende Informationen

Pigeonhole Sort ist ein Sortieralgorithmus, der zum Sortieren von Listen von Elementen geeignet ist, bei denen die Anzahl der Elemente (n) und die Anzahl der möglichen Schlüsselwerte (N) ungefähr gleich sind. Es ist O (n + Range) Zeit erforderlich, wobei n die Anzahl der Elemente im Eingabearray und "Range" die Anzahl der möglichen Werte im Array ist.

Arbeiten (Pseudo-Code) für Pigeonhole Sort:

1. Finden Sie minimale und maximale Werte im Array. Die minimalen und maximalen Werte seien 'min' bzw. 'max'. Finden Sie auch den Bereich als 'max-min-1'.
2. Richten Sie ein Array mit zunächst leeren "Schubladen" ein, die der Größe des Bereichs entsprechen.
3. Besuchen Sie jedes Element des Arrays und legen Sie dann jedes Element in seine Schublade. Eine Elementeingabe [i] wird an der Indexeingabe [i] in das Loch eingefügt - min.
4. Starten Sie die Schleife über das gesamte Schubladenfeld, und fügen Sie die Elemente aus nicht leeren Löchern wieder in das ursprüngliche Array ein.

Die Pigeonhole-Sortierung ähnelt der Zählsortierung. Hier ist ein Vergleich zwischen der Pigeonhole-Sortierung und der Zählsortierung.

Beispiel für Pigeonhole Sort:

Weltraumhilfsmittel: O(n)
Zeitkomplexität: O(n + N)

C # -Implementierung

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