Алгоритм простого выбора (выбором)

Методы внутренней сортировки

Пусть определен следующий тип данных

type mas = array [1.. n ] of typel;

var a: mas;

Алгоритмы простой сортировки

Алгоритм простой вставки (прямого включения)

Метод основан на использовании двух подпоследовательностей:

ü готовую отсортированную часть, начиная с первого элемента (a ₁.. a _i);

ü входную, из которой вначале выбираются элементы (a _i.. a _n).

На каждом i –ом шаге сортировки из входной последовательности выбирается j –ый элемент и в готовой последовательности определяется соответствующее место вставки элементов. На шаге n – 1 массив отсортирован.

Отсортированная часть рассматривается с конца. Элемент a _i сравнивается последовательно с a_i-1, a_i-2 … и ищется место a _i в упорядоченной последовательности. Ищется первый элемент a _j < a _i и a _i вставляется правее a _j.

Если выполняется сортировка в порядке возрастания, то осуществляется поиск соответствующего места «справа – налево» до тех пор пока выполняется условие x < a _j, где x – сортируемый элемент.

Пусть дана последовательность целых чисел:

44 55 12 42 94 18 6 67

1) 44 55 12 42 94 18 6 67

2) 12 44 55 42 94 18 6 67

3) 12 42 44 55 94 18 6 67

4) 12 18 42 44 45 94 6 67

…

procedure IncludeSort;

var i, j: integer;

x: typel;

Begin

for i: = 2 to n do

Begin

x: = a [ i ]; j: = i – 1;

while (a [ i ] > x) and (j > 0) do

Begin

a [ j + 1]: = a [ j ]; j: = j – 1;

end;

a [ j + 1]: = x;

end;

end;

Оценка» ½ перемещений и пересылок

C_min = n – 1 M_min = 3(n –1)

C_ср = (n² + n – 2)/4 M_ср = (n² + 9n –10)/4

C_max = (n² + n – 4)/4 M_max = (n² + 3n –4)/4

Общее число пересылок и перемещений

T_n = О (n²) C = О (n ²) M = O (n ²)

В качестве улучшения данного алгоритма придется ускорить поиск места для вставки с помощью метода половинного деления (заменить цикл while в упорядоченной части).Число сравнений уменьшится C = О (n log ₂ n), а число перестановок то же, что не дает значительного эффекта.

Если алгоритм применить к отсортированному массиву, то цикл while вырождается, т.е алгоритм реагирует на предварительную отсортированность массива (хотя бы частичную).

Алгоритм простого выбора (выбором)

Данный метод основан на поиске элемента из оставшейся последовательности и его перестановку на место, с которого начинался поиск

44 55 12 42 94 18 6 67

Иначе говоря данный алгоритм является пошаговым и на каждом шаге массив разбивается на два подмассива:

ü отсортированный

ü неотсортированный

i = 1, …, n – 1.

Причем на каждом шаге отыскивается минимальный элемент и меняется местами с первым элементом неотсортированной части. В результате неотсортированная часть становится на один элемент короче.

В нашем примере

1) 6 55 12 42 94 18 44 67

2) 6 12 55 42 94 18 44 67

3) 6 12 18 42 94 55 44 67

4) 6 12 18 42 44 55 94 67

5) 6 12 18 42 44 55 67 94

Алгоритм:

procedure SelectSort;

var i, j, m: integer; x: typel;

Begin

for i: = 1 to n – 1 do

Begin

m: = i;

for j: = i +1 to n do

if a [ j ] < a [ m ] then m: = j;

x: = a [ i ]; a [ i ]: = a [ m ]; a [ m ]: = x;

end;

end;

Оценка по числу сравнений:

M_min = 3(n–1) M_ср = n (ln (n)+ g) M_max = n ²/4 + 3(n –1)

g – константа Эйлера (0.577216).

Число сравнений C = O (n ²); число перемещений M = O (n log₂ n).

Общая оценка T _n = O (n ²).

Алгоритм не реагирует на предварительную сортировку.