Довідка

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

Дізнаємось

Що таке сортування за розрядами і як воно працює.
У чому різниця між підходами LSD (Least Significant Digit) та MSD (Most Significant Digit).
Як використовувати сортування підрахунком як допоміжний етап у Radix Sort.
Яка часова та просторова складність алгоритму.
Коли Radix Sort перевершує алгоритми, що базуються на порівняннях.

Навчимось

Реалізовувати сортування за розрядами у Python.
Застосовувати алгоритм Counting Sort для сортування цифр на кожному етапі.
Аналізувати ефективність Radix 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