Пересылка записи

end

Математическое ожидание количества пересылок в цикле While при условии, что новый элемент вставляется в уже отсортированную последовательность длиной i равна i/2, т.е. в среднем придется просмотреть половину последовательности, до тех пор, пока не найдется подходящее место.

Получается, что в начале работы алгоритма сортировки вставками (начинаем с i =2) у нас имеется отсортированная последовательность из одного элемента, количество перестановок может быть либо 1 (1-й элемент меняем местами со 2‑ м элементом), либо 0 (т.к. 2-й элемент уже находится на своем месте).

При i =3 (длина отсортированной последовательности равна двум) возможны три варианта: 0 пересылок, 1 пересылка, 2 пересылки. По определению математического ожидания количество пересылок равно 1.

Таким образом, при i = n (длина отсортированной последовательности равна n –1) количество пересылок может быть от 0 до n –1. Математическое ожидание количества пересылок при условии, что в среднем придется просмотреть половину последовательности из n –1 элемента, будет равно (n ‑ 1)/2.

Тогда

M_ср=3(n-1)+ =3(n-1)+1/2(1+2+...+(n-1))=

=3(n-1)+1/2·n·(n-1)/2=3(n-1)+(n²-n)/4=

=3n-3+(n²-n)/4=(12n-12+n²-n)/4=

=(n²+11n-12)/4.

15) Методы сортировок: алгоритм быстрой сортировки. Анализ сложности алгоритма быстрой сортировки.

Алгоритм:

· выбрать элемент, называемый опорным.

· сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.

· повторить рекурсивно для «меньших» и «больших».

procedure hoarsort(var mas: array[1..100] of integer; a, b: integer); //при начальном вызове a=1 b=количеству элементов массива

var i, j, m, k: integer;

begin

i: =a;

j: =b;

if (a> =b) then

else

begin

m: =mas[(a+b)div 2];

while i< =j do

begin

while mas[i]> m do

inc(i);

while mas[j]< m do

j: =j-1;

if i< =j then

begin

k: =mas[i];

mas[i]: =mas[j];

mas[j]: =k;

inc(i);

j: =j-1;

end;

end;

hoarsort(mas, a, j);

hoarsort(mas, i, b);

end;

end;

+ оценка сложности

16) Обзор методов сортировок: Сортировка Шелла, пирамидальная сортировка, сортировка слияниями, Шейкер – сортировка, сортировка подсчетом, цифровая сортировка...

Сортировка Шелла:

Идея метода: делим массив на k1 групп, каждую группу сортируем, далее делим массив на k2 групп (k2< k1), снова сортируем полученные группы, далее на k3 групп (k3< k2< k1), и т.д. в конце делим на kn групп, причем kn = 1, т.е. в конце сортируем весь массив.

Значения k1, k2, k3, …, kn называются приращениями.

Лучшим считается выбор в качестве значений приращений взаимно простых чисел.