Сортування простими включенням (бульбашки)

1. Цей метод звичайно використовують гравці в карти. Елементи (карти) умовно розділяються на впорядковану послідовність a₁,...,a_i-1 і вхідну послідовність a_i,...,a_n, яку потрібно впорядкувати. На кожному кроці, починаючи з другого, беруть поточний елемент невпорядкованої частини і передають у впорядковану послідовність, уставляючи його на підходяще місце. Вставка здійснюється “посуванням” елементів впорядкованої послідовності на певну кількість кроків вправо. Посування закінчується при виконання однієї з двох умов:

· знайдено елемент a_j із ключем меншим, чим ключ x (елемента, який впорядковується);

· досягнутий лівий кінець готової послідовності.

Оскільки наперед кількість таких “посувань” невідома, для практичної реалізації алгоритму доцільно застосувати цикл з передумовою. Застосування методу розглянемо на прикладі впорядкування масиву з 10 елементів. Елементи, що переміщувались вправо, виділимо кольором.

Вихідний масив:

44 55 12 42 94 18 06 67 32 13

Перший крок: переставляється елемент х=12

44 55 55 42 94 18 06 67 32 13

44 44 55 42 94 18 06 67 32 13

12 44 55 42 94 18 06 67 32 13

Другий крок: переставляється елемент х=42

12 44 55 55 94 18 06 67 32 13

12 44 44 55 94 18 06 67 32 13

12 42 44 55 94 18 06 67 32 13

Третій крок: переставляється елемент х=18

12 42 44 55 94 94 06 67 32 13

12 42 44 55 55 94 06 67 32 13

12 42 44 44 55 94 06 67 32 13

12 42 42 44 55 94 06 67 32 13

12 18 42 44 55 94 06 67 32 13

….

Процедуроа реалізації алгоритму має вигляд:

procedure straightinsertion (var a: massiv);

var

i,j: integer;

x: integer;

n1,n:integer;

begin

{границі масиву}

n1:= low(a);

n:= high(a);

{впорядкування}

for i:= n1+1 to n do

begin

x:=a[i];

j:=i-1;

while (j>=L) and (a[j]>x) do

begin

a[j+1]:=a[j];

j:=j-1;

end;

a[j+1]:=x;

end;

end;

 

Бінарний пошук елемента із вказаними властивостями у впорядкованому одновимірному масиві.

Якщо ж масив впорядкований, то можна з’ясувати, чи є дане число в масиві, іншим способом, значно ефективнішим. Пояснимо його на прикладі. Нехай маємо впорядкований за зростанням масив з 10 чисел: 2, 5, 8, 12, 13, 16, 17, 20, 22, 30 і деяке дане число х. Порівняємо це число із значенням елемента масиву, який знаходиться посередині масиву (з числом 13). Якщо дане число х дорівнює 13, то воно в масиві є, якщо ні, то з’ясуємо, чи більше дане число числа 13 (х>13). Якщо так, то його потрібно шукати тільки серед правої половини масиву, якщо ні, то тільки серед лівої половини масиву. Таким чином область пошуку звужується вдвічі. На наступному кроці поступаємо так саме: порівнюємо дане число із значенням елемента масиву, який знаходиться посередині тієї частини масиву, яка залишилися для пошуку. Знову або дане число дорівнює значенню цього елемента масиву, або залишаємо для пошуку або ліву, або праву половини тієї частини масиву, що залишилася, тобто область пошуку знову зменшується вдвічі.

Такий метод пошуку є значно ефективнішим, ніж попередній, бо значно швидше приводить до результату, особливо для великих N (максимум за [log₂N] +1 кроків, де N – кількість елементів у масиві, а квадратними дужками тут позначена ціла частина числа).

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

Відповідна процедура, в якій реалізується цей метод для впорядкованого масиву з 10 цілих чисел, виглядає так:

procedure TForm1.Button1Click(Sender: TObject);

var a: array [1..10] of Integer; i, x, left, right, m: Integer; f: Boolean;

Begin

for i:= 1 to 10 do

a[i]:= StrToInt(Memo1.Lines[i-1]);

x:= StrToInt(Edit1.Text);

left:= 1; // Початковий номер елемента тієї частини масиву, де відбуватиметься пошук

right:= 10; // Кінцевий номер елемента тієї частини масиву, де відбуватиметься пошук

f:= false; // Задане число в масиві поки що не знайдене

while (left <= right) and not f do

Begin

m:= (left + right) div 2; // Номер елемента посередині тієї частини масиву, де далі продовжуватиметься пошук

if x > a[m]

then left:= m+1 // Змінюється початковий номер елемента тієї частини масиву, де відбуватиметься пошук

else if x < a[m]

then right:= m-1 // Змінюється останній номер елемента тієї частини масиву, де відбуватиметься пошук

else f:= true; // Число в масиві знайшлося

end;

If f

then Edit1.Text:= 'Число в масиві є'

else Edit1.Text:= 'Числа в масиві немає';

end;