Задача 173.173. Розв’яжіть попередню задачу, але шикуйте учнів від нижчих до вищих.

Спосіб 2-й: Інакше кажучи, умову задачі можна сформулювати так: відсортувати масив по неспаданню. Чому саме по неспаданню, а не по зростанню. Термін неспадання є більш точним у застосуванні до поставленої задачі. Адже цілком можливо, і скоріше всього так воно практично і буде, що в класі обов’язково виявиться декілька учнів з однаковим зростом. Нам байдуже, хто з них буде стояти раніше, але якби ми сказали сортувати по зростанню, то з філософської точки зору отримали б проблему, яку неможливо вирішити: серед двох однакових обов’язково потрібно було б вибрати більшого. Саме у точності формулювання умови задачі і полягає мистецтво складання завдань з будь–якого предмету, а з програмування – особливо.

Розв’яжемо задачу іншим способом – способом перестановок.

Спочатку розберемо сам спосіб впорядкування масиву на основі способу перестановок. Нагадаємо, що наш масив до сортування має такий вигляд:

до сорт.

Будемо вважати, що наш масив ще не впорядковано. Ідея методу перестановок полягає в тому, що під час кожного проходження по всьому масиву порівнюються два сусідні елементи: перший з другим, другий з третім і т.д., передостанній з останнім. Якщо під час порівняння виникла необхідність поміняти елементи місцями, то їх переставляють і про це повідомляють змінній, яка відповідає за спостереження за тим, чи зроблено хоча б одну перестановку (Таку змінну у програмістів прийнято називати прапорцем). Ця змінна може бути типу boolean, назвемо її flag. До початку сортування роблять присвоєння flag:= false, якщо ж під час проходження по масиву зроблено хоча б одну перестановку, то flag:= true. Якщо flag = true (зроблено хоча б одну перестановку), то прапорець знову встановлюють у початкове положення і знову повторюють порівняння сусідніх елементів масиву. Якщо на якомусь кроці не зроблено жодної перестановки, то сортування на цьому закінчується, так як масив вже впорядковано. Зробимо трасування нашого масиву, але будемо відображати стан масиву після чергового порівняння всіх елементів масиву.

Звертаємо вашу увагу ще раз на той факт, що стан масиву відображено після кожного повного проходження по масиву. Жирним шрифтом виділено комірки, значення яких змінилися після закінчення проходження. Як бачимо, нам знадобилось менше кроків для впорядкування всього масиву, ніж при використанні попереднього способу – способу обміну. Чому? Нам просто повезло, що у невпорядкованому масиві початкові значення комірок мали саме такі значення. Взагалі, згідно теорії ймовірності, так і повинно бути при використанні способу перестановок, але у найгіршому випадку ми виконали б рівно ж стільки проходжень, як і при застосуванні способу обміну. У такому випадку програмісти кажуть, що обидва способи однакового порядку.

										прапорець	прохід
										false	до сорт.
										true	1-й
										true	2-й
										true	3-й
										true	4-й
										true	5-й
										false	6-й

Крім того, уважне вивчення таблиці для різних випадків початкових значень елементів масиву приводить до висновку, що після першого проходження останній елемент точно буде найбільшим, після другого – точно будуть на своїх місцях останній і передостанній і т.д., тобто після завершення чергового проходження ми можемо зменшити кількість розглядуваних елементів на 1.

Мабуть настав час привести програмну реалізацію способу перестановок, отже, пишемо програму:

program sort2;

uses dos, crt;

const b: array[1..10] of byte =

(172,165,180,174,182,179,183,185,176,181);

var a: array[1..10] of byte;

i, n: integer;

flag: boolean;

k: byte;

begin

for i:= 1 to 10 do a[i]:= b[i];

n:= 10;

flag:= true; { інакше ми просто не ввійдемо в цикл }

while flag = true do

begin

flag:= false;

for i:=1 to n-1 do

if a[i]>a[i+1] then

begin

k:= a[i];

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

a[i+1]:= k;

flag:= true;

end;

dec(n);

end;

writeln(‘ Відсортований масив з 10 чисел: ’);

for i:=1 to 10 do write(a[i],‘ ’);

readln;

end.

3-й спосіб: Розв’яжемо останню задачу ще одним способом – способом вставки. Суть способу вставки полягає в тому, що на підставі існуючого масиву формується новий таким чином: спочатку в новий масив заноситься перший елемент, потім заносимо другий елемент, але розміщуємо його так, щоб не порушити порядок, потім третій і т.д. Якщо при розміщенні якогось елементу, його потрібно розмістити перед деякими елементами, то останні просто зсуваються, а в утворене вакантне місце вставляється розглядуваний елемент. Цей спосіб дуже нагадує роботу бібліотекаря з книгами на стелажах. Якщо читач приніс том номер 12, а всього є зібрання творів з 20 томів, то принесений том розміщується після 11-го, а томи 13–20 зсуваються вправо. Отже, показуємо хід описаного алгоритму вставки для нашого масиву.

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

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

