Сортування Діріхле — це алгоритм сортування, який підходить для сортування списків елементів, де кількість елементів (n) і довжина діапазону можливих значень ключів (N) приблизно однакові.NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort Це вимагає O(n+N) часу. Він подібний до сортування підрахунком, але відрізняється тим, що він переміщує елементи двічі: один раз в масив відрахувань, а в другий раз до кінцевого масиву, оскільки сортування підрахунком створює допоміжний масив для обчислення кінцевого місця кожного елемента і його переміщення.
Алгоритм працює таким чином:
Враховуючи масив значень, що підлягають сортуванню, створюється допоміжний масив спочатку порожніх значень, один прохід для кожного ключа через діапазон вихідного масиву. Переходячи до початкового масиву, кожне значення кладеться в комірку, що відповідає його ключу, таким чином, щоб кожна комірка згодом містила список всіх значень з цим ключем. Послідовно переставляється матриця з наведених елементів, і елементи кладуться з непустого вузла назад у вихідний масив.
Приклад Відсортуємо ці пари значень за першим елементом:
(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 Pythondef pigeonhole_sort(a): mi = min(a) size = max(a) - mi + 1 holes = * 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.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.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()) }
Див. також Принцип Діріхле Сортування за розрядами
Список літератури