Завдання та порядок виконання. 2.1 Вивчити навчальний матеріал та підготувати відповіді на контрольні питання.

2.1 Вивчити навчальний матеріал та підготувати відповіді на контрольні питання.

2.2 Скласти схему алгоритму рішення задачі за варіантом завдання.

 

3 Контрольні питання

3.1 Зазначте області застосування сортування.

3.2 Сутність методу "кулькового" сортування.

3.3 Сутність сортування методом послідовних мінімумів.

3.4 Сутність сортування методом вставки.

3.5 Методи швидкого сортування.

 

4 Зміст звіту

4.1 Номер роботи, її назва, визначення мети.

4.2 Короткі відповіді на контрольні запитання.

4.3 Алгоритм, короткий його опис.

4.4 Висновки по роботі.

 

4 Навчальний матеріал

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

Методи сортування дуже важливі в теоретичному відношенні і мають велике поширення як у наукових задачах, так і в задачах управління. Вони породили величезне число досліджень. На такому прикладі як сортування, який легко формулюється, можна порівнювати різноманітні алгоритми, досліджувати їхню складність і поведінку в залежності від числа і форми даних. У більшості машин існують стандартні програми сортування і користувач урятований від необхідності писати свою власну програму.

Для сортування всі дані потрібно ввести в машину. Припустимо, що потрібно впорядкувати за зростанням числові дані, які містяться в пам’яті в масиві Т розміром N. Існує багато різноманітних алгоритмів сортування, що дозволяють вирішити цю задачу.

"Кулькове" сортування. Назва походить від образної інтерпретації, при якій у процесі виконання алгоритму більш "легкі" елементи потрохи підіймаються на "поверхню".

Алгоритм (рис.1) "кулькового" сортування складається з послідовних проходів від початку до кінця масиву введених даних Т і обміну сусідніх елементів з інверсією.

Порівнюють пари значень Т(I) і Т(I+1) при I в інтервалі від 1 до N-1; якщо Т(I)>T(I+1), то значення переставляються місцями.

Сортування зупиняється, коли немає чого переставляти; у цьому випадку сортування масиву закінчується.

Сортування пошуком послідовних мінімумів. При першому проході шукається мінімальне значення масиву Т, що потім змінюється місцями з першим елементом T(1), потім пошук продовжується на N-1 елементах, що залишилися, шукається другий мінімум, що змінюється з елементом Т(2) і т.д. Алгоритм сортування пошуком послідовних мінімумів наведено на рис.2.

Сортування методом вставки. Щоб відсортувати масив Т, достатньо вставити T(J) у J-1 вже сортованих перших елементів, при цьому J змінюється від 2 до N. Алгоритм сортування методом вставки наведено на рис.3.

Швидке сортування SHELL-SORT є вдосконаленим методом вставки. Ідея, що покладена в основу цього метода така, що дані попередньо сортуються у блоках, а потім кількість блоків зменшується до тих пір, поки усі данні не будуть в одному блоці. Тим самим значно зменшується кількість обмінів. На операції обмінів у програмі для сортування даних витрачається багато машинного часу. Швидке сортуванняQUICKSORT є одним із найшвидших методів сортування. Серед N значень, які треба відсортувати, обирається значення, яке називають провідним елементом. Цей вибір може проводитися випадковим чином. Потім у початок масиву ставляться усі елементи, менші за провідний, а у кінець –усі інші. На кожній з отриманих послідовностей ця операція повторюється до тих пір, доки не одержані послідовності, які мають один або два елементи. Таким чином масив відсортований. Ефективність цього методу є високою лише у тому випадку, коли вибрані провідні елементи розділяють кожну послідовність на послідовності приблизно однієї довжини.

Розберемо приклад. Дано деяку послідовність чисел:

 

4 3 7 6 9 1 0 2 5

 

Виберемо перше (4), останнє (5) та число (9), яке знаходиться посередині. Середнім числом D є 5, і по ньому дана послідовність ділиться на 2 підгрупи. Для цього число D переставляється на праве провідне місце (у цьому прикладі воно вже там стоїть). Тепер, починаючи з провідного лівого, шукається число більше за 5, а з правого – число менше за 5, і ці числа переставляються місцями. У даному випадку це числа 2 та 7.

 

4 3 2 8 9 1 0 7 5

 

Пошук продовжується до тих пір, доки не зупиниться на числі, котре не вдасться переставити з жодним іншим числом. Таким чином послідовність має вигляд:

 

4 3 2 0 1 9 8 7 5

Потім це число (у даному випадку 9) зміняється з числом, що стоїть у правому кінці (у даному випадку числом 5). Це дає:

 

4 3 2 0 1 5 8 7 9

 

