Сортування Діріхле

Сортування Діріхле — це алгоритм сортування, який підходить для сортування списків елементів, де кількість елементів (n) і довжина діапазону можливих значень ключів (N) приблизно однакові. Це вимагає O(n+N) часу. Він подібний до сортування підрахунком, але відрізняється тим, що він переміщує елементи двічі: один раз в масив відрахувань, а в другий раз до кінцевого масиву, оскільки сортування підрахунком створює допоміжний масив для обчислення кінцевого місця кожного елемента і його переміщення.

Сортування Діріхле

Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	${\displaystyle O(N+n)}$, де N — діапазон значень, n довжина вхідного масиву
Просторова складність у найгіршому випадку	${\displaystyle O(N+n)}$

Алгоритм працює таким чином:

1. Враховуючи масив значень, що підлягають сортуванню, створюється допоміжний масив спочатку порожніх значень, один прохід для кожного ключа через діапазон вихідного масиву.
2. Переходячи до початкового масиву, кожне значення кладеться в комірку, що відповідає його ключу, таким чином, щоб кожна комірка згодом містила список всіх значень з цим ключем.
3. Послідовно переставляється матриця з наведених елементів, і елементи кладуться з непустого вузла назад у вихідний масив.

Приклад

Відсортуємо ці пари значень за першим елементом:

• (5, «привіт»)
• (3, «пиріг»)
• (8, «яблуко»)
• (5, «король»)

Для кожного значення між 3 і 8 ми встановлюємо комірку, а потім переміщуємо кожен елемент у його комірку:

• 3: (3, «пиріг»)
• 4:
• 5: (5, «привіт»), (5, «король»)
• 6:
• 7:
• 8: (8, «яблуко»)

Потім матриця повторюється, а елементи повертаються до початкового списку.

Різниця між сортуванням Діріхле і сортуванням підрахунком полягає в тому, що в сортуванні підрахунку допоміжний масив не містить списків вхідних елементів, тільки підраховує:

• 3: 1
• 4: 0
• 5: 2
• 6: 0
• 7: 0
• 8: 1

Використовуючи цю інформацію, можна було б виконати серію обмінів на вхідному масиві, які б поклали його в порядок, переміщаючи елементи тільки один раз.

Для масивів, де N значно перевищує n, сортування комірками є узагальненням, яке є більш ефективним у просторі та часі.

Реалізації Python та Golang

Python

def pigeonhole_sort(a): mi = min(a) size = max(a) - mi + 1 holes = [0] * size for x in a: holes[x - mi] += 1 i = 0 for count in xrange(size): while holes[count] > 0: holes[count] -= 1 a[i] = count + mi i += 1 

Golang

type Pair struct { Key int Value string } type KeyValueArray []Pair func (a KeyValueArray) MinKey() int { if len(a) <= 0{ return 0 } min := a[0].Key for _, v := range a { if min > v.Key { min = v.Key } } return min } func (a KeyValueArray) MaxKey() int { if len(a) <= 0{ return 0 } max := a[0].Key for _, v := range a { if max < v.Key { max = v.Key } } return max } func (a KeyValueArray) pigeonHoleSort() []int{ mi := a.MinKey() size := a.MaxKey() - mi + 1 aux := make([]int, len(a)) holes := make([]int, size) for _, pair := range a { holes[pair.Key - mi] += 1 } i := 0 for count := 0; count < size; count++ { for holes[count] > 0 { holes[count] -= 1 aux[i] = count + mi i += 1 } } return aux } func main() { arr := []Pair{ {5, "hello"}, {3, "pie"}, {8, "apple"}, {5, "king"}, } kvArr := KeyValueArray(arr) fmt.Println(kvArr.pigeonHoleSort()) } 

Див. також

• Принцип Діріхле
• Сортування за розрядами

Список літератури

1. NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort
2. Black, Paul E. Dictionary of Algorithms and Data Structures. NIST. Процитовано 6 листопада 2015.