algorithm
Сортировка Pigeonhole

Pigeonhole Сортировать базовую информацию

Pigeonhole Sort - это алгоритм сортировки, который подходит для сортировки списков элементов, где число элементов (n) и количество возможных значений ключа (N) примерно одинаковы. Для этого требуется время O (n + Range), где n - количество элементов в входном массиве, а «Range» - количество возможных значений в массиве.

Рабочий (псевдо-код) для Pigeonhole Сортировать:

1. Найти минимальное и максимальное значения в массиве. Пусть минимальное и максимальное значения равны «min» и «max» соответственно. Также найдите диапазон как «max-min-1».
2. Настройте массив изначально пустых «голубинок» того же размера, что и диапазон.
3. Посетите каждый элемент массива, а затем поместите каждый элемент в его яму. Элементный вход [i] помещается в отверстие на входе индекса [i] - мин.
4. Начните цикл по всей решетке пигмента и поместите элементы из непустых отверстий обратно в исходный массив.

Тип Pigeonhole аналогичен сортировке сортировки, поэтому здесь приведено сравнение Сортировки Pigeonhole Sort и counting sort.

Пример Pigeonhole Сортировать:

Вспомогательный объем: O(n)
Сложность времени: O(n + N)

Реализация 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;
    }
}