Тепер число 5 стоїть на тому місці, на якому воно буде стояти після закінчення сортування. Таким самим чином сортуються обидві підгрупи (4 3 2 0 1) і (8 7 9), доки в кожній з них не залишиться по одному числу.

 

 

 

 

 

 

 

6 Варіанти індивідуальних завдань

Скласти схему алгоритму сортування двовимірного масиву A(30,30). Елементи розташувати в порядку відповідно варіанту завдання. Результати обробки записати в масив F і вивести на друк.

 

1. Розташувати елементи головної діагоналі за зростанням.

2. Розташувати елементи 2 рядку і 5 стовпчика за зростанням.

3. Розташувати елементи 5 стовпчика і рядка 9 за спаданням.

4. Розташувати елементи 15 рядка і 12 стовпчика за спаданням.

5. Розташувати елементи рядків за зростанням.

6. Розташувати елементи додаткової головної діагоналі за спаданням.

7. Розташувати елементи рядків верхньої трикутної матриці за зростанням.

8. Розташувати елементи стовпчиків верхньої трикутної матриці за зростанням. 9. Розташувати елементи стовпчиків за спаданням.

10. Розташувати елементи рядків 4, 11, 23 за зростанням.

11. Розташувати елементи рядків 1 і 5 за зростанням.

12. Розташувати елементи рядка 4 за зростанням, а рядка 7 за спаданням.

13. Розташувати елементи стовпчика 7 за спаданням, а стовпчика 11 – за зростанням.

14. Розташувати елементи стовпчиків 6, 8, 25 за зростанням.

15. Розташувати елементи рядка 4 і стовпчика 17 за зростанням.

16. Розташувати елементи рядка 14 за зростанням, а стовпчика 5 за спаданням. 17. Розташувати елементи головної діагоналі за спаданням.

18. Розташувати елементи рядків 4, 11, 23 за зростанням.

19. Розташувати елементи стовпчиків 1 і 5 за спаданням.

20. Розташувати елементи рядка 7 за спаданням., а рядка 19 – за зростанням.

21. Розташувати елементи стовпчика 8 за зростанням, а стовпчика 13 – за спаданням.

22. Розташувати елементи стовпчиків 7, 11, 28 за спаданням.

23. Розташувати елементи рядка 6 і стовпчика 21 за спаданням.

24. Розташувати елементи рядка 17 за спаданням, а стовпця 7 – за зростанням.

25. Розташувати елементи головної діагоналі за спаданням.

26. Розташувати елементи 15 рядку і стовпчика 12 за спаданням.

27. Розташувати елементи рядків за спаданням.

28. Розташувати елементи додаткової головної діагоналі за зростанням.

29. Розташувати елементи рядків нижньої трикутної матриці за спаданням.

30. Розташувати елементи стовпчиків нижньої трикутної матриці за спаданням. 31. Розташувати елементи стовпчиків за зростанням.

32. Розташувати елементи непарних рядків за спаданням.

 

 

Список рекомендованої літератури

 

1 Інформатика: Комп’ютерна техніка. Комп’ютерні технології. Посіб. /За ред. О.І.Пушкаря – К.: Видавничий центр “Академія”, 2001. – 696 с.

2 Вычислительная техника и программирование: Учеб. для техн. вузов/ А.В.Петров, В.Е.Алексеев, А.С.Ваулин и др.; Под ред. А.В.Петрова. - М.: Высш. шк., 1990. – 479с.

3 Вычислительная техника и программирование: Практикум по программированию: Практ. пособие/ В.Е. Алексеев, А.С.Ваулин, Г.Б.Петрова; Под ред. А.В.Петрова. - М.: Высш. шк., 1991. – 400 с.

4 Вычислительная техника и программирование: Учебное пособие/В.А.Гладков, Л.В.Филиппович, Т.Н.Морозова, С.А.Третьяков; Под ред.В.А.Гладкова.-Киев: КИЖТ, 1996. – 310 с.

5 Светозарова Г.И., Мельников А.А., Козловский А.В. Практикум по программированию на языке Бейсик: Учеб.пособие для вузов.-М.: Наука. Гл.ред.физ.-мат. лит., 1988.– 368 с.

 

 

Методичні вказівки

до виконання лабораторних робіт 7–15 для студентів усіх спеціальностей з дисципліни “Обчислювальна техніка та програмування”, частина 2.

 

Укладачі: Гладков Владлен Андрійович

 

Відповідальний за випуск В.А.Гладков

 

Редактор О.Д.Дьордійчук

 

_______________________________________________________________

Підписано до друку. Формат паперу А5, папір для тиражувальних апаратів, друк – на різографі.

Замовлення №, тираж.

_______________________________________________________________

Надруковано видавничо-друкарським комплексом Київського університету економіки і технологій транспорту

03049, м.Київ-49, вул. Миколи Лукашевича, 19