Трети семинар по структури от данни - 24.10.2024

Долна граници на сортиране с преки сравнения. Алгоритъмът Counting sort.

За пряко сравнение можем да си мислим като за отговор с "да" или "не" на въпроса "а по-голям ли е от b". Алгоритъм за сортиране с преки сравнения задава такива въпроси за да стигне до отговора. Разгледаните до момента алгоритми са алгоритми за сортиране с преки сравнения. Видяхме, че задачата сортиране може да се реши във време O(nlog(n)). Възможно ли е да се справим по - добре? Възможно ли е да намерим алгоритъм с по - ниска асимптотика от O(nlog(n)).

Отговорът на този въпрос е не. Всеки алгоритъм за сортиране използващ преки сравнения има долна граница Ω(nlogn). Това означава, че не можем да съставим алгоритъм за сортиране използващ преки сравнения и имащ сложност по-ниска от nlogn.

Все пак съществуват и други алгоритми за сортиране, които не използват преки сравнения. Тяхното предимство е, че асимптотично работят по-бързо. Недостатъкът е, че не работят върху произволен тип елементи.

Пример за такъв алгоритъм е Counting sort. Входът е масив от цели числа. Работейки с числа знаем, че всеки елемент в масива е от интервала [min, ..., max] (където min и max са съответно най - малкия и най - големия елемент в масива).

Накратко, можем да обобщим работата му по следния начин: 1. Създай два масива count и copy. copy е копия на входния масив. count е масив с размер max - min + 1 пълен с нули. 2. Преброй колко пъти се среща всеки елемент на входния масив. * След изпълнение на стъпка 2 count[i - min] - колко пъти се среща i във входния масив. 3. Последователно приложи count[i] += count[i - 1] за i от 1 до count.size(). * Тази стъпка променя масива count по следния начин - count[i - min] отговаря на въпроса коя е най - дясната позиция на i в сортираната последователност. Наистина, преди стъпка 3 в count има брой на елементите. Елементът на 0 позиция е ясен - ако имаме 3 единици най - дясната позиция на единицата е 3 (ако индексираме от 1, иначе 2). Ако имаме 3 единици и две двойки, най - дясната позиция на двойката е 5. Ако имаме 3 единици 2 двойки и 7 четворки най - дясната позиция на 4 е 12 и тн... 4. След като знаем най - дясната позиция на всеки елемент за всеки елемент от copy отдясно наляво * Постави елемента copy[i] на правилната (най - дясната) позиция във входния масив. * Намали стойността на count[copy[i] - min]. - Това ни дава следващата позиция (тази вляво от дясната) за да може като го видим следващия път да го сложим на правилната позиция.

Всички тези магии се правят за да може алгоритъма да е стабилен. Тръгването отдясно наляво (от n - 1 до 0) не е случайно - разполагаме с най - дясната позиция на всеки елемент. Логично е при три елемента първо да се справиш с най - десния.

Структури от данни

TBI

Реализация на динамичен масив.