Урок 43. Алгоритм сортування методом обміну
Пригадайте!
Завдання 1. Відсортуйте числа: 34, 45, 1, 23, 56, 17, 100 методом вибору.
Завдання 2 (Задача на повторення роботи з масивами). Знайти суму додатних елементів одновимірного масиву (таблиці) всі елементи якого є цілими числами.
Прочитайте!
Алгоритм сортування методом обміну
У шеренгу стали 5 учнів. Порівняйте зріст перших двох. Якщо перший вищий за другого, поміняйте їх місцями, за потреби — другого і третього і т. д. Як розмістяться учні?
Розглянемо сутність алгоритму сортування масиву в порядку зростання значень його елементів методом обміну.
З описаного випливає, що ознакою упорядкованості масиву є те, що після завершення його перегляду жодної перестановки елементів не було.
У прикладі 2 наведено порядок переміщення максимального числа на крайню праву позицію у масиві [4, 2, 5, 7, 6, 1]. Жирним шрифтом виділено елементи, які порівнюються.
Отже, після першого перегляду масиву елемент із максимальним значенням буде розташований на останній позиції. Розробимо алгоритм сортування методом обміну. В алгоритмі використано такі позначення: p — індекс правої межі поточної ділянки масиву; y — ознака наявності перестановки: на початку кожного зовнішнього циклу y набуває значення True.
Якщо після завершення зовнішнього циклу вона має значення True, це означає, що перестановок під час останнього перегляду не було; якщо y = False, то відбулася принаймні одна перестановка; i — індекс поточного елемента масиву; z — змінна, призначена для тимчасового зберігання значення елемента масиву під час перестановки елементів. Розглянемо алгоритм сортування масиву методом обміну, який може бути таким.
Програму реалізації алгоритму зображено на рисунку:
Результат виконання програми: 7, 16, 20, 31, 51, 63, 100.
Самостійне виконання вправ
Завдання 1. Визначте кількість операцій порівняння в алгоритмі сортування методом обміну в процесі впорядкування масиву 100, 20, 41, 30, 35.
Завдання 2. Дано масив чисел: 34, 12, 8, 5, 20, 17. Виконайте його сортування за допомогою методу обміну в порядку зменшення чисел.
-
Тема 1.Бази даних
- Урок 1. Поняття бази даних. Поняття, призначення й основні функції систем управління базами даних.
- Урок 2. Поняття моделі подання даних, основні моделі подання даних. Проектування баз даних. Поняття сутності, атрибута, ключа, зв’язку. Модель «сутність-зв’язок» предметної області. Класифікація зв’язків за множинністю та обов’язковістю. Бази даних в інформаційних системах.
- Урок 3. Основні відомості про СУБД MS Access. Створення й уведення структури таблиць. Поняття таблиці, поля, запису. Створення таблиць, означення полів і ключів у середовищі СКБД. Властивості полів, типи даних.
- Урок 4. Модифікація структури таблиць. Ключові поля, індекси, зв’язування таблиць.
- Урок 5. Уведення, пошук і редагування даних у таблиці.
- Урок 6. Інструктаж з БЖД Практична робота 1. Створення структури таблиць і введення вмісту.
- Урок 7. Сортування та фільтрація записів. Операції над таблицями.
- Урок 8. Розв’язання задач на створення таблиць та зв’язків
- Урок 9. Розв’язання задач на створення таблиць та зв’язків
- Урок 10. “ЗАПИТИ Загальні відомості про запити. Створення й виконання запитів на вибірку даних.”
- Урок 11. Запити з функціями і з полями, що обчислюються.
- Урок 12. Запити з параметрами. Перехресні запити.
- Урок 13. Інструктаж з БЖД. Практична робота 3.Запити з функціями та з полями, що обчислюються.
- Урок 14. Запити на змінення даних.
-
Тема 2. Форми. Звіти. Імпорт та експорт даних.
- Урок 18. Створення форм за допомогою простих засобів. Елементи керування та властивості форм.
- Урок 19. Поняття звіту. Автоматичне створення звіту. Створення звіту за допомогою конструктора звітів.
- Урок 20. Інструктаж з БЖД Практична робота 4. Створення форм, звітів, запитів..
- Урок 21. Призначення, основні поняття та терміни мови SQL. Найпростіші запити мовою SQL у системі Access.
- Урок 22. Запити з умовою. Групування запитів.
- Урок 23. Сутність імпорту та експорту об’єктів. Імпорт об’єктів з однієї бази даних в іншу. Експорт об’єктів з однієї бази даних в іншу.
- Урок 25. Інструктаж з БЖД. Практична робота 5. Основи мови запитів SQL. Імпорт та експорт об’єктів бази даних.
- Урок 30. Практикум з використання інформаційних технологій
-
Тема 3. Алгоритми
- Урок 31. Повторення теми «алгоритми» вивченої в 10 класі. Методи проектування і подання алгоритмів.
- Урок 32. Кодування алгоритмів. Поняття складності алгоритмів. Математична модель, вибір структури даних
- Урок 33. Пошук оптимального алгоритму розв’язання
- Урок 34. Оцінка та аналіз ефективності алгоритму
- Урок 35. Інструктаж з БЖД. Практична робота 6. Реалізація алгоритму мовою програмування
- Урок 36. Розв’язання задач на оцінку аналізу ефективності алгоритму
- Урок 37. Основні поняття теорії чисел: системи числення
- Урок 38. Робота з великими числами
- Урок 39. Факторизація чисел. Інструктаж з БЖД. Практична робота 7. Основні поняття теорії чисел.
- Урок 42. Алгоритми сортування. Квадратичні алгоритми сортування. Алгоритми сортування вибором.
- Урок 43. Алгоритм сортування методом обміну
- Урок 44. Сортування вставленням
- Урок 45. Сортування злиттям.
- Урок 48. Бінарний пошук
- Урок 49. Пошук максимального і мінімального елементів у масиві
- Урок 50. Поняття про пошук із поверненням і тернарний пошук.
- Урок 51. Інструктаж з БЖД. Практична робота 9. Розв’язування практичних завдань
- Урок 52. Практикум з використання інформаційних технологій
- Урок 53. Практикум з використання інформаційних технологій
-
Тема 4. Обробка рядків
- Урок 61. Обробка рядків. Основні відомості про рядки й операції над ними
- Урок 62. Функції і методи опрацювання рядків
- Урок 63. Функції і методи опрацювання рядків
- Урок 64. Приклади програм обробки рядків
- Урок 65. Основні поняття і терміни теорії графів.
- Урок 66. Способи подання графів у комп’ютері.
- Урок 67. Пошук у глибину та ширину
- Урок 68. Визначення найкоротшого шляху у графі. Алгоритм Дейкстри та його реалізація
- Урок 69. Алгоритм Флойда-Уоршела та його реалізація. Інструктаж з БЖД. Практична робота №10 “Реалізація алгоритму пошуку”
- Урок 70. Динамічне програмування.
- Урок 71. Жадібні алгоритми
- Урок 72. Критерії застосування задач динамічного програмування
- Урок 74. Базові поняття обчислювальної геометрії
- Урок 75. Операції над векторами. Векторний добуток
- Урок 76. Обчислення площі многокутника
- Урок 79. Інструктаж з БЖД. Практична робота №12 “Основи обчислювальної геометрії”
-
Веб-технології
- Урок 85. Основні тренди у веб-дизайні.
- Урок 86. Види і типи сайтів. Цільова аудиторія.
- Урок 87. Інформаційна структура сайта.
- Урок 88. Системи керування вмістом
- Урок 89. Запуск проекту «Розробка власного сайта»
- Урок 90. Адміністрування сайта
- Урок 91. Інструменти веб-розробника
- Урок 92. Інструктаж з БЖД. Практична робота №13 “Створення макету інформаційної структури сайта”
- Урок 93. Мова гіпертекстової розмітки.
- Урок 94. Мова гіпертекстової розмітки. Списки на веб-сторінках
- Урок 95. Каскадні таблиці стилів
- Урок 96. Проектування та верстка веб-сторінок. Адаптивна верстка.
- Урок 97. Кросбраузерність.
- Урок 98. Інструктаж з БЖД. Практична робота №14 “Створення веб-сторінок”
- Урок 99. Графіка для веб-середовища.
- Урок 100. Анімаційні ефекти.
- Урок 103. Інструктаж з БЖД. Практична робота №15 “Графіка та мультимедіа для веб-середовища”
- Урок 105. Веб-програмування та інтерактивні сторінки.
- Урок 106. Хостинг сайта. Інструктаж з БЖД. Практична робота №16 “Розміщення сайту на сервері”
- Урок 108. Валідація та збереження даних форм.
- Урок 110. Правила ергономічного розміщення відомостей на веб-сторінці.
- Урок 111. Пошукова оптимізація та просування веб-сайтів. Інструктаж з БЖД. Практична робота №17 “Оцінка сайту. Просування сайту”
-
Парадигми програмування. повторення вивченого матеріалу
0.00 на основі 0 рейтингів