Методи впорядкування масивів.

Методи впорядкування масивів.

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

У загальному випадку елементом масиву може бути запис, що складається з декількох полів. Сортування може проводитися по кожному з полів, яке називається в цьому випадку ключем. Так, якщо список службовців сортується по коду службовців, то ключем є код, якщо за прізвищем - ключем є прізвище і т.п. Якщо ж елементами масиву є дані простого типу (цілий, дійсний і т.д.), то ключем буде саме значення елементу.

Основні вимоги до сортування масивів – раціональне використання пам'яті. Це означає, що переупорядкування елементів потрібно виконувати в цьому ж самому масиві. Методи, що пересилають елементи з масиву А в масив В, нами розглядатись не будуть..

Існує кілька різних методів сортування, що відрізняються ступенем складності й ефективністю. Зручна міра ефективності утворюється при підрахунку числа С - необхідних порівнянь ключів і М – кількості пересилань елементів. Ці числа визначаються деякими функціями від числа n – кількості елементів, що впорядковуються.. Гарні алгоритми сортування вимагають порядку n•logn порівнянь, однак, вони досить складні. Щоб розібрати основні принципи сортувань, скористаємося спочатку розглядом щодо простих методів, що вимагають порядку n² порівнянь ключів.

Методи, що сортують елементи усередині масиву, можна розбити на чотири основних класи в залежності від покладеного в їх основі прийому:

· сортування включеннями;

· сортування вибором;

· сортування обміном;

При розгляді основних методів зробимо припущення:

· в ролі структури даних для розгляду алгоритмів сортування оберемо одновимірний цілочисельний масив;

· сортування буде здійснюватись без використання допоміжних масивів;

· впорядкування здійснюється за зростанням;

· в головній програмі діє такий опис даних.

const n=...;

{кількість елементів масиву визначається користувачем}

type

massiv = array[1..n] of integer;

var

a:massiv;

i:integer;

Методи сортування.

Сортування простим вибором

Сутність методу полягає у наступному. На першому кроці обирається найменший елемент і міняється місцями з першим. На другому кроці серед решти елементів знову обирається найменший елемент і міняється місцями з другим. Цей процес продовжується до повного впорядкування вихідного масиву. Проілюструємо роботу методу на прикладі масиву з 10 елементів. На кожному кроці найменший елемент виділятимемо іншим кольором.

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

44 55 12 42 94 18 06 67 32 13

Після першого кроку:

06 55 12 42 94 18 44 67 32 13

Після другого кроку:

06 12 55 42 94 18 44 67 32 13

На останньому кроці

06 12 13 18 32 42 44 55 67 94

При записі алгоритму на кожному кроці доцільно при пошукові найменшого елементу запам’ятовувати не сам елемент, а його номер. Це спростить алгоритм. Процедура сортування простим вибором має такий вигляд:

procedure straightselection (var a: massiv);

var

i,j,k: integer;

x: integer;

n1,n: integer;

begin

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

n1:= Low(a);

n:= High (a);

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

for i:= n1 to n do

begin

k:=i;

for j:= i+1 to n do

if a[j]<a[k] then k:=j;

if k >i then

begin

x:=a[i];

a[i]:=a[k];

a[k]:=x;

end;

end;

end;

Число C порівнянь ключів не залежить від початкового порядку ключів:

C=1/2 (n² +n–1).

Мінімальне число пересилань у випадку початково упорядкованих елементів має значення:

M_min=0

Найбільше значення ця величина приймає у випадку, коли елементи вихідного масиву розташовані в зворотному порядку до впорядкування (тобто, впорядковані за спаданням):

M_max=trunc (n²/4).

Сортування простим обміном

Наведений нижче алгоритм сортування простим обміном заснований на принципі порівняння й обміну пари сусідніх елементів доти, поки не будуть відсортовані всі елементи. Сутність методу полягає у тому, що на кожному кроці порівнюються пари сусідніх елементів. Якщо “лівий” елемент більший за “правий”, то вони міняються місцями. Тобто, здійснюється впорядкування кожної пари елементів. Порівняння здійснюємо, починаючи з кінця масиву в зворотному природному порядку напрямку. В результаті елементи з малими значеннями будуть рухатись в бік початку масиву.

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

Застосування методу розглянемо на прикладі впорядкування масиву з 10 елементів. Елементи, що переміщувались вліво, виділимо кольором.

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

44 55 12 42 94 18 06 67 32 13

Після першого кроку:

06 44 55 12 42 94 18 13 67 32

Після другого кроку:

06 12 44 55 13 42 94 18 32 67

Після останнього кроку:

06 12 13 18 32 42 44 55 67 94

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

