Новини освіти і науки:

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Сортування вставкою.

Масиви

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

Масиви (Array)-упорядкована структура однотипних даних, причому кількість компонентів фіксована. Її розмір не повинен перевищувати 64 Кб (розмір сегмента пам'яті). Тип компонента може бути структурний. Масиви можуть бути як одномірними, так і багатомірними.

Опис масиву:

1-й спосіб:

Type <ім'я типу> = Array [діапазон1,…,діапазон n] of <тип компонентів>;

…....

Var <ім'я змінної>: <ім'я типу>;

2-й спосіб:

Var <ім'я змінної> = Array [діапазон1, …,діапазон n] of <тип компонентів>;

Діапазон може бути будь-яким типом, що розглядається, але він повинен належати до типу Word.

Масив- упорядкована множина однорідних елементів, якому дане одне загальне ім'я. Кожне число в масиві називається елементом.

5.2 Одномірні масиви

Одномірний масив складається з n елементів - це a₁,a₂,…,a _n-являє собою рядок або стовпець. Елементи одномірного масиву позначаються a[i], де a - ім'я масиву, i - номер елемента в масиві.

Приклад. Географ передав набір значень температури, які знімалися протягом червня місяця. Необхідно обчислити:

а) середню температуру;

б) число днів, у яких температура була вище 23 градусів.

Набір температур утворить масив. Дамо цьому масиву ім'я t. Тоді масив t містить 30 елементів, при цьому кожен елемент являє собою температуру одного із днів червня.

Елементи масиву t можна записати в такому вигляді: t[1], t[2], t[3], t[4], ..., t[29], t[30].

Нижче показано, як призначаються елементи масиву для 30 чисел, які становлять червневі температури.

Дата	Температура	Елемент
1 ЧЕРВНЯ		t[1]
2 ЧЕРВНЯ		t[2]
3 ЧЕРВНЯ		t[3]
4 ЧЕРВНЯ		t[4]
5 ЧЕРВНЯ		t[5]
. . . . . .	. . . . . . .	. . . . . .
29 ЧЕРВНЯ		t[29]
30 ЧЕРВНЯ		t[30]

Наприклад, значення елемента t[3]=23, а значенню елемента t[29]=20. Важливо пам'ятати, що елементи t[1], t[2], t[3], ..., t[30] є просто окремими числами.

uses WinCrt;
var t : array[1..30] of integer; {опис масиву}
i, k : integer;{i- лічильник, k - кількість днів для яких t>23}
s : real; {s- середня температура}
begin
{введення масиву температур}
for i := 1 to 30 do
begin
write('Введіть температуру в ',i,' - день '); readln(t[i])
end;
s := 0; k := 0;
for i := 1 to 30 do
begin
s:= s + t[i]; {обчислюємо сумарну температуру}
if t[i] > 23 then k:= k + 1
end;
s:=s/30;
{обчислюємо середню температуру}
writeln('Середня температура в червні ', s:4:2);
writeln('Число днів з температурою більше 23 град. ', k)
end.

Приклад. Необхідно ввести одномірний масив і перевірити, чи належать його елементи відрізку [a,b] і, якщо належать, запам'ятати їх номера й вивести на екран. Відрізок ввести із клавіатури.

