- •Лекція №8-9
- •Перерахований тип даних
- •Діапазонний тип
- •Особливості роботи з користувацькими простими типами
- •Регулярний тип даних (масиви)
- •Порядок роботи з масивом:
- •Одновимірні масиви Опис одновимірних масивів
- •Двовимірні масиви
- •Сортування одновимірних масивів
- •Використання одновимірних масивів
- •Одновимірні масиви, що складаються з констант
- •Сортування вставкою (включенням).
- •Сортування вибором (виділенням).
- •Сортування обміном (метод «бульбашки»).
- •Сортування підрахунком.
Сортування вставкою (включенням).
Принцип методу Масив розділяється на дві частини: відсортовану і невідсортовану. Елементи з невідсортованої частини по черзі вибираються і вставляються у відсортовану частину так, щоб не порушити в ній вже встановлений порядок елементів. На початку роботи алгоритму в якості відсортованої частини масиву приймають тільки один перший елемент, а в якості невідсортованої – всі інші елементи. Таким чином, необхідно виконати (n-1) перегляд таблиці, кожний з яких буде включати чотири дії:
-
взяття чергового невідсортованого елемента і збереження його в додатковій змінній;
-
пошук позиції у відсортованій частині масиву, у якій присутність взятого елемента не порушить упорядкованості елементів;
-
зсув елементів масиву вправо, щоб звільнити знайдену позицію вставки;
-
вставка взятого елемента в знайдену позицію.
Приклад сортування вставкою за зростанням:
|
program vstavka; |
|
|
uses crt; |
|
|
var n, i, j, k, p, zb: integer; |
|
|
a: array [1..255] of integer; |
|
|
begin |
|
|
clrscr; randomize; |
|
|
write ('Vvedit rozmirnist masuvy: '); |
|
|
readln (n); |
|
|
for i:=1 to n do |
Заповнення масиву випадковими числами в діапазоні [-100; 100] |
|
begin |
|
|
a[i]:=random(200)-100; |
|
|
end; |
|
|
clrscr; |
|
|
writeln ('Pochatkovuj masuv:'); |
|
|
for i:=1 to n do write (a[i]:5); |
виведення заповненого масиву на екран |
|
for i:=2 to n do |
початок сортування (з 2-го до n-ного елемента) |
|
begin |
|
|
zb:=a[i]; |
збереження поточного елемента |
|
j:=1; |
|
|
while (a[j]<a[i]) do j:=j+1; |
пошук місця для цього елемента |
|
for k:=i-1 downto j do a[k+1]:=a[k]; |
зсув елементів і звільнення потрібного місця |
|
a[j]:=zb; |
вставка збереженого елемента |
|
end; |
|
|
writeln; writeln; |
|
|
writeln ('Vidsortirovanuj masuv:'); |
|
|
for i:=1 to n do write (a[i]:5 ); |
виведення відсортованого масиву |
|
readln |
|
|
end. |
|