procedure bubblesort (var a: massiv);

var

i,j: integer;

x: integer;

n1,n: integer;

begin

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

n1:=low(a);

n:= high (a);

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

for i:= n1 to n-1 do

for j:= n downto i+1 do

if a[j]<a[j-1] then

begin

x:=a[j];

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

a[j-1]:=x;

end;

end;

Число порівнянь для сортування даним методом дорівнює:

C=1/2 (n² - n),

а кількість пересилань

M_min = 0,

M_ср = 3/4 (n² - n),

M_max = 3/2 (n² - n).

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;

Метод

Можливості об'єкту. Оскільки Сірко — Собака, він може гавкати. Тому гавкати() є одним із методів об'єкту Сірко. Він може мати і інші методи, зокрема: місце(), або їсти(). В межах програми, використання методу має впливати лише один об'єкт; всі Собаки можуть гавкати, але треба щоб гавкала лише одна окрема собака.

Успадкування

В деяких випадках, клас може мати «підкласи», спеціалізовані версії класу. Наприклад, клас Собака може мати підкласи Коллі та Пікінес. В цьому випадку, Сірко буде екземпляром класу Вівчарка. Підкласи успадковують атрибути та поведінку своїх батьківських класів, і можуть вводити свої власні.

Поліморфізм

Поліморфізм означає залежність поведінки від класу, в якому ця поведінка викликається, тобто, два або більше класів можуть реагувати по різному на однакові повідомлення. Наприклад, якщо Собака отримує команду голос(), то у відповідь можна отримати Гав; якщо Свиня отримує команду голос (), то у відповідь можна отримати Хрю.

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

Використання середовища візуального програмування (наприк­лад, Visual Basic) дозволяє поєднати «старий», математико-алго-ритмічний, і «новий», інформаційно-технологічний, підходи до навчання інформатики, які до цього часу існували в одному курсі прак­тично незалежно один від одного. Повна відмова від математико-ал-горитмічного підходу призвела б до скорочення інтелектуально-ло­гічного аспекту навчання, в той же час відмова в'щ вивчення сучасних

інформаційних технологій ускладнила би формування основ загаль­ної інформаційної культури.

Крім того, системи візуального програмування є провідниками об'єктно-оріентованоїтехнопогїі Microsoft та ідеології ресурсів, які ви­користовуються спільно, а з іншого боку пропонує користувачеві струк-туровану, а також просту та зручну мову запису і налагодження про­грам, що використовуються як при створенні нових програм, так і для програмування в офісних продуктах Microsoft.

Програмування в середовищі Visual Basic суттєво відрізняється від програмування в процедурних, процедурно-орієнтованих мовах про­грамування, а також мовах логічного програмування.

До основних принципів середовищ візуального програмування, які відрізняють їх від процедурних, слід віднести:

