Лабораторна робота № 1

Порівняти ефективність методів сортування масивів:

Метод прямого вибору і метод сортування за допомогою дерева.

Сортування за допомогою прямого вибору

Цей прийом заснований на наступних принципах:

1. Вибирається елемент з найменшим ключем.

2. Він міняється місцями з першим елементом ai.

3. Потім цей процес повторюється з рештою n-1 елементами, n-2елементами і т.д. до тих пір, поки не залишиться один, найбільшийелемент.

Процес роботи цим методом з тими ж вісьмома ключами, що і в табл. 2.1,наведено в табл. 2.2. Алгоритм формулюється так:

FORi: = ITO n-1 DO

привласнити k індекс найменшого з a [i],,, a [nJ; поміняти місцями a [i ] іa [j];

end

Такий метод - його називають прямим вибором - в певному сенсіпротилежний прямому включенню. При прямому включенні на кожному кроцірозглядаються тільки один черговий елемент початкової послідовності івсі елементи готової послідовності, серед яких відшукується точкавключення; при прямому виборі для пошуку одного елемента з найменшим ключемпроглядаються всі елементи початкової послідовності і знайденийпоміщається як черговий елемент в готову послідовність. Повністюалгоритм прямого вибору приводиться в прогр. 2.3.

Таблиця 2.2. Приклад сортування за допомогою прямого вибору

Початкові ключі

44 55 12 42 94 18 06 67

06 55 12 42 94 18 44 67

06 12 55 42 94 18 44 67

06 12 18 42 94 55 44 67

05 12 18 42 94 55 44 67

05 12 13 42 44 55 94 67

06 12 18 42 44 55 94 67

06 12 18 42 44 55 67 94

PROCEDURE StraightSfcleclion;

VAR i, j, k: index; x: item; BEGIN

FORi: = 1 TO n-1 DO k: = i; x: = a [i]; FORj: = i +1 TO n DO

IF a [j ]