Старий масив:

Новий масив:

										1-й прохід
	172									2-й прохід
										3-й прохід
			180							4-й прохід
										5-й прохід
				180	182					6-й прохід
										7-й прохід
										8-й прохід
				179	180	182	183	185		9-й прохід
							182	183	185	10-й прохід

 

При великих масивах можуть виникати проблеми з пам’яттю комп’ютера, тому модифікуємо спосіб вставки таким чином, щоб не використовувати додаткового масиву. В цьому випадку нам потрібно розглядати всі елементи, починаючи з другого і вставляти їх у відповідне місце серед всіх елементів, що знаходяться перед ним, так як вони на попередньому кроці були впорядковані відповідним чином. Хід сортування у цьому випадку буде мати вигляд:

										до сортування
	172									1 -й прохід
										2 -й прохід
			180							3 -й прохід
										4 -й прохід
				180	182					5 -й прохід
										6 -й прохід
										7 -й прохід
			176	179	180	182	183	185		8 -й прохід
						181	182	183	185	9 -й прохід

Знову ж таки, елемент, що вставляється, виділено жирним шрифтом, а елементи, що зсуваються, крім того написано курсивом і підкреслено.

Відповідна програма сортування буде мати вигляд:

program sort3;

uses dos,crt;

const b: array[1..10] of byte =

(172,165,180,174,182,179,183,185,176,181);

var a: array[1..10] of byte;

i, j: integer;

flag: boolean;

k: byte;

begin

for i:= 1 to 10 do a[i]:= b[i];

for i:= 1 to 10 do write(f, a[i],' ');writeln(f,'');

n:= 10;

for i:= 2 to n do

begin

k:= a[i];

j:= i-1;

flag:= false;

while (j >= 1) and (flag = false) do

begin

if k < a[ j] then

begin

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

j:= j-1;

end

else flag:= true;

end;

a[ j+1]:= k;

end;

writeln(‘ Відсортований масив з 10 чисел: ’);

for i:= 1 to 10 do write(a[ i],‘ ’);writeln;

readln;

end.

Всі три розглянуті вище способи є найпростішими, але в той же час і не дуже ефективними. Це пов’язано з тим, що у всіх способах порівнюються і при необхідності міняються елементами сусідні елементи. Тому, якщо останній елемент буде найменшим (при впорядкуванні за незростанням), то для впорядкування такого масиву знадобиться великий час. Методи швидких сортувань як раз і базуються на ідеї порівняння і обміну елементів, що стоять далеко один від одного.

4–й спосіб: Розглянемо спосіб сортування, запропонований Шеллом. Суть методу сортування, названого методом Шелла, полягає в тому, що спочатку порівнюються елементи, що стоять один від одного на відстані N/2 (N – кількість елементів в масиві), потім на відстані N/4 і т.д. І лише в останню чергу переставляються (якщо є потреба) сусідні елементи.

										до сортування
										1 -й прохід
										2 -й прохід
										3 -й прохід
										4 -й прохід

Більш детально з способом сортування, запропонованим Шеллом, спробуйте розібратись самостійно на підставі вище наведеної таблиці і програми, написаної нижче.

Program sort4; { Метод Шелла }

uses dos,crt;

const b: array[1..10] of byte =

(172,165,180,174,182,179,183,185,176,181);

var a: array[1..10] of byte;

i, j, k, m: integer;

t: byte;

begin

for i:= 1 to 10 do a[i]:= b[i];

{ Нижче знаходиться алгоритм сортування по методу Шелла }

m:=10;

while m>0 do

begin

m:= m div 2;

for i:= m to 9 do

begin

j:= i - m + 1;

while j >= 1 do

begin

if a[ j] <= a[ j + m] then j:= 0

else

begin

t:= a[ j];

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

a[ j + m]:= t;

end;

dec(j);

end;

end;

end;

{ Кінець сортування }

writeln(‘ Відсортований масив з 10 чисел: ’);

for i:= 1 to 10 do write(a[i], ‘ ’); writeln;

readln;

end.

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

Відмітимо, що не існує універсального рецепту по використанню того чи іншого методу сортування, більше того, при одних вхідних даних кращим може виявитись один спосіб, а при інших – інший. І сьогодні продовжуються пошуки модифікації існуючих алгоритмів сортування та створення нових способів для прискорення сортування при розв’язанні кожної конкретної «солідної» задачі, отож бажаємо і вам створити власний спосіб сортування, який був би кращим (у всякому випадку – не гіршим) від уже відомих. Рекомендуємо вам спробувати створити власний комбінований спосіб сортування, наприклад, для великих масивів застосувати метод Шелла, а після зменшення проміжку (десь до 50 елементів) – спосіб вставки. Це буде також швидке сортування.