ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Лекція №3 Сортування масивів

План

1. Основні поняття про алгоритми упорядкування даних

2. Сортування бульбашкою.

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

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

  1. Основні поняття про алгоритми упорядкування даних

Дуже часто при розв'язуванні задач, пов'язаних з обробкою масивів, необхідно виконувати сортування його елементів за зростанням або спаданням. Такі задачі мають велике практичне значення.

Впорядкування даних є досить актуальним. Проблеми впорядкування виникають у різних застосуваннях, зокрема, в базах даних. У неупорядкованому масиві з п елементів пошук потрібного даного виконують методом перебирання усіх значень. Такий підхід потребує виконання у найгіршому випадку п операцій порівняння. Якщо ж масив упорядкований, то операцій порівняння потрібно лише . Тому перед пошуком даних масив спочатку необхідно упорядкувати, тобто переставити елементи місцями так, щоб вони розташовувалися за зростанням або спаданням значень.

Є багато способів упорядкування масивів. їх можна поділити на прямі методи та поліпшенні. До прямих методів належать:

• метод обміну (метод «бульки»);

• метод мінімальних елементів;

• метод вставок.

Поліпшені методи — це методи Шелла, Хоара (швидке упорядкування), пірамідального упорядкування, злиття тощо.

Кожний метод характеризується кількістю порівнянь і перестановок елементів, які асимптотично залежать від кількості елементів п (інколи цю характеристику називають порядком чи складністю методу); обсягом використаної пам'яті та часом виконання програми.

Поліпшені методи упорядкування використовують меншу кількість порівнянь та перестановок елементів. Зазвичай вони особливо ефективні для упорядкування великих масивів даних. Для наборів даних, які складаються з невеликої кількості елементів, ліпше застосовувати прямі методи упорядкування. Прямі методи впорядкування не потребують додаткової оперативної пам'яті.

Можна упорядковувати дані різних типів: числових, символьних, рядкових, застосовуючи один і той же алгоритм.

Без втрати загальності розглянемо послідовність з п натуральних чисел. Наведемо алгоритми, програми та характеристики декількох методів упорядкування даних за зростанням.

Сортування бульбашкою.

У методі обміну спочатку розглядають першу пару елементів масиву. Якщо перший елемент більший від сусіднього ( ), то їх міняють місцями. Далі другий елемент порівнюють із третім і, якщо потрібно, обмінюють місцями і т. д. Після порівнянь максимальний елемент буде розташований в кінці масиву, тобто там, де потрібно. Тепер знову розглядають масив, але вже без останнього елемента, і застосовують до нього метод обміну — другий за величиною елемент буде розміщений в масиві на передостанній позиції і т.д. Упорядковані елементи нагромаджуватимуться в кінці масиву. Елементи переміщаються до хвоста масиву подібно до бульбашок, які переміщаються на поверхню води під час кипіння. Звідси і друга назва — «метод бульбашок».

Якщо масив має елементів, то метод треба застосувати разів (кожного разу до меншої кількості елементів).

Кількість порівнянь утворює спадну арифметичну прогресію з елементами від до 1. Тому кількість операцій порівнянь , тобто . Кількість операцій обміну елементів у найгіршому випадку є порядку .

Розглянемо модель масиву з п'ятьма елементами ( = 5) — невпорядкований набір п'яти чисел:

4,2,7,9,1. Упорядкуємо його методом обміну.

Під час першого ( ) перегляду набору даних матимемо:

¨ 1-й крок: 4 > 2 — умова істина, тому міняємо 4 і 2 місцями, отримаємо 2,4,7,9,1;

¨ 2-й крок: 4 > 7 — умова хибна, обміну немає, послідовність залишається незміненою: 2,4,7, 9, 1;

¨ 3-й крок: 7 > 9 — умова хибна, запишається 2,4,7, 9,1;

¨ 4-й крок: 9 > 1, тому міняємо 9 і 1 місцями, отримаємо 2,4,7,1,9.

Під час першого перегляду було порівняння і два обміни.

Для розглядаємо вже набір з чотирьох елементів (2, 4, 7, 1) і застосовуємо до нього метод обміну, отримаємо 2,4,1,7,9.

Для. розглядаємо лише перші три елементи. Отримаємо 2,1,4,7,9.

Для розглядаємо перші два і отримуємо 1,2,4,7,9.

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти