Сортування одновимірного масиву

Вправи

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

Рекурсивний об'єкт, факторіал числа, рекурсивний виклик, рекурсія, рекурсивна функція, глибина рекурсії, рекурсивний спуск, рекурсивний підйом.

1. Як буде змінюватися значення змінної Добуток на рекурсивному спуску при роботі функції Факторіал 1, якщо максимальна глибина рекурсії дорівнює п'яти?
2. Чи будуть розрізнятися значення максимальної глибини рекурсії при роботі функцій Факторіал 2(0) і Факторіал 2(1)?
3. Як Ви думаєте, чому у визначенні функції Факторіал 2 (код 3.6) її аргумент має тип Integer, а значення — тип Long?

1. За аналогією з кодом 3.5 і 3.6 напишіть визначення двох функцій, що обчислюють суму квадратів натуральних чисел від 1 до N. Створіть невеликий проект у середовищі Visual Basic, за допомогою якого Ви зможете перевірити роботу цих функцій.
2. Перевірте твердження, що міститься в 3-у питанні до даного розділу. Для цього визначте функцію, що викликає саму себе без умов, напишіть програму з визначенням цієї функції і запустіть її.
3. Напишіть визначення і перевірте працездатність процедур, за допомогою яких обчислюється факторіал числа. (Їхня єдина відмінність від функцій Факторіал 1 і Факторіал 2 — наявність вихідного параметра.)

У розд. 3.1 була розглянута задача сортування всього трьох чисел. А якщо чисел багато (20, 100, 100000)?

Немає потреби пояснювати, що як при декларативному, так і при процедурному способі вирішенні цієї задачі виникнуть проблеми.

Про розв'язок однієї з них (збереження великої кількості різних чисел у масивах) йшла мова раніше.

Друга проблема полягає в тому що в розглянутих алгоритмах кількість порівнянь буде різко зростати зі збільшенням кількості порівнюваних чисел (згадайте відповіді на питання до попереднього розділу).

Вирішення другої проблеми — тема цього і наступних розділів даної глави.

По-перше, як і в інших алгоритмах, розглянутих в попередній главі, в алгоритмах сортування можна використовувати вже знайомі Вам цикли — повторювані не дуже складні комбінації порівнянь чисел. І від кількості чисел буде залежати не кількість порівнянь на одному кроці циклу, а тільки кількість цих кроків.

По-друге (і це головна тема даної глави), в алгоритмах сортування ми будемо застосовувати ідею рекурсії.

Спочатку вирішимо більш просту задачу, алгоритм якої ми дуже коротко описали на початку глави, — задачу рекурсивного пошуку максимального з N чисел.

Використовуючи цей алгоритм, визначимо рекурсивну функцію МаксЕлемент, що буде повертати максимальний елемент одномірного масиву Масив. Аргументів у цієї функції два: Масиви і n (сам масив і число його елементів).

Код 3.7

Дуже часто потрібно знаходити не значення максимального елемента, а його позицію — порядковий номер у масиві. Наступний код дуже нагадує код 3.7:

Код 3.8

А тепер перейдемо до сортування одномірного масиву. Сортуванням одномірного масиву називається така процедура, у результаті якої його елементи змінюють свої порядкові номери так, що кожен наступний у списку елемент не менший (У мові Visual Basic можна сортувати не тільки числа, але і рядки. При цьому вони вистроюються в лексикографічному порядку, як в енциклопедії. Один рядок вважається більшим за інший, якщо при їхньому перегляді зліва направо і відсіканні від них по одному символі виявляється, що код ASCII символу першого рядка більший за код ASCII символу другого рядка, або ж якщо другий рядок є лівим підрядком першого рядка. Наприклад: рядок «Петрівна» більший рядка «Петрович», а рядок «Петрович» більший рядка «Петров». (Не забудьте, що символ пробілу теж має код ASCII.)), ніж попередній.

Приклад 3.3. Початковий порядок елементів масиву M був таким:
M(0)=5, M(1)=15, M(2)=12, M(3)=2, M(4)=22, M(5)=5.

Після сортування порядок елементів масиву M став таким:
M(0)=2, M(l)=5, M(2)=5, M(3)=12, M(4)=15, M(5)=22.

Існує кілька алгоритмів сортування. Вони відрізняються один від одного складністю і швидкістю роботи. Якщо говорити більш точно, то не швидкістю, а ефективністю — залежністю часу роботи алгоритму від довжини сортованого масиву. Як правило, чим ефективніше працює алгоритм, тим він складніший. (За все треба платити!)

Розглянемо два з них (далеко не найгірші). Це алгоритми сортування вибором і сортування вставкою. Ще два алгоритми сортування (кулькового та наївного сортування) приведені в розд. 3.6.

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