Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи сортуваня. Сортування підрахунком.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки
Предмет:
Алгоритми і структури даних
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти України
Національний університет «Львівська політехніка»
Методичні вказівки
До лабораторної роботи № 7
На тему: «Методи сортуваня. Сортування підрахунком»
з дисципліни
«Алгоритми і структури даних»
Для базового напрямку 6.0804 «Комп’ютерні науки»
ЗАТВЕРДЖЕНО
на засіданні кафедри
програмного забезпечення
протокол № від 2008 року
місто Львів
2008 рік
Методичні вказівки до лабораторної роботи з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки»
Укладачі: Семчишин Ю. Б.
Коротєєва Т. О.
Вовчак І. Г.
Відповідальний за випуск:
Рецензенти:
Тема роботи: Ознайомлення із методами сортування. Алгоритм сортування пірахунком
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування підрахунком. Виконати лабораторну роботу використавши здобуті знання з методів сортування, зокрема методу сортування підрахунком.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зуcтрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.
Обчислювальна складність роботи алгоритму становить O(N + K), де N — довжина масиву, та K — величина діапазону.
В алгоритмі використовуються додатковий масив, тому ємнісна складність становить E(N + K).
В такій реалізації алгоритм є стабільним (не змінює порядок елементів з однаковим ключем). Використання даного алгоритму є доцільним тільки у випадку малих K.
РЕКОМЕНДОВАНІ ДЖЕРЕЛА
http://www.wikipedia.org/.
Donald Ervin Knuth «The Art of Computer Programming».
2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ
При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм сортування підрахунком.
Використовувати мову програмування C/C++.
Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи.
3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ
Отримати індивідуальне завдання у викладача;
Уточнити завдання (можливі різні трактування завдання);
Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу (алгоритму) на даній лабораторній роботі;
Протестувати на наявність логічних помилок програми;
Оформити звіт відповідно до стандарту;
Захистити виконану роботу.
4. КОНТРОЛЬНІ ПИТАННЯ
Які ви знаєте методи сортування?
Який метод сортування був розглянений на даній лабораторній роботі?
Від чого прямо – залежним являється швидкість сортування?
Опишіть характеристики даного методу.
Порівняєте даний метод із іншими методами сортування вам відомими.
Наскільки являється ефективним даний метод сортування?
Чи використовують даний метод на практиці, і наскільки часто?
Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах?
Чим оригінальним виділяється даний метод від інших?
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора