ІНФОРМАТИКА для 9 класу


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

Упорядкування обміном; упорядкування вставлянням; упорядкування вибором.

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

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

Це робиться таким чином (рис. 7.29).

image

Рис. 7.29. Алгоритм упорядкування методом “бульбашки”

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

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

Читать  Формалізація та алгоритмізація обчислювальних процесів

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

Нарешті, коли залишається тільки два елементи, які потрібно порівняти, виконується лише одне порівняння.

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

Кількість порівнянь у кожному проході дорівнює m – i, де i – номер проходу масивом (перший, другий, третій і так далі).

При обміні значень між елементами масиву зазвичай використовується “буферна” (третя) змінна, якій надають значення одного з елементів.

Приклад 7.9.1 const

M = 10;

Var

Arr: array[1..m] of integer; i, j, k: integer;

Begin

Randomize; // ініціювання надання випадкових значень змінним write (‘Початковий масив: ‘);

For i := 1 to m do // надання випадкових значень елементам масиву

Begin

Arr[i] := random(256);

Write (arr[i]:4); // виведення i-го значення

End; begin

Writeln; writeln; // завершення рядка виведення і порожній рядок for i := 1 to m-1 do // початок циклу проходів по масиву

For j := 1 to m-i do // початок циклу перебору елементів if arr[j] > arr[j+1] then

Читать  ПЕРЕДДИПЛОМНА ПРАКТИКА – Адміністрування програмного комплексу Денвер (Denwer)

Begin // обмін значеннями елементів k := arr[j];

Arr[j] := arr[j+1];

Arr[j+1] := k

End;

Write (‘Упорядкований масив: ‘); for i := 1 to m do

Write (arr[i]:4); // виведення i-го значення writeln;

End; end.

 

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

Таким чином, потрібно n–1 разів (n – розмірність масиву) виконати дії:

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

Знайти позицію j у впорядкованій частині масиву, у якій вибраний елемент не порушуватиме впорядкованості;

Зсув елементів масиву від i–1-го до j–1-го вправо для звільнення знайденої позиції;

Вставити вибраний елемент у знайдену j-ту позицію. Схематично описані дії можна подати так:

image image image

image

1

2

3

4

 

 

 

image

 

image

 

image

 

image

 

 

image

 

image

 

image

 

image

 

Збереження

 

 

 

 

 

 

 

 

 

image

image

 

image

image

 

 

 

Пошук місця вставляння

 

Зсув

Вставляння

 

Приклад 7.9.2

Const N = 20;

Var A : array [1..N] of Real; P: Real; i, j, k: Integer; begin

WriteLn (‘Уведіть елементи масиву’); for i := 1 to N do

Begin Write(‘A[‘,i,’]=‘);

ReadLn(A[i]);

End;

WriteLn(‘Масив до впорядкування:’); for i := 1 to N do Write(A[i], ‘ ‘); WriteLn;

For i := 1 to n do begin

P := A[i]; //збереження елемента із невідсортованої частини масиву j := 1; // пошук позиції вставлення

While P > A[j] do j := j + 1;

For k := i-1 downto j do A[k+1] := A[k]; //зсув елементів A[j] := P; //вставляння елемента у знайдену позицію end;

WriteLn(‘Упорядкований масив:’); for i := 1 to N do Write(A[i], ‘ ‘); WriteLn;

End.

Суть методу впорядкування вибором полягає у тому, що знаходимо найменший елемент масиву на інтервалі від 1-го елемента до n-го (остан — нього) елемента і переставляємо його місцями з першим елементом. На другому кроці знаходимо найменший елемент масиву на інтервалі від 2-го до n-го елемента і переставляємо його місцями з другим елементом. І так далі для всіх елементів до n–1-го.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Застосуємо метод упорядкування вибором для упорядкування масиву 8, 2, 15, 12, 3, 5:

 

image

 

image image

 

 

image image

 

image image

image

 

 

 

 

 

 

 

 

 

 

 

Приклад 7.9.3

Const N = 20;

Var A : array [1..N] of Real; P: Real; i, j, Nmin: Integer; begin

WriteLn (‘Уведіть елементи масиву’); for i := 1 to N do

Begin Write(‘A[‘,i,’]=‘);

ReadLn(A[i]); end;

WriteLn(‘Масив до впорядкування:’); for i := 1 to N do Write(A[i], ‘ ‘); WriteLn;

For i := 1 to n-1 do begin

Nmin := i;

For j := i+1 to n do

If A[Nmin] > A[j] then Nmin := j; P := A[Nmin];

A[Nmin] := A[i];

A[i] := P;

End;

[Всего голосов: 6    Средний: 3.5/5]