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

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

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

Сортування Діріхле — це алгоритм сортування, який підходить для сортування списків елементів, де кількість елементів (n) і довжина діапазону можливих значень ключів (N) приблизно однакові. Це вимагає 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())
}

Див. також

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