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


 

8.5. Упорядкування елементів значення рядкової величини

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

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

Приклад 8.5.1

Var

S: string;

I, j: integer; k:char; begin

Write (‘Введіть рядок’); readln (S);

For i := 1 to length(S)-1 do for j := 1 to length(S)-i do if S[j] > S[j+1] then

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

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

S[j+1] := k

End;

Writeln (‘Упорядкований рядок: ‘, S);

End.

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

Приклад 8.5.2

Var S: string; i, j, k: integer; P:char;

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

Begin

Write (‘Введіть рядок’); readln (S);

For i := 1 to length(S) do

Begin

P := S[i]; j := 1;

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

For k := i-1 downto j do S[k+1] := S[k]; S[j] := P;

End;

WriteLn(‘ Упорядкований рядок: ‘, S); end.

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

Приклад 8.5.3

Var S: string;

I, j, k,nm: integer;

P:char;

Begin

Write (‘Введіть рядок’); readln (S);

Write (‘Уведіть рядок’, S); readln (S);

For i := 1 to length(S)-1 do

Begin nm := i;

For j := i+1 to length(S) do if S[nm] > S[j] then nm := j; P := S[nm];

S[nm] := S[i];

S[i] := P;

End;

WriteLn(‘Упорядкований рядок: ‘, S); end.

Слід мати на увазі при всіх підходах до сортування, що перші букви алфавіту будуть менші за останні букви, тому частіше рядкові та символьні типи даних сортують за зростанням (як у прикладах 8.5.1–8.5.3).

Перевіряємо себе

 

Що ви розумієте під упорядкуванням даних? image

За якими ознаками найкраще порівнювати символи? image

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

Обґрунтуйте, чому символи сортують переважно за зростанням? image

Яка рядкова величина більша: “баба” чи “дід”? Чому? image

Як порівнюються між собою рядкові записи чисел порівняно зі самими числами? image

 

Виконуємо

1.image Напишіть програму сортування слів у реченні. image

2. Побудуйте блок-схему методу впорядкування вставлянням. image

3.image Побудуйте блок-схему впорядкування вибором. image

Побудуйте блок-схему впорядкування обміном. image

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