ПОШУК, СОРТУВАННЯ ТА ПОНЯТТЯ СКЛАДНОСТІ У ПРОГРАМУВАННІ

1. Пошук за ключем у масиві

1.1. Лінійний пошук

Читачеві колись доводилося шукати своє прізвище в списках, надрукованих не в алфавітному порядку? Або уявіть собі словник на 100 тисяч слів, розташованих там без упорядкування за алфавітом. Потрібне слово шукати там доведеться довго. Дуже довго. Звичайно, якщо воно випадково не потрапило в самісінький початок. А якщо в кінець чи середину? А пошук слова в "нормальному" словнику займає чомусь кілька секунд незалежно від його розташування там.

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

Нехай елементи масиву A[1], A[2], … , A[n] та змінна key ("ключ") мають той самий тип T. Пошук за ключем полягає в пошуку номера i такого, що A[i]= key. За відсутності такого номера результатом будемо вважати 0. Нехай діють означення

const maxn = 1000;

type T = integer;

Indx = 1 .. maxn; (17.1)

ArT = array [Indx] of T;

Подамо розв'язання задачі функцією

function srcseq ( var A : ArT; n : Indx; key : T) : integer;

var i : integer;

begin

i := 0;

while ( i 1.* Вам треба дізнатися про день народження, тобто місяць і число, свого співбесідника (рік неважливий). Ви можете задавати питання типу: "День народження такого-то числа такого-то місяця?". Відповідь може бути "так", "раніше" або "пізніше". Скільки питань достатньо, щоб дізнатися про будь-який день народження?

2. Бульбашкове сортування

Розглянемо найпростіший (і найгірший з точки зору витрат часу) спосіб сортування масиву. Нехай A[1], A[2], ... , A[n] – масив із довільними значеннями елементів. Порівняємо A[1] і A[2]: якщо A[1]>A[2], то поміняємо їхні значення місцями. Потім порівняємо A[2] і A[3] та за необхідності обміняємо їхні значення. В результаті A[3] має найбільше значення серед A[1], A[2], A[3]. Продовжимо такі порівняння та обміни до кінця масиву:

для всіх i від 1 до n-1 виконати

якщо A[i]>A[i+1], то

значення A[i] та A[i+1] обмінюються.

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

Далі почнемо все спочатку і перемістимо друге за величиною значення до передостаннього елемента A[n-1], перетворивши, наприклад, на . Потім третє за величиною значення перемістимо до A[n-2] тощо. Останній крок складається лише з порівняння A[1] A[i+1]

then swap (A[i], A[i+1])

end

Тут і далі процедура swap задає обмін значень своїх параметрів. Як бачимо, разом виконується (n-1)+(n-2)+…+1= n (n-1)/2 порівнянь. Очевидно, що найбільше можливе число елементарних дій за цим способом прямо пропорційне кількості порівнянь. Тому час сортування масиву з n елементів у такий спосіб прямо пропорційний n (n-1).

Задачі

2.* Якщо при черговому виконанні циклу із заголовком for i:=1 to k-1 do процедури Bubbles1 не було жодного обміну, то масив уже відсортовано. Тому подальші проходи масивом зайві. Переробити процедуру сортування так, щоб її виконання закінчувалося за відсортованого масиву.

3. Сортування вибором здійснюється так. Проглянемо елементи масиву від першого до останнього, визначимо елемент із найменшим значенням, та обміняємо це значення з першим. Потім так само виберемо найменше значення серед A[2]...A[n] і обміняємо його зі значенням A[2], потім виберемо наступне найменше та обміняємо з A[3] тощо. Написати процедуру сортування вибором.

4. Сортування простими вставками дозволяє створити відсортований масив із значень, що читаються, наприклад, із клавіатури. Перше значення записується на перше місце, тобто присвоюється першому елементу масиву. Друге значення порівнюється з першим і, якщо перше менше, то воно "витісняється" на друге місце. Інакше нове значення йде на друге місце. Потім третє порівнюється з другим та записується або на третє місце, або витісняє значення з другого місця на третє та порівнюється з тим, що на першому місці. Наприклад, за читання послідовності значень 3, 1, 2 створюються послідовності значень у масиві , , .

Узагалі, після читання k-1 елемента маємо відсортовану частину масиву A[1]A[2]...A[k-1]. Нове значення v порівнюємо зі значенням A[k-1]. Якщо A[k-1]>v, то значення A[k-1] зсуваємо на k-е місце. Після цього порівнюємо v зі значенням A[k-1]: якщо A[k-2]>v, то A[k-2] зсуваємо на (k-1)-е місце тощо. Коли за чергового порівняння A[i]Нехай A позначає алгоритм розв'язання деякої масової задачі. Позначимо через F(A, екземпляр) кількість елементарних дій у процесі розв'язання цього екземпляра задачі за алгоритмом A, а через F(A, n) – максимум кількості елементарних дій серед усіх екземплярів розміру n.

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

F(A, n)=4 n (n-1)/2.

Кожному n = 1, 2, 3, … відповідає певне значення F(A, n), тобто ми маємо функціональну залежність між розмірами n та максимальними кількостями елементарних дій, виконуваних за алгоритмом A. Ця функція називається складністю алгоритму A. Алгоритми практично всіх реальних задач мають складність, монотонно неспадну за n.

Аналітичне задання функції F(A, n) для реальних алгоритмів, як правило, неможливе й не потрібне. Велике практичне значення має так званий порядок зростання F(A,n) за n. Він задається за допомогою іншої функції з простим аналітичним виразом, яка є оцінкою для F(A, n).

Функція G(n) є оцінкою для функції F(n), або F(n) є функцією порядку G(n), коли існують такі додатні скінченні числа C1 і C2, що за деякого m при всіх n > m

C1 G(n)  F(n)  C2 G(n).

Така залежність між функціями позначається за допомогою знака "О":

F(n) = O(G(n)).

Для задання порядку зростання інколи користуються іншим означенням: функція F(n) називається функцією порядку G(n) за великих n, якщо , де C>0, C 2 маємо

0.5 n2 mr + r - 1 then

begin X[k] := Y[i]; i := i + 1 end else

if Y[i] lp,

і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.

Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2kvar m, k : integer;

begin

if l>=r then exit;

m:=(l+r) div 2;

Mrgrec(A, B, l, m); Mrgrec(A, B, m+1,r);

mrg(A, l, m-l+1, r-m, B);

for k:=l to r do A[k]:=B[k];

end;

Ця процедура набагато коротше нерекурсивної процедури Merges, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції".

Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.

Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два – ні. Розглянемо два алгоритми, позбавлені цього недоліку.

4.2. Піраміда, вона ж дерево

Уявіть собі, що ми розташували елементи масиву рядками, щоразу подвоюючи їх кількість: у першому рядку – перший елемент, у другому – елементи з індексами 2, 3, у наступному – 4, 5, 6, 7, далі 8, 9, 10, 11, 12, 13, 14, 15 тощо. Останній рядок може виявитися неповним. Наприклад, за кількості елементів n=12 маємо таку піраміду індексів:

1

2 3

4 5 6 7

8 9 10 11 12

Елементи цієї піраміди будемо називати вузлами.

Між вузлами проведемо стрілки: від 1 – до 2 та 3, від 2 – до 4 та 5, від 3 – до 6 та 7 тощо, тобто від кожного вузла k до 2k та 2k+1, де kКоли 2*i>j, то властивість (17.2) не може бути порушеною в частині масиву A[i], … , A[j].

За дії означень (17.1) відновлення задається рекурсивною процедурою reorg:

procedure reorg ( var A : ArT; i, j : Indx );

var k : Indx;

begin

if 2*i = j then

if A[i] a[c[ll]].x)and(tp.x a[c[rr]].y)or

not( (tp.x>a[c[ll]].x)and(tp.x20. (Задача про два станки) Є n деталей, кожна з яких проходить обробку спочатку на першому станку, потім на другому. Кожний станок здатний обробляти одночасно одну деталь і готовий до обробки наступної деталі одразу після обробки попередньої. Відомий час обробки кожної деталі на кожному із станків. Упорядкувати деталі таким чином, щоб час від початку обробки першої деталі до закінчення обробки останьої був якнайменшим. Наприклад, якщо перша деталь обробляється на станках 20 і 10 одиниць часу, а друга – 10 і 20, то за порядку деталей (перша, друга) одержимо час 50, а за порядку (друга, перша) – 40.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать