Этот метод, называемый сортировкой простым выбором, в не. котором смысле противоположен сортировке простыми вклю. чениями; при сортировке простыми включениями на каждом шаге рассматривается только один очередной элемент вход, ной последовательности и все элементы готового массива для нахождения места включения; при сортировке простым выбо-ром рассматриваются все элементы входного массива для нахождения элемента с наименьшим ключом, и этот один очередной элемент отправляется в готовую последовательность. Весь алгоритм сортировки простым выбором пред. ставлен в виде программы 2.3.

procedure straightselection; var i,j,k: index; x: item; begin fotX:= 1 to n-1 do

begin A; := i; x := a[i]; forj :~ i+l to и do

if й[7] .key < X .key then begin A: := j; x a[j] end ;

a[k] := a\i]; аЦ] := x;

Программа 2.3. Сортировка простым выбором.

Анализ сортировки простым выбором. Очевидно, что число С сравнений ключей не зависит от начального порядка ключей. В этом смысле можно сказать, что сортировка простым выбором ведет себя менее естественно, чем сортировка простыми включениями. Мы получаем

Минимальное число пересылок равно

M , = 3(r-1) (2.6)

в случае изначально упорядоченных ключей и принимает наибольшее значение:

M 3x=trunc (-) + 3(п-1).

если вначале ключи расположены в обратном порядке. Среднее Мер. трудно определить, несмотря на простоту алгоритма. Оно зависит от того, сколько раз определяется, что kj меньше всех предшествующих величин ki, k,-i при просмотре последовательности чисел ki, kn. Это значение, взятое

среднем для всех перестановок п ключей, число которых

- n-e гармоническое число

Я„ = 1+ + --+...+- (2.7)

т^гКнут.т. 1).- -

Число Нп можно выразить как

Я„ = 1п + у + -7+.... (2.8)

J,дe у = 0.577216... - эйлерова константа. Для достаточно больших п мы можем опустить дробные слагаемые и, таким образом, аппроксимировать среднее число присваиваний на (-М проходе следующим образом:

Тогда среднее число пересылок Мер. при сортировке выбором есть сумма Fi, где / принимает значения от 1 до п:

Мер, = Е = (Y + 1) + S In /.

Аппроксимируя далее сумму отдельных слагаемых с помощью интеграла

In л; йл; = л; (In л; - 1) I = п In п - п + 1,

получаем приближенное значение

Mep.-R(ln + Y). (2.9)

Мы можем сделать вывод, что обычно алгоритм сортировки простым выбором предпочтительней алгоритма сортировки простыми включениями, хотя в случае, когда ключи заранее рассортированы или почти рассортированы, сортировка простыми включениями все же работает несколько быстрее.

2.2.3. Сортировка простым обмено>х.

Классификация методов сортировки не всегда четко определена. Оба представленных ранее метода можно рассматривать как сортировку обменом. Однако в этом разделе мы Остановимся на методе, в котором обмен двух элементов является основной характеристикой процесса. Приведенный иже алгоритм сортировки простым обменом основан па

принципе сравнения и обмена пары соседних элементов до пор, пока не будут рассортированы все элементы.

Как и в предыдущих методах простого выбора, мы совер, щаем повторные проходы по массиву, каждый раз просеива, наименьщий элемент оставшегося множества, двигаясь к д^. вому концу массива. Если, для разнообразия, мы будем рас сматривать массив, расположенный вертикально, а не горц, зонтально и - при помощи некоторого воображения - пред, ставим себе элементы пузырьками в резервуаре с- водой, сб.-ладающими весами , соответствующими их ключам, то кад. дый проход по массиву приводит к всплыванию пузырька на соответствующий его весу уровень (см. табл. 2.3). Этот ые-

Таблица 2.3. Пример сортировки методом пузырька

-----ч^-tn----ta - г со

Начальные н и н н П и и

44 55 12 42 94 18

-06 06. 06 06 06 06 06

44 *-12 12 12 12 12 12

55 1 44 г^18 18 18 18 18

12-J 55 1 44 н-42 42 42 42

Л9 , .1Я-I W 1 АЛ лл

42 94 18-

18- 55 1 44-44 44 44

42 42-J 55 55-Ч-55 55

94 167 67 67 67- -67

67 67 67-* 94 94 94 94 94

тод широко известен как сортировка методом пузырька. Его простейший вариант приведен в программе 2.4.

procedure bubblesort;

var index; x: item; begin for J := 2 to и do

begin forj := n downto i do

if alj-1] .key > аЦ] Jcey then begin X := dU-1]; aU-1] := a[j]; a[j] := x end

end [btAblesort]

Программа 2.4. Сортировка методом пузырька.

, Этот алгоритм легко оптимизировать. Пример в табл. 2.3 показывает, что три последних прохода никак не влияют порядок элементов, поскольку те уже рассортированы. Очевидный способ улучшить данный алгоритм - это запоминать, производился ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм может закончить работу-Этот процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и место (индекс) последнего