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

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

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

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

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

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

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()) } 

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