— відокремлення елементів (об'єктів) програми, які пов'язані з інтерфейсом користувача, від її алгоритмічної частини;

— швидкість і простота створення, модернізація інтерфейсу про­грам, в якому використовуються готові елементи (блоки), що реалізу­ють деякі великі функції (процедури) управління програмою;

— використання вже існуючих кодів, описаних іншими мовами про­грамування.

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

Стандартне програмування традиційно орієнтується на послідов­ний опис деякого конкретного процесу, тому написання програм є кро-піткою працею програміста. В такому процесі необхідно детально опи­сувати кожний крок, передбачений програмою. Одним з недоліків такого стилю є те, що той, хто складає програму, повинен до програ­ми все записати сам. У програмуванні, що орієнтоване на реакції на події, замість детального опису кожного кроку програміст повинен вка­зати, як слід реагувати на різні події (чи дії користувача), до яких, на­приклад, можна віднести вибір вказівки, клацання кнопкою миші, пе­реміщення миші тощо. На одні з подій можна передбачити деяку реакцію, інші—просто проігнорувати. При цьому створюється не одна велика програма, а кілька програм, які складаються із набору взаємо­діючих процедур, що управляються користувачем.

Використання середовища візуального програмування вже при складанні найпростіших програм надає можливість учням одразу спо­стерігати наслідки своєї роботи, що дуже важливо на перших кроках

 

Методи впорядкування масивів.

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

У загальному випадку елементом масиву може бути запис, що складається з декількох полів. Сортування може проводитися по кожному з полів, яке називається в цьому випадку ключем. Так, якщо список службовців сортується по коду службовців, то ключем є код, якщо за прізвищем - ключем є прізвище і т.п. Якщо ж елементами масиву є дані простого типу (цілий, дійсний і т.д.), то ключем буде саме значення елементу.

Основні вимоги до сортування масивів – раціональне використання пам'яті. Це означає, що переупорядкування елементів потрібно виконувати в цьому ж самому масиві. Методи, що пересилають елементи з масиву А в масив В, нами розглядатись не будуть..

Існує кілька різних методів сортування, що відрізняються ступенем складності й ефективністю. Зручна міра ефективності утворюється при підрахунку числа С - необхідних порівнянь ключів і М – кількості пересилань елементів. Ці числа визначаються деякими функціями від числа n – кількості елементів, що впорядковуються.. Гарні алгоритми сортування вимагають порядку n•logn порівнянь, однак, вони досить складні. Щоб розібрати основні принципи сортувань, скористаємося спочатку розглядом щодо простих методів, що вимагають порядку n² порівнянь ключів.

Методи, що сортують елементи усередині масиву, можна розбити на чотири основних класи в залежності від покладеного в їх основі прийому:

· сортування включеннями;

· сортування вибором;

· сортування обміном;

При розгляді основних методів зробимо припущення:

· в ролі структури даних для розгляду алгоритмів сортування оберемо одновимірний цілочисельний масив;

· сортування буде здійснюватись без використання допоміжних масивів;

· впорядкування здійснюється за зростанням;

· в головній програмі діє такий опис даних.

const n=...;

{кількість елементів масиву визначається користувачем}

type

massiv = array[1..n] of integer;

var

a:massiv;

i:integer;

Методи сортування.

Сортування простим вибором

Сутність методу полягає у наступному. На першому кроці обирається найменший елемент і міняється місцями з першим. На другому кроці серед решти елементів знову обирається найменший елемент і міняється місцями з другим. Цей процес продовжується до повного впорядкування вихідного масиву. Проілюструємо роботу методу на прикладі масиву з 10 елементів. На кожному кроці найменший елемент виділятимемо іншим кольором.

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

44 55 12 42 94 18 06 67 32 13

Після першого кроку:

06 55 12 42 94 18 44 67 32 13

Після другого кроку:

06 12 55 42 94 18 44 67 32 13

На останньому кроці

06 12 13 18 32 42 44 55 67 94

При записі алгоритму на кожному кроці доцільно при пошукові найменшого елементу запам’ятовувати не сам елемент, а його номер. Це спростить алгоритм. Процедура сортування простим вибором має такий вигляд:

procedure straightselection (var a: massiv);

var

i,j,k: integer;

x: integer;

n1,n: integer;

begin

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

n1:= Low(a);

n:= High (a);

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

for i:= n1 to n do

begin

k:=i;

for j:= i+1 to n do

if a[j]<a[k] then k:=j;

if k >i then

begin

x:=a[i];

a[i]:=a[k];

a[k]:=x;

end;

end;

end;

Число C порівнянь ключів не залежить від початкового порядку ключів:

C=1/2 (n² +n–1).

Мінімальне число пересилань у випадку початково упорядкованих елементів має значення:

M_min=0

Найбільше значення ця величина приймає у випадку, коли елементи вихідного масиву розташовані в зворотному порядку до впорядкування (тобто, впорядковані за спаданням):

M_max=trunc (n²/4).

Сортування простим обміном

Наведений нижче алгоритм сортування простим обміном заснований на принципі порівняння й обміну пари сусідніх елементів доти, поки не будуть відсортовані всі елементи. Сутність методу полягає у тому, що на кожному кроці порівнюються пари сусідніх елементів. Якщо “лівий” елемент більший за “правий”, то вони міняються місцями. Тобто, здійснюється впорядкування кожної пари елементів. Порівняння здійснюємо, починаючи з кінця масиву в зворотному природному порядку напрямку. В результаті елементи з малими значеннями будуть рухатись в бік початку масиву.

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

Застосування методу розглянемо на прикладі впорядкування масиву з 10 елементів. Елементи, що переміщувались вліво, виділимо кольором.

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

44 55 12 42 94 18 06 67 32 13

Після першого кроку:

06 44 55 12 42 94 18 13 67 32

Після другого кроку:

06 12 44 55 13 42 94 18 32 67

Після останнього кроку:

06 12 13 18 32 42 44 55 67 94

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

procedure bubblesort (var a: massiv);

var

i,j: integer;

x: integer;

n1,n: integer;

begin

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

n1:=low(a);

n:= high (a);

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

for i:= n1 to n-1 do

for j:= n downto i+1 do

if a[j]<a[j-1] then

begin

x:=a[j];

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

a[j-1]:=x;

end;

end;

Число порівнянь для сортування даним методом дорівнює:

C=1/2 (n² - n),

а кількість пересилань

M_min = 0,

M_ср = 3/4 (n² - n),

M_max = 3/2 (n² - n).