ПЛАН ЗАНЯТТЯ No 19
Дата: група: Дисципліна: Алгоритми та структури даних. Тема: Сортування масивів. Метод вставки. Мета:
Методична: закріпити методику проведення лекційного заняття. Дидактична: розглянути сортування масивів методом вставки . Виховна: зміцнювати бажання вивчення дисципліни.
Вид заняття: лекційне заняття. Форми та методи проведення заняття: інформаційно- рецептивні, фронтальне опитування, викладання нового матеріалу.
Міжпредметні зв’язки:
- Дисципліни, що забезпечують: математичний аналіз, лінійна алгебра та аналітична геометрія.
- Дисципліни, що забезпечуються: алгоритмічні мови та програмування, об'єктно-орієнтоване програмування.
Науково-методичне забезпечення:
- Вирт Н. Алгоритмы и структуры данных: Пер с англ. – М.: Мир, 1989. –
360 с., ил. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное
пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.
ХІД ЗАНЯТТЯ.
- Організаційний момент: перевірка відсутніх, зовнішнього вигляду,
готовності аудиторії. 2. Повідомлення теми, формування мети та основних завдань. 3. План викладання нового матеріалу: надано в конспекті лекції. 4. Актуалізація опорних знань:
- Дати визначення похідної;
- Дати визначення первісної, невизначеного інтегралу;
- Дати визначення диференціалу;
- Визначити зв’язок неперервності та диференційованості;
- Необхідні умови інтегрованості функції;
- Таблиця похідних, таблиця інтегралів основних елементарних функцій. 5. Вивчення нового матеріалу: Тема лекції: Сортування масивів. Метод вставки.
- Мотивація вивчення матеріалу: диференціальні рівняння – це основний сучасний засіб розв’язання прикладних задач, який дає змогу описати математичну модель на зрозумілій мові. Тому, сучасному студенту необхідно вміти не тільки розв’язувати основні типи звичайних диференціальних рівнянь, але моделювати за допомогою диференціальних рівнянь текстові задачі.
- План вивчення нового матеріалу: надається в конспекті лекції. 6. Виклад нового матеріалу: конспект лекції надається. 7. Закріплення нового матеріалу: обговорення окремих питань алгоритмів. 8. Підведення підсумків заняття. 9. Домашнє завдання:
Викладач М.П.Леверя
Лекція No13 Тема: Сортування масивів. Метод вставки.
План 1. Сортування масивів методом вставки.
1.Сортування масивів методом вставки.
Сортування вставкою полягає в тому, що спочатку упорядковуються два елементи масиву. Потім робиться вставка третього елемента у відповідне місце по відношенню до перших двох елементів. Четвертий елемент поміщають в список з уже впорядкованих трьох елементів. Цей процес повторюється до тих пір, поки всі елементи не будуть упорядковані.
Перш ніж приступити до складання блок-схеми розглянемо наступний приклад. Нехай відомо, що в масиві з восьми елементів перші шість вже упорядковані, а сьомий елемент потрібно вставити між другим і четвертим. Збережемо сьомий елемент в допоміжній змінної, так як показано на мал. 1, а на його місце запишемо шостий. Далі п'ятий перемістив на місце шостого, четвертий на п'яте місце, а третє місце на четвертого, тим самим, виконавши зсув елементів масиву на одну позицію вправо. Записав вміст допоміжної змінної в третю позицію, досягнемо потрібного результату.
Рис. 3.10. Процес вставки елемента в масив Складемо блок-схему алгоритму (мал.2), враховуючи, що можливо описані вище дії доведеться виконати неодноразово.
Організуємо цикл для перегляду всіх елементів масиву, починаючи з другого (блок 4). Збережемо значення поточного i-го елемента в допоміжній змінній X, так як воно може бути втрачено при зсуві елементів (блок 5) і привласнимо змінній j значення індексу попереднього (i-1)-го елемента масиву (блок 6). Далі рухаємося по масиву вліво у пошуках елемента меншого, ніж поточний і поки він не знайдений Зрушуємо елементи вправо на одну позицію. Для цього організовуємо цикл (блок 7), який припинитися, як тільки буде знайдено елемент менше поточного. Якщо такого елемента в масиві не знайдеться і змінна j стане рівною нулю, то це буде означати, що досягнута ліва межа масиву, і поточний елемент необхідно встановити в першу позицію. Зсув елементів масиву вправо на одну позицію виконується в блоці 8, а зміна
лічильника j в блоці 9. Блок 10 виконує вставку поточного елемента в відповідну позицію.
Приклад. Відсортувати масив х з n елементів в порядку зростання методом вставки. Блок-схема:
На алгоритмічній мові: алг Сортування вибором (нат n, дійсн Мас Y[1:n])
арг. n, Y рез. Y поч дійсн. X; нат i, j
Ввести n -------- Введення масиву
для і від 1 до n
нц
Ввести Y[i] кц -------- Сортування методом вставки
для i від 2 до n нц X:= Y[i] j:=i-1 поки j>0 та X< Y[j]
нц Y[j+1]:= Y[j]
j:=j-1 кц Y[j+1]:=X
кц
-------- Виведення масиву для і від 1 до n
нц
Вивести Y[i] кц кін
- Контрольні питання
- Алгоритм сортування масиву методом вставки.
Список літератури:
- Алтухов Е.В., Рыбалко Л.А., Савченко В.С. Основы информатики и
вычислительной техники: Учеб. пособие для учащ. средн. спец. уч. заведений. – М.: Высш. шк., 1992. – 303 с. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное
пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.
Для перегляду тексту необхідно залогінитись.