• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Сортування елементів масиву

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

Задача 172. Вистроїти учнів класу по зросту – від вищих до нижчих. Для спрощення вважати, що в класі навчаються тільки хлопці.

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

Спосіб 1-й:Припустимо, що на уроці фізичного виховання в нашому класі присутні лише 10 учнів (для можливості наочного зображення ходу розв’язання). Приведемо таблицю зі значеннями росту учнів у відповідності зі списком, який міститься на відповідній сторінці в класному журналі. Номер комірки приведеної таблиці відповідає порядковому номеру учня в списку. Зроблено це знову ж таки лише тому, щоб простіше було пояснювати спосіб шикування, а не тому, що наш клас знаходиться в концтаборі, де відсутні прізвища і кожен має свій «інвентарний» номер.

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

Тепер спробуємо словесно пояснити спосіб сортування елементів масиву (росту учнів) по спаданню, тобто спочатку повинні стояти учні з більшим зростом, а далі – з меншим. Беремо перший елемент масиву – 172 і порівнюємо його з другим – 165. Так як другий елемент менший за перший, то залишаємо його на місці. Порівнюємо перший елемент – 172 з третім – 180, так як третій елемент більший за перший, то їх необхідно поміняти місцями. Тобто перший елемент стає 180, а третій – 172. Тут необхідно врахувати той факт, що для виконання такої перестановки необхідно використати додаткову змінну, щоб не втратити значення однієї з комірок. Це реалізовується досить просто:

...

b := a[1];

a[1] := a[3];

a[3] := b;

...

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

Жирним шрифтом ми виділили вже відсортовані елементи масиву. Всього при даному способі сортування нам необхідно зробити 9! порівнянь[8]. Розглянутий спосіб сортування називають способом обміну. Програмна реалізація даного способу сортування матиме вигляд:

Program sort1;

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, n : integer;

k : byte;

begin

clrscr;

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

{ Нижче реалізовано алгоритм сортування методом обміну }

n:=10;

for i:=1 to n-1 do

begin

for j := i+1 to n do

if a[i]<a[j] then

begin

k := a[j];

a[j] := a[i];

a[i] := k;

end;

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

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

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

readln;

end.

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

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

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

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

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

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

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

Крім того, уважне вивчення таблиці для різних випадків початкових значень елементів масиву приводить до висновку, що після першого проходження останній елемент точно буде найбільшим, після другого – точно будуть на своїх місцях останній і передостанній і т.д., тобто після завершення чергового проходження ми можемо зменшити кількість розглядуваних елементів на 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 зсуваються вправо. Отже, показуємо хід описаного алгоритму вставки для нашого масиву.

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

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

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

Новий масив:

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

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

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

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 і т.д. І лише в останню чергу переставляються (якщо є потреба) сусідні елементи.

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

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 елементів) – спосіб вставки. Це буде також швидке сортування.

Читайте також:

1. II. За зміною ступенів окиснення елементів, які входять до складу реагуючих речовин
2. Аналіз службового призначення деталей та конструктивних елементів обладнання харчових виробництві, визначення технічних вимог і норм точності при їх виготовленні
3. Багатофазне сортування
4. Багатофазне сортування
5. Будова атомів хімічних елементів.
6. Будова нагрівальних елементів
7. Валентність — це здатність атомів одного елемента сполу­чатися з певним числом атомів інших елементів під час утворення хімічних сполук.
8. Взаємозв’язок елементів управління
9. Виберіть 2 положення, які треба добавити у визначення елементів наукової проблеми.
10. Вивчення структури та зв”язку структурних зрушень елементів.
11. Вимоги до структурних елементів пояснювальної записки
12. Вимоги до структурних елементів роботи

Переглядів: 1105