ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ

 

4.1. Вибір варіанта індивідуального завдання

Введемо позначення: DN – день народження

MN – місяць народження

А1 – ASCII-код першої літери прізвища – велика латинська літера

№ варіанта = (DN + MN + А1) % 25+ 1

4.2. Варіанти завдань

Загальна частина:

Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування.

 

Провести дослідження побудованого методу за схемою:

1) Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний).

2) Намалювати схему алгоритму на прикладі послідовності з десяти (або більше при необхідності) цілих чисел, показуючи всі проміжні кроки процесу сортування.

3) Дослідити метод cортування на стійкість.

4) Дослідити метод cортування на економність використання пам’яті.

5) Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).

6) Дослідити ефективність методу. Для цього програмно визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому () і в найгіршому () випадках. Середні значення кількості порівнянь () і кількості перестановок () визначити, як середнє арифметичне для кожної величини від великої кількості спроб сортування випадкових послідовностей. Побудувати графіки залежностей , , , від кількості елементів n, де n змінюється від 1 до 100 000.

7) Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості.

Індивідуальні завдання:

1. Сортування методом простої вставки.

2. Сортування просіюванням з барьером.

3. Сортування бінарною вставкою.

4. Сортування методом простого вибору.

5. Сортування методом простого обміну.

6. Шейкер-сортування.

7. Сортування Шелла, що використовує кроки 9, 5, 3 і 1

8. Сортування Шелла, що обчислює послідовність приростів по першій формулі.

9. Сортування Шелла, що обчислює послідовність приростів по другій формулі.

10. Пірамідальне сортування.

11. Швидке сортування.

12. Сортування злиттям.

13. Порозрядне сортування.

14. Бітове сортування.

15. Сортування методом підрахунку порівнянь [1, 94-97 c.].

16. Сортування методом підрахунку розпреділення [1, 97-98 c.].

17. Сортування з обчисленням адреси [1, 118-121 c.], [2, 469-472 c.].

18. Обмінне сортування зі злиттям [1, 131-133 c.].

19. Обмінне порозрядне сортування [1, 144-150 c.].

20. Сортування методом двохшляхового злиття [1, 181-182 c.].

21. Сортування методом природного двохшляхового злиття [1, 183-185 c.].

22. Сортування методом простого двохшляхового злиття [1, 186-187 c.].

23. Сортування методом злиття списків [1, 187-189 c.].

24. Порозрядне сортування списку [1, 195-200 с.]

25. Сортування за допомогою вставок і злиття [1, 208-210 c.].

 

5. ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТУ

I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта.

II. В звіті мають бути відображені наступні пункти:

1. Мета роботи.

2. Постановка задачі.

2.1. Загальна частина

2.2. Індивідуальне завдання

3. Опис алгоритму.

4. Дослідження методу.

4.1. Обґрунтування вибору структури даних.

4.2. Схема алгоритму cортування на прикладі послідовності чисел.

4.3. Дослідження методу cортування на стійкість.

4.4. Дослідження методу cортування на економність використання пам’яті.

4.5. Дослідження методу на специфіку вхідної послідовності.

4.6. Дослідження ефективності методу.

1) Програмні дослідження.

а) Кількість порівнянь в найкращому, в найгіршому та в середньому випадках.

б) Кількість перестановок в найкращому, в найгіршому та в середньому випадках.

2) Чисельні дослідження.

а) Визначення класу (підкласу) алгоритму по його трудомісткості.

б) Обчислення функції трудомісткості алгоритму.

3) Асимптотичні дослідження.

а) Знаходження часової складності алгоритму (за нотацією Ландау).

б) Визначення назви асимптотичного класу ефективності алгоритму.

5. Результати виконання програми.

Висновки.

Додатки (тексти програм з коментарями).

6. КОНТРОЛЬНІ ЗАВДАННЯ

1.	Промоделюйте вручну, показуючи всі проміжні результати, роботу алгоритму сортування методом простої вставки наступної послідовності: 55, 3, 20, 88, 1, 66, 9.
2.	Промоделювати вручну, показуючи всі проміжні кроки, роботу алгоритму швидкого сортування наступної послідовності: 15, 23, 47, 54, 10, 5, 19.
3.	Дослідити на стійкість метод cортування простим вибором, програмна реалізація якого має такий вигляд:   procedure SelectionSort(var a:VectType); var i,j,k: integer; min: KeyType; Begin for i:=1 to n-1 do begin k:=i; min:=a[i]; for j:=i+1 to n do if a[j] < = min then begin k:=j; min:=a[k]; end; a[k]:=a[i]; a[i]:=min; end; End;

 

СПИСОК ЛІТЕРАТУРИ

1. Кнут Д. Искусство програмирования, том 3. Сортировка и поиск. – М.: Изд.дом ”Вильямс”, 2001. – 832 с.

2. Вирт Н. Алгоритмы + структуры данных = програмы. –М.:Мир,1985 - 406 с.

3. Ленгсам Й., Огенстайн М., Тененбаум А. Структура данных для персональных ЭВМ. –М.:Мир, 1989 - 560 с.

4. Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі. –К:Либідь, 1993 - 224 с.

5. Семакин И.Г., Шестаков А.П. Лекции по программированию. Пермь: изд-во ПГУ, 1998.