Довідка

Практичне заняття 11. Алгоритми сортування. Сортування підрахунком

Дізнаємось

Що таке сортування підрахунком і як воно працює.
У яких випадках його доцільно використовувати.
Як працює процес підрахунку частот елементів.
Яка часова та просторова складність алгоритму.
Як можна модифікувати Counting Sort для забезпечення стабільності.

Навчимось

Реалізовувати алгоритм сортування підрахунком у мові Python.
Використовувати додаткові масиви для підрахунку кількості входжень елементів.
Оптимізувати алгоритм для різних діапазонів значень.
Розуміти принцип стабільного сортування та його вплив на результат.
Порівнювати Counting Sort з іншими алгоритмами сортування за швидкодією та пам’яттю.

Матеріали

Доступно тільки для зареєстрованих користувачів

Проблемні питання

Доступно тільки для зареєстрованих користувачів

Д.з.

Доступно тільки для зареєстрованих користувачів

№	Тема
3 лекції
1	Лекція 1. Поняття структур даних та їх класифікація. Формалізація поняття алгоритму. Основні напрямки в теорії алгоритмів
2	Лекція 2. Масиви. Стеки. Черги. Дек
3	Лекція 3. Зв’язні списки. Хеш-таблиці
4	Лекція 4. Пряма адресація. Хеш-функції.
5	Лекція 5. Двійкові дерева пошуку
6	Лекція 6. Сортування вибором та обмінне сортування. Сортування злиттям. Швидке сортування
7	Лекція 7. Сортування заздалегідь. Збалансовані дерева пошуку
8	Лекція 8. Послідовний пошук. Бінарний пошук. Методи, засновані на порівнянні ключів або на цифрових властивостях ключів
9	Лекція 9. Генератори псевдо випадкових чисел. Властивості випадкових та псевдо випадкових чисел. Недоліки генераторів псевдовипадкових чисел. Лінійний конгруентний метод.
10	Лекція 10. Представлення графа. Вершини. Ребра. Орієнтовані та неорієнтовані графи. Список суміжних вершин. Матриця суміжності. Пошук в ширину та в глибину. Дерева пошуку
11	Лекція 11. Властивості відрізків. Опукла комбінація. Векторний добуток. Обмежуючий прямокутник. Обчислення опуклої оболонки. Задача комівояжера. Задача про рюкзак. Задача про призначення
12	Лекція 12. Поняття хеш-функції. Метод відкритого хешування. Метод закритого кешування. Вибір хеш-функції
13	Лекція 13. Швидкість росту функцій. Логарифмічний, лінійний, квадратичний експоненціальний рости.
14	Лекція 14. Поняття про рекурсію. Умови застосування рекурсії. Аналіз рекурсивних алгоритмів. Методи розв’язання рекурсивних рівнянь. Дерево рекурсій.
15	Лекція 15. Динамічне програмування. Задача про множення матриць. Оцінка складності алгоритму задач про множення матриць.
16	Лекція 16. Жадібні алгоритми. Використання жадібних алгоритмів у програмуванні
3 практичні заняття
1	Практичне заняття 1. Вступ до структур даних та алгоритмів.
2	Практичне заняття 2. Базові структури даних
3	Практичне заняття 3. Базові структури даних. Хеш-таблиці
4	Практичне заняття 4. Базові структури даних. Дерева
5	Практичне заняття 5. Алгоритми пошуку. Лінійний пошук
6	Практичне заняття 6. Алгоритми пошуку. Бінарний пошук
7	Практичне заняття 7. Алгоритми сортування. Сортування бульбашкою
8	Практичне заняття 8. Алгоритми сортування. Сортування вибором
9	Практичне заняття 9. Алгоритми сортування. Сортування вставкою
10	Практичне заняття 10. Алгоритми сортування. Швидке сортування
11	Практичне заняття 11. Алгоритми сортування. Сортування підрахунком
12	Практичне заняття 12. Алгоритми сортування. Сортування за розрядами
13	Практичне заняття 13. Комбінаторні алгоритми
14	Практичне заняття 14. Фундаментальні алгоритми на графах та деревах
15	Практичне заняття 15. Рекурсія
16	Практичне заняття 16. Динамічне програмування
17	Практичне заняття 17. Жадібні алгоритми

Загальнонаціональна хвилина мовчання за загиблими внаслідок збройної агресії рф проти України

60