algorithm
Eimer-Sort

Grundlegende Informationen zum Eimersortieren

Bucket Sort ist ein Sortieralgorithmus, bei dem Elemente des Eingabearrays in Buckets verteilt werden. Nachdem alle Elemente verteilt wurden, werden die Buckets durch einen anderen Sortieralgorithmus einzeln sortiert. Manchmal wird es auch rekursiv sortiert.

Pseudo-Code für Bucket-Sort

1. N sei die Länge der Eingabeliste L;
2. Für jedes Element i von L
3. Wenn B [i] nicht leer ist
4. Setze A [i] in B [i];
5. Sonst B [i]: = A [i]
6. Rückgabe von Concat B [i .. n] in eine sortierte Liste;

Beispiel für die Sortierreihenfolge:

Die meisten Leute verwenden Einfügungsparadigmen zur Optimierung.
Hilfsraum: O{n}

C # -Implementierung

public class BucketSort
{
    public static void SortBucket(ref int[] input)
    {
        int minValue = input[0];
        int maxValue = input[0];
        int k = 0;

        for (int i = input.Length - 1; i >= 1; i--)
        {
            if (input[i] > maxValue) maxValue = input[i];
            if (input[i] < minValue) minValue = input[i];
        }

        List<int>[] bucket = new List<int>[maxValue - minValue + 1];

        for (int i = bucket.Length - 1; i >= 0; i--)
        {
            bucket[i] = new List<int>();
        }

        foreach (int i in input)
        {
            bucket[i - minValue].Add(i);
        }

        foreach (List<int> b in bucket)
        {
            if (b.Count > 0)
            {
                foreach (int t in b)
                {
                    input[k] = t;
                    k++;
                }
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortBucket(ref input);
        return input;
    }
}