Сортування підрахунком на Python

27.05.20. Час прочитання - 5 хв

Сортування підрахунком (Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів. Ідея алгоритму полягає у тому, щоб підрахувати скільки разів кожен елемент зустрічається у вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.

Алгоритм

Підраховуємо скільки разів в масиві зустрічається кожне значення, і заповнюємо масив підрахованими елементами у відповідних кількостях. Лічильники для всього діапазону чисел створюються заздалегідь (спочатку дорівнюють нулю).

Складність сортування за часом

1. Найгірша O (n + k)
2. Середня O (n + k)
3. Краща O (n)

Кроки до правильного рішення

1. Створюємо функцію counting_sort, яка приймає на вхід список і змінну largest.

2. Усередині функції створюємо список з нулями та довжиною largest + 1.

3. Для кожного елемента вхідного списку збільшуємо значення елемента наступним чином c[alist [i]] = c[alist [i]] + 1.

4. Тепер список містить частоту кожного елемента вхідного списку.

5. Кожному елементу від 1 до length (c) -1 додаємо до значення поточного елемента значення попереднього c[i] = c[i] + c [i - 1].

6. Створюємо result список з таким же розміром, як і вхідний список.

7. Створюємо цикл, який ітерується по списку в зворотному порядку.

8. У кожній ітерації циклу встановлюємо result [c[x]] = x, а потім зменшуємо c[x]на 1.

Сподіваємось, Вам було цікаво та корисно.
Ставте плюсик в коментарях, якщо хочете, щоб ми частіше публікували інформацію про алгоритми➕...