uses wincrt;
var x: array[1..20] of real; {опис вихідного масиву}
nom: array[1..20] of integer; {опис масиву номерів елементів, що належать до
заданого інтервалу}
a, b: real;
i, k, n: integer;
begin
k:=0;
{кількість шуканих елементів}
writeln('введіть відрізок
[а,b], a < b:');
write('a='); readln(a);
write('b='); readln(b);
{введення вихідного масиву}
write('розмір масиву n='); readln(n);
writeln('введення масиву');
for i:=1 to n do
begin
read(x[i]); {введення N чисел у рядок через пробіл}
if (x[i]>=a) and
(x[i]<=b) then
begin
k:=k+1;
{обчислюємо кількість}
nom[k]:=i;
{заповнюємо масив}
end;
end;
write('кількість таких елементів:k=',k);
writeln;
write('їх номера: ');
for i:=1 to k do
write(' ',nom[i]); {друк нового масиву}
end.

Приклад. Скласти програму перестановки m - го й k - го елементів одномірного масиву. Розглянемо вирішення задачі на конкретному прикладі.

Нехай заданий довільний масив чисел:

3, -12 , 45 , 16 , -23 , 4 , -5 , 76 , -34.

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

Користувач забажав, щоб були переставлені 5-й й 8-й елементи, тобто -23 й 76. Якщо виконати відразу команду присвоєння a[5] := a[8], то значення елемента a[5] буде "стерте" і загублено назавжди. Щоб цього не відбулося, потрібна ще одна команда, яка б "запам'ятовувала" значення одного з елементів, що переставляють. Нехай ця змінна з ім'ям p, тоді перестановка буде виглядати так:

p := a[5] - "запам'ятовується" 5 - й елемент,

a[5] := a[8] - на місце п'ятого елемента "ставиться" восьмий,

a[8] := p - на місце восьмого елемента "ставиться" п'ятий.

uses wincrt;
var а: array[1..9] of real; {опис вихідного масиву}
p: real;
k, m,n: integer;
begin
writeln('введіть m , k:');
write('m='); readln(m);
write('k='); readln(k);
{введення
вихідного масиву}
write('розмір масиву n='); readln(n);
writeln('введення масиву');
for i:=1 to n do
read(a[i]); {введення N
чисел у рядок через пробіл}
p := a[k];
a[k]:= a[m];
a[m]:= p;
for i:=1 to n do
write(' ',a[i]); {друк нового масиву}
writeln;
end.

Приклад. Знайти максимальний елемент числового масиву A(20) і його номер.

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

A					…
i					…...

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

На нашому прикладі цей процес буде виглядати так: Приймаємо за найбільший -А(1) (max=45, im=1) і порівнюємо його з наступними елементами А(2)> max (25>45-?) (немає), ідемо далі; A(3)>max (93>45-?) (так) - за найбільший приймаємо A(3) (max=93) і запам'ятовуємо його номер (im=3) продовжуємо порівняння; A(4)> max ((35>93-?)) (немає) і т.д. У результаті змінна мах буде дорівнює максимальному елементу, im- буде містити його номер.

uses wincrt;
var а: array[1..9] of real; {опис вихідного масиву}
max: real;
i, im,n: integer;
begin
{введення
вихідного масиву}
write('розмір масиву n='); readln(n);
writeln('введення масиву');
for i:=1 to n do
read(a[i]); {введення N
исел у рядок через пробіл}
max:= a[1];
for i := 2 to n do if a[i]> max then
begin
max := a[i] ; im:=i;
end;
writeln('max=',max,'im=',im);
end.

5.3 Методи сортування масивів

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

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

- кількість присвоєнь;

- кількість порівнянь.

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

- прямі методи сортування;

- поліпшені методи сортування.

Прямі методи сортування за принципом, що лежить в основі методу, у свою чергу, розділяються на три підгрупи:

1) сортування вставкою (включенням);

2) сортування вибором (виділенням);

3) сортування обміном ("бульбашкове" сортування).

Поліпшені методи сортування ґрунтуються на тих же принципах, що й прямі, але використають деякі оригінальні ідеї для прискорення процесу сортування. Прямі методи на практиці використаються досить рідко, тому що мають відносно низьку швидкодію. Однак вони добре показують суть базованих на них поліпшених методів. Крім того, у деяких випадках (як правило, при невеликій довжині масиву й/або особливому вихідному розташуванні елементів масиву) деякі із прямих методів можуть навіть перевершити поліпшені методи.

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

- сортування вставкою (включенням);

- сортування вибором (виділенням);

- сортування обміном ("бульбашкове" сортування).

Сортування масивів методом вставки(включенням) здійснюються таким чином.

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

Таким чином, алгоритм буде складатися з n-1-го проходу (n - розмірність масиву), кожний з яких буде включати чотири дії:

взяття чергового i-го невідсортованого елемента й збереження його в додатковій змінній;

- пошук позиції j у відсортованій частині масиву, у якій наявність узятого елемента не порушить упорядкованості елементів;

- зсув елементів масиву від i-1-го до j-го вправо, щоб звільнити знайдену позицію вставки;

- вставка взятого елемента в знайдену j-ю позицію.

Для реалізації даного методу можна запропонувати кілька алгоритмів, які будуть відрізнятися способом пошуку позиції вставки. Розглянемо схему реалізації одного з можливих алгоритмів.

Схематично описані дії можна представити таким чином:

Малюнок 5.2

Малюнок 5.3

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

<== попередня сторінка	\|	наступна сторінка ==>
Злочини проти міжнародного правопорядку.	\|	Сортування вибором.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.