Наївне» сортування

Кулькове» сортування

До розд. 3.3) «Кулькове» і «наївне» сортування одномірного масиву

Вправи

Питання для роздумів

Рекурентна формула, коректність програми.

1. Не могли б Ви спростити умову в текстах програмних кодів 3.15 і 3.16:
   If Номер=1 Or Номер=2 Then?
2. Як Ви думаєте, чому в кодах 3.15 — 3.17 змінна Число і значення функцій Фібоначчі1 і Фібоначчі3 мають тип Long?
3. Як Ви думаєте, навіщо в програмному коді 3.17 введено локальну змінну r5# і чому в неї такий суфікс?

1. Напишіть програму генерації ряду Фібоначчі, у якій за допомогою функції Timer встановлюється обмеження часу її роботи (наприклад, 10 сек). Яке по рахунку число Фібоначчі буде генерованим на Вашому комп'ютері останнім?
2. Напишіть визначення рекурсивної функції, що повертає суму членів геометричної прогресії. Аргументи функції: перший член прогресії, знаменник прогресії і число членів прогресії. Напишіть аналогічне визначення рекурсивної процедури.

Програма для цього виду сортування виглядає дуже лаконічною:

Код 3.18

Опис її роботи пояснює, чому даний вид сортування називається кульковим.

У масиві послідовно проглядаються елементи від 1-го до передостаннього. І для кожного i-го елемента масив проглядається від (i+1)-гo елемента до кінця. Якщо даний (і-й) елемент виявиться більшим від одного з тих елементів, що знаходяться після нього, вони міняються місцями, (i-й елемент, немов кулька у повітрі, «спливає» нагору — у напрямку до верхнього краю масиву.)

Кульковий метод гірший (менш ефективний), ніж розглянуті в розд. 3.3 методи сортування вставкою і вибором. Однак, не потрібно відразу «ставити на ньому хрест». Він підійде для тих випадків, коли впорядковується вже «майже» відсортований масив — масив, у якому порядок порушений у якомусь одному місці.

Наприклад, застосування кулькового методу до масиву 1, 2, 9, 4, 6, 8, 10, 12 дасть тільки 3 обміни значеннями: 9 з 4, 9 з 6 і 9 з 8.

Цей вид сортування недарма називається наївним. Його ідея нескладна — створюються всі можливі перестановки (Про те, що таке перестановка, розповідалося в розд. 3.1. У прикладі 3.1 розглядалися перестановки трьох чисел. Їх всього 6. А число перестановок шести чисел уже дорівнює 720.) елементів масиву. І для кожної з них робиться перевірка — чи виконується для неї умова неубування/зростання. Очевидно, що працює такий алгоритм дуже повільно.

Наступний код містить програму для додатка, яка демонструє роботу алгоритму наївного сортування.

Код 3.19

На початку роботи додатка, після натискання командної кнопки на екранній формі, одномірний Macuв (1 To 6) заповнюється шістьма числами, а потім викликається процедура Перестановка.

Аргументи процедури Перестановка — це сам масив, верхня границя індексу цього масиву і номер елемента масиву, починаючи з якого елементи масиву міняються місцями в процесі формування нової перестановки. Рекурсивні виклики цієї процедури створюють усі перестановки елементів масиву. Кожна нова перестановка поміщається у Вікно списку у вигляді ланцюжка наступного виду:
«7 5 7 2 3 7».

Крім того, при кожному рекурсивному виклику перевіряється умова впорядкованості отриманої перестановки — запускається процедура Порядок. Її аргументи — це масив і його розмір, а значення, що повертається функцією, — це або True (Істина), або False (Неправда).

Якщо функція Порядок повертає Істину, перестановка разом зі своїм номером поміщається в текстове поле, призначене для результату.

На мал. 3.4 приведений вид екранної форми додатка, за допомогою якого демонструється алгоритм «наївного» сортування.

Мал. 3.4. Екранна форма з демонстрацією результату роботи «наївної» сортування масиву 7, 5, 5, 2, 3, 7

Для визначення числа перестановок (факторіала числа N) використовується властивість ListCount об'єкта Вікно списку. Значення цієї властивості — кількість елементів списку (Нагадаємо, що в математиці факторіал числа N позначається так: N!.).

Нові поняття:

Дата добавления: 2014-12-23