Лекція No14 Сортування масивів. Метод Шелла

ПЛАН ЗАНЯТТЯ No 21

Дата: група: Дисципліна: Алгоритми та структури даних. Тема: Сортування масивів. Метод Шелла. Мета:

Методична: закріпити методику проведення лекційного заняття. Дидактична: розглянути сортування масивів методом Шелла . Виховна: зміцнювати бажання вивчення дисципліни.

Вид заняття: лекційне заняття. Форми та методи проведення заняття: інформаційно- рецептивні, фронтальне опитування, викладання нового матеріалу.

Міжпредметні зв’язки:

• Дисципліни, що забезпечують: математичний аналіз, лінійна алгебра та аналітична геометрія.
• Дисципліни, що забезпечуються: алгоритмічні мови та програмування, об'єктно-орієнтоване програмування.

Науково-методичне забезпечення:

1. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное

пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с. 2. Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных

в Delphi: Пер. с англ./ Бакнелл Джулиан М.: СПб ООО «ДиасофтЮП», 2003. – 560 с.

ХІД ЗАНЯТТЯ.

1. Організаційний момент: перевірка відсутніх, зовнішнього вигляду,

готовності аудиторії. 2. Повідомлення теми, формування мети та основних завдань. 3. План викладання нового матеріалу: надано в конспекті лекції. 4. Актуалізація опорних знань:

• Дати визначення похідної;
• Дати визначення первісної, невизначеного інтегралу;
• Дати визначення диференціалу;
• Визначити зв’язок неперервності та диференційованості;
• Необхідні умови інтегрованості функції;
• Таблиця похідних, таблиця інтегралів основних елементарних функцій.

5. Вивчення нового матеріалу: Тема лекції: Сортування масивів. Метод Шелла.

• Мотивація вивчення матеріалу: диференціальні рівняння – це основний сучасний засіб розв’язання прикладних задач, який дає змогу описати математичну модель на зрозумілій мові. Тому, сучасному студенту необхідно вміти не тільки розв’язувати основні типи звичайних диференціальних рівнянь, але моделювати за допомогою диференціальних рівнянь текстові задачі.
• План вивчення нового матеріалу: надається в конспекті лекції. 6. Виклад нового матеріалу: конспект лекції надається. 7. Закріплення нового матеріалу: обговорення окремих питань алгоритмів. 8. Підведення підсумків заняття. 9. Домашнє завдання:

Викладач М.П.Леверя

Лекція No14 Тема: Сортування масивів. Метод Шелла.

План 1. Сортування масивів методом Шелла.

1.Сортування масивів методом Шелла.

Сортування Шелла — це алгоритм, що є узагальненням алгоритму сортування вставками. Ідея алгоритму полягає в обміні елементів, розташованих не тільки поряд, як в сортуванні методом вставок, але і далеко один від одного, що значно скорочує загальне число операцій переміщення елементів.

Для прикладу візьмемо масив з 16 елементів. Спочатку продивляються пари в з 16 елементів. Спочатку продивляються пари з кроком 8. Це пари елементів 1-9, 2-10, 3-11,4-12, 5-13, 6-14, 7-15, 8-16. Якщо значення елементів в парі не впорядковані за збільшенням, то елементи міняються місцями. Назвемо цей етап 8-сортуванням.

Наступний етап — 4-сортування, на якому елементи у масиві діляться на четвірки: 1-5-9-13, 2-6-10-14, 3-7-11-15,4-8-12-16. Виконується сортування в кожній четвірці.

Наступний етап — 2-сортування, коли елементи у масиві діляться на 2 групи по 8: 1-3-5-7-9-11-13-15 і 2-4-6-8-10-12-14-16. Виконується сортування в кожній вісімці. Нарешті весь масив упорядковується методом вставок. Оскільки дальні елементи вже перемістилися на своє місце або знаходяться поблизу від нього, цей етап буде значний менш трудомістким, ніж при сортуванні вставками без попередніх «дальніх обмінів». Тому сортування Шелла виконує декілька впорядкувань вставками, кожен раз порівнюючи і переставляючи елементи, що знаходяться на різній відстані один від одного. Сортування Шелла не є стабільним(не гарантує збереження порядку елементів, які вже відсортовані).

Розглянемо приклад сортування масиву з 16 елементів за допомогою алгоритму Шелла:

1. спочатку сортуємо 8 груп по 2 елементи:
2. тепер сортуємо 4 групи по 4 елементи:

Очевидно, лише останнє сортування необхідне, щоб розташувати всі елементи по своїх місцях. Так навіщо потрібні попередні?- Вони просувають елементи максимально близько до відповідних позицій, так що при останньому проході число переміщень буде дуже маленьке. так як послідовність і так майже відсортована. Єдиною характеристикою сортування Шелла є приріст - відстань між сортованими елементами. В кінці приріст завжди рівний одиниці – метод завершується звичайним сортуванням вставками, але саме послідовність приростів визначає зростання ефективності алгоритму.

Приклад. Відсортувати масив х з n елементів в порядку зростання методом Шелла.

Алгоритмічна мова Блок-схема алг Сортування Шелла (нат N, дійсн Мас A[1:N])

арг. N, A рез. A поч дійсн. P; нат M, i, j, f

Ввести n для і від 1 до N нц

Ввести A[i] кц --- сортування массиву методом Шелла M:=[N/2]

поки M≥1 нц

для i від 1+M до N нц

P:=A

i j:=i-M f:=0

поч

N

i:=1,N

Введення A

i

M:=[N/2]

1

3. тепер сортуємо 2 груп по 8 елементи:
4. нарешті сортуємо всі 16 елементів:
5. В результаті ми отримаємо посортований масив:

поки j≥1 и f=0

нц

якщо P < A

j то

A

j+M

1

M≥1

f:=0

P < A

j

f:=1

:=A

j j:=j-M інакше f:=1 все кц A

j+M

M:=[M/2]

i :=1+M, N := P кц M:=[M/2] кц

для і від 1 до N

нц

Вивести А[i] кц кін

j≥1 и f=0

+

A

j+M

+

2. Контрольні питання
3. Алгоритм сортування масиву методом Шелла.

P:=A

i

j:=i-M

A

j+M

:= P

:=A

j j:=j-M

i:=1,N

Виведення A

i

кін

Список літератури:

1. Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных

в Delphi: Пер. с англ./ Бакнелл Джулиан М.: СПб ООО «ДиасофтЮП», 2003. – 560 с. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное

пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.

Для перегляду тексту необхідно залогінитись.