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

Лабораторна робота № 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:= і; x := a[i]; FORj:= i+1TO n DO.

IF a[j].