Пошук, сортування та поняття складності, Детальна інформація

lb := 1; hb := n;

i := (lb + hb) div 2;

while (lb < hb) do

begin

if A[i] = key then break else

if A[i] > key

then hb := i - 1 { key може бути лише ліворуч від A[i] }

else lb := i + 1; { key може бути лише праворуч від A[i] }

i := (lb + hb) div 2

end;

{ lb >= hb або A[i] = key }

if (i=0) or (i=n+1) then srcbin := 0 else

if A[i] = key then srcbin := i else srcbin := 0

end

Виконання тіла циклу while вимагає сталого числа елементарних дій незалежно від значень змінних A, key, i, lb, hb. Звідси загальна кількість дій прямо пропорційна кількості повторень тіла циклу while. Але за кожного повторення різниця hb-lb зменшується принаймні у два рази. Спочатку hb-lb = n - 1, тому виконань тіла циклу не більше ніж log2n , звідки час виконання функції t2 = O(log2n). Ця пропорційність зумовлює ще одну назву описаного пошуку – логарифмічний.

Чим більше n, тим більше відношення n до log2n. Наприклад, за n=10000 це більше 500. Коли треба відшукати значення один раз, можливо, комп'ютер упорається досить швидко і за лінійним алгоритмом. Але в реальних задачах доводиться шукати за ключем багаторазово, і різниця між лінійним і двійковим пошуком стає дуже відчутною.

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

Існує кілька інших способів швидкого пошуку в масивах. Їх докладне описання є в книзі [Кнут, т.3].

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] має найбільше значення. Наприклад, послідовність значень <3, 4, 2, 1> перетвориться на <3, 2, 1, 4>.

Далі почнемо все спочатку і перемістимо друге за величиною значення до передостаннього елемента A[n-1], перетворивши, наприклад, <3, 2, 1, 4> на <2, 1, 3, 4>. Потім третє за величиною значення перемістимо до A[n-2] тощо. Останній крок складається лише з порівняння A[1]
За дії означень (17.1) опишемо бульбашкове сортування такою процедурою (bubble – це англійське "бульбашка"):

procedure Bubbles1 (var A: ArT; n: Indx);

var i, k: Indx;

begin

for k := n downto 2 do