Доповідь Сортування підрахунком
.docxЗміст
Вступ ...................................................................................................................... 3
1. Опис алгоритму ................................................................................................ 5
1.1 Простий алгоритм ................................................................................. 5
1.2 Алгоритм зі списком ............................................................................. 5
1.3. Стійкий алгоритм ................................................................................. 6
1.4. Узагальнення на довільний цілочисельний діапазон……................ 6
1.5. Аналіз .................................................................................................... 7
2. Реалізація на Pascal............................................................................................ 8
Висновок ............................................................................................................ 9
Список використаної літератури ..................................................................... 10
Вступ
Сортування підрахунком - алгоритм сортування, в якому використовується діапазон чисел сортованого масиву (списку) для підрахунку співпадаючих елементів. Застосування сортування підрахунком доцільно лише тоді, коли кількість сортованих чисел набагато більша діапазона можливих значень, наприклад, мільйон натуральних чисел менших 100.
Ідея сортування вказана в її назві - потрібно підраховувати число співпадаючих елементів, а потім вибудовувати масив. Нехай, наприклад, є масив A з мільйона натуральних чисел, менших 100. Тоді можна створити допоміжний масив B з 99 (1..99) елементів, «пробігти» весь вихідний масив і обчислювати частоту зустрічальності кожного елемента - тобто якщо A[i]=a, то B[a] слід збільшити на одиницю. Потім «пробігти» лічильником i масив B, записуючи в масив A число i B[i] разів.
Якщо список задовольняє цим вимогам, сортування підрахунком виконується неймовірно швидко. В одному з тестів на комп'ютері з процесором Pentium з тактовою частотою 90 МГц, швидке сортування 100000 елементів зі значеннями від 1 до 1000 зайняла 24,44 секунди. Для сортування тих же елементів сортуванням підрахунку треба було всього 0,88 секунд - в 27 разів менше часу.
Видатна швидкість сортування підрахунком досягається за рахунок того, що при цьому не використовуються операції порівняння. Без використання операцій порівняння, алгоритм сортування підрахунком дозволяє впорядковувати елементи за час порядку O(N).
Ефективність алгоритму падає, якщо попадає декілька різних елементів в одну комірку, бо їх треба додатково сортувати. Необхідність сортування всередині комірок позбавляє алгоритм сенсу, так як кожен елемент доведеться переглядати більше одного разу.
Проблеми можуть виникати, тільки якщо список містить невелике число різних значень. Наприклад, якщо всі елементи мають одне і те ж значення, вони всі будуть поміщені в одну комірку. Якщо алгоритм не виявить це, він знову і знову буде поміщати всі елементи в одину і ту ж комірку, викликавши нескінченну рекурсію і вичерпавши весь стековий простір.
Рис. 1. Обробка алгоритмом CountingSort вхідного масиву A[1…8]
1.Опис алгоритму
Припустимо, що вхідний масив складається з n цілих чисел в діапазоні від 0 до k−1, де k ∈ N. Далі алгоритм буде узагальнений для довільного целочисленного діапазону. Існує кілька модифікацій сортування підрахунком.
1.1.Простий алгоритм
Це найпростіший варіант алгоритму. Створити допоміжний масив C [0..k-1], що складається з нулів, потім послідовно прочитати елементи вхідного масиву A, для кожного A [i] збільшити C [A [i]] на одиницю. Тепер досить пройти по масиву C, для кожного j∈{0, ..., k-1} в масив A послідовно записати число j C [j] раз.
SimpleCountingSort
for i = 0 to k – 1 do
C[i] = 0;
for i = 0 to n – 1
C[A[i]] = C[A[i]] + 1;
b = 0;
for j = 0 to k – 1
for i = 0 to C[j] – 1
A[b] = j;
b = b + 1;
1.2.Алгоритм зі списком
Цей варіант використовується, коли на вхід подається масив структур даних, який слід впорядкувати за ключам (key). Потрібно створити допоміжний масив C [0..k - 1], кожен C [i] в подальшому буде містити список елементів з вхідного масиву. Потім послідовно прочитати елементи вхідного масиву A, кожен A [i] додати в список C [A [i] .key]. У висновку пройти по масиву C, для кожного j∈ {0, ..., k-1} в масив A послідовно записувати елементи списку C [j]. Алгоритм стійкий.
ListCountingSort
for i = 0 to k - 1
C[i] = NULL;
for i = 0 to n - 1
C[A[i].key].add(A[i]);
b = 0;
for j = 0 to k - 1
p = C[j];
while p != NULL
A[b] = p.data;
p = p.next();
b = b + 1;
1.3.Стійкий алгоритм
В цьому варіанті крім вхідного масиву A буде потрібно два допоміжних масиву - C [0..k - 1] для лічильника і B [0..n - 1] для відсортованого масиву. Спочатку слід заповнити масив C нулями, і для кожного A [i] збільшити C[A[i]] на 1. Далі підраховується кількість елементів менших або рівних k-1. Для цього кожен C [j], починаючи з C [1], збільшують на C [j - 1]. Таким чином в останній комірці буде знаходитися кількість елементів від 0 до k-1 існуючих у вхідному масиві. На останньому кроці алгоритму читається вхідний масив з кінця, значення C [A [i]] зменшується на 1 і в кожний B[C[A[i]]] записується A [i]. Алгоритм стійкий.
StableCountingSort
for i = 0 to k - 1
C[i] = 0;
for i = 0 to n - 1
C[A[i]] = C[A[i]] + 1;
for j = 1 to k - 1
C[j] = C[j] + C[j - 1];
for i = n - 1 to 0
C[A[i]] = C[A[i]] - 1;
B[C[A[i]]] = A[i];
1.4.Узагальнення на довільний цілочисельний діапазон
Виникає кілька питань. Що робити, якщо діапазон значень (min і max) заздалегідь не відомий? Що робити, якщо мінімальне значення більше нуля або в сортируемих даних присутні негативні числа? Перше питання можна вирішити лінійним пошуком min і max, що не вплине на асимптотику алгоритму. Друге питання дещо складніше. Якщо min більше нуля, то слід при роботі з масивом C з A [i] відняти min, а при зворотній записи додавати. При наявності негативних чисел потрібно при роботі з масивом C до A [i] додавати | min |, а при зворотньому записі віднімати.
1.5.Аналіз
У перших двох алгоритмах перші два циклу працюють за Θ(k) і Θ(n), відповідно; подвійний цикл за Θ(n+k). У третьому алгоритмі цикли займають Θ(k), Θ(n), відповідно. Разом всі три алгоритму мають лінійну тимчасову трудомісткість Θ(n+k). Використовувана пам'ять в перших двох алгоритмах дорівнює Θ(k), а в третьому Θ(n+k).
Фраза «складність алгоритму є Θ(n)» означає, що зі збільшенням параметра n, що характеризує кількість вхідної інформації алгоритму, час роботи алгоритму буде зростати не швидше, ніж деяка константа, помножена на n.
2.Реалізація на Pascal
PROCEDURE CountingSort (VAR a: ARRAY OF INTEGER;
min, max: INTEGER);
VAR
i, j, c: INTEGER;
b: POINTER TO ARRAY OF INTEGER;
BEGIN
FOR i := 0 TO LEN(a) - 1 DO
INC(b[a[i] - min])
i := 0;
FOR j := min TO max DO
BEGIN
c := b[j - min];
WHILE c > 0 DO
BEGIN
a[i] := j;
INC(i);
DEC(c)
END
END
END;
Висновок
Сортування підрахунком - алгоритм сортування масиву, при якому підраховується число однакових елементів. Алгоритм вигідно застосовувати, коли в масиві багато елементів, але всі вони досить малі.
Сортування підрахунком - спеціалізований алгоритм, який дуже добре працює, якщо елементи даних - цілі числа, значення яких знаходяться
у відносно вузькому діапазоні. Цей алгоритм працює досить швидко, наприклад, якщо значення знаходяться від 1 до 1000. Поки виконуються ці умови, алгоритм працює відмінно.
На практиці, розподіл даних зазвичай не є рівномірним. В деякі блоки потрапляє більше елементів, в інші менше. Тим не менше, якщо розподіл в цілому близький до рівномірного, то в кожному з блоків виявиться лише невелике число елементів.
Важлива властивість алгоритму сортування підрахунком полягає в тому, що він стійкий: елементи з одним й тим самим значенням знаходяться у вихідному масиві в тому самому порядку, що й у вхідному. Зазвичай властивість стійкості важлива тільки для ситуації, коли разом з елементами для сортування є додаткові дані.
Список використаної літератури
1. Ананій В. Левітін Глава 7. Просторово-часовий компроміс: Сортування підрахунком // Алгоритми: введення в розробку і аналіз = Introduction to The Design and Analysis of Aigorithms. - М .: «Вільямс», 2006. - С. 307 - 310.
2. Кормен, Томас Х., Лейзерсон, Чарльз І., Ривест, Рональд Л., Штайн, Кліфорд Глава 8. Сортування за лінійний час // Алгоритми: побудова й аналіз = Introduction to Algorithms. - 2-e видання. - М .: «Вільямс», 2005. - С. 224-226.