Сортировка выбором

Принцип метода:

Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

Рассмотрите схему алгоритма прямого выбора.

Сортировка методом простого обмена. Рекурсивная сортировка.

Принцип метода:

Слева направо поочередно сравниваются два соседних элемента, и если их взаимное расположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный (или минимальный) элемент ("всплыл" первый "пузырек"). Поскольку максимальный (или минимальный) элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n-1)-го элемента. И так далее. Всего требуется (n-1) проход.

Задание. В тетради начертите схему работы рассмотренного алгоритма произвольно выбранного массива.

Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

Procedure Obmen(Var a : Array1); Var   i,j,f,g:integer; Begin   for i:=n downto 2 do     for j:=1 to i-1 do       if a[j]>a[j+1]         then           begin             f:=a[j];             a[j]:=a[j+1];             a[j+1]:=f;           end; End;

Задание. Составьте программу сортировки одномерного массива рассмотренным методом.

Сортировка массива с помощью рекурсии

Рассмотрим использование рекурсии для построения алгоритма сортировки значений массива.

Алгоритм реализуется следующим образом: в некотором отрезке массива выбирается центральное (серединное) значение; все элементы из левой части отрезка, превосходящие центральное значение, перемещаются в правую часть, и наоборот. На следующем шаге (для которого используются рекурсивные вызовы этой же процедуры) алгоритм повторяется для обоих частей отрезка.

Рассмотрите процедуру, упорядочивающую по возрастанию значения из массива Massiv в диапазоне индексов Left..Right.

Procedure QuickSort (Left, Right : integer; Massiv : Array1); Var   i, j, x, y : integer; Begin   i := Left;   j := Right;   x := Massiv[(Left+Right) div 2];{}   repeat     while Massiv[i]<x do       Inc(i);     while Massiv[j]>x do       Dec(j);     if i<=j       then         begin           y := Massiv[i];           Massiv[i] := Massiv[j];           Massiv[j] := y;           Inc(i);           Dec(j);         end; until i>j; if Left<j   then     QuickSort (Left, j); if i<Right   then     QuickSort (i, Right); End;

Задача. Составьте программу, реализующую рассмотренный метод. Дополните ее комментариями.

Сортировка методом слияний.

Определение. Целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов называется упорядоченным.

Использование упорядоченности позволяет создавать эффективные алгоритмы для решения многих интересных задач.

Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов.

Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[1] сравнивается с элементом В[1] и наименьший из них записывается в массив С. Если наименьшим был А[1], то на следующем шаге сравниваются А[2] и B[1], а если наименьшим был B[1], то будут сравниваться A[1] и B[2] и т.д. Если на очередном шаге окажется, что из одного входного массива все элементы переписаны в С, то переписывается элемент из другого массива.

Рассмотрим пример работы алгоритма слияния.

Пусть в массиве А содержатся 3 элемента: {5, 13, 14}, а в массиве В - 4 элемента: {7, 9, 10, 12}. Внимательно рассмотрите таблицу, в которой по шагам показано изменение переменных i, i1, i2 и действия с массивами.

Рассмотрите фрагмент решения задачи на слияние двух массивов А и В, которые содержат соответственно n1 и n2 элементов. Результирующий массив С будет содержать n1+n2 элементов.

. . . i1 := 1; i2 := 1; for i := 1 to n1+n2 do   if i1>n1     then       begin         C[i] := B[i2];         i2 := i2+1;       end     else       if i2>n2         then           begin             C[i] := A[i1];             i1 := i1+1;           end         else           if A[i1]<=B[i2]             then               begin                 C[i] := A[i1];                 i1 := i1+1;               end             else               begin                 C[i] := B[i2];                 i2 := i2+1;               end; . . .

Задача. Составьте программу, реализующую рассмотренный метод. Дополните ее комментариями.