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

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

Сортування одновимірних масивів

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

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

ü кількість присвоювань;

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

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

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

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

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

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

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

3. Сортування обміном (метод «бульбашок»).

4. Сортування підрахунком.

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

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

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

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

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

Приклад сортування вставкою за зростанням:

programvstavka;
usescrt;
varn, i, j, k, p, zb: integer;
a: array [1..255] ofinteger;
begin
clrscr; randomize;
write ('Vvedit rozmirnist masuvy: ');
readln (n);
fori:=1 tondo	Заповнення масиву випадковими числами в діапазоні [-100; 100]
begin
a [ i ]:= random (200)-100;
end;
clrscr;
writeln ('Pochatkovuj masuv:');
fori:=1 tondowrite (a [ i ]:5);	виведення заповненого масиву на екран
fori:=2 tondo	початок сортування (з 2-го до n -ного елемента)
begin
zb:= a [ i ];	збереження поточного елемента
j:=1;
while (a [ j ]< a [ i ]) do j:= j +1;	пошук місця для цього елемента
fork:= i -1 downtojdoa [ k +1]:= a [ k ];	зсув елементів і звільнення потрібного місця
a [ j ]:= zb;	вставка збереженого елемента
end;
writeln; writeln;
writeln ('Vidsortirovanuj masuv:');
fori:=1 tondowrite (a [ i ]:5);	виведення відсортованого масиву
readln
end.

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

Приклад сортування:

program vubir;
uses crt;
var n, i, j: integer; x: real;
a: array [1..255] of real;
begin
clrscr; randomize;
write ('Vvedit rozmirnist masuvy: ');
readln (n);
for i:=1 to ndo
a [ i ]:=(random (100)-50)/5;	Заповнення масиву випадковими числами
writeln ('Pochatkovuj masuv:');
for i:=1 to ndo write (a [ i ]:6:1);	виведення заповненого масиву на екран
for i:=1 to n -1 do	початок перебору всіх елементів масиву
for j:= i +1 to ndo	розгляд всіх елементів після i -того
if a [ j ]< a [ i ]	порівняння поточного елементу з усіма наступними
then begin
x:= a [ i ];	обмін місцями поточного елемента з найменшим, що розташований після нього
a [ i ]:= a [ j ];
a [ j ]:= x
end;
writeln; writeln;
writeln ('Vidsortirovanuj masuv:');
for i:=1 to ndo write (a [ i ]:6:1);	виведення відсортованого масиву
readln
end.

Дата добавления: 2014-01-07