Сортировка пузырьком (обменом)

Алгоритм. Последовательно сравниваются пары соседних элементов x_k и x_k+1 (k= 1, 2, ... , n-1). Если x_k > x_k+1, то они меняются местами. Тем самым наименьший элемент окажется на своем месте в начале массива (“всплывет пузырек”). Затем этот метод применяется ко всем элементам, кроме первого. В результате будет найден второй элемент в отсортированном массиве и т.д.

Пример. Пусть дан массив {4, 5, 2, 3, 9, 1}, который необходимо упорядочить по возрастанию, используя метод пузырька.

ш1 4 5 2 3 9 1 всплывает 1.

ш2 1 4 5 2 3 9 всплывает 2.

ш3 1 2 4 5 3 9 всплывает 3.

ш4 1 2 3 4 5 9 всплывает 4.

ш5 1 2 3 4 5 9 всплывает 5.

ш6 1 2 3 4 5 9 всплывает 9.

ш7 1 2 3 4 5 9 результат.

program bublesort;

const n = 30;

var a: array [1..n] of integer;

x, i, j: integer;

begin

for i := 1 to n do

read(a[i]); {формирование массива}

for i := 2 to n do

for j := n downto i do {поиск места элемента в упорядоченной части}

if a[j - 1] > a[j] then

begin

x := a[j - 1]; {меняются местами a[j-1] и a[j]}

a[j-1] := a[j];

a[j] := x

end;

for i := 1 to n do

writeln (a[i]);

end.

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

Алгоритм. Сначала находим в массиве элемент с минимальным значением среди элементов с индексами от 1-го до n-го и меняем местами найденный элемент с первым. После этого первый элемент из обработки можно исключить. На втором шаге находим минимальный элемент среди элементов с индексами от 2-го до n-го и меняем его местами со вторым элементом. Продолжаем повторять поиск минимального элемента и его обмен со всем элементами с 3-го до n-1-го.

Пример. Пусть дан массив {4, 5, 2, 3, 9, 1}, который необходимо упорядочить по возрастанию, используя метод выбора.

ш1 4 5 2 3 9 1

ш2 1 5 2 3 9 4

ш3 1 2 5 3 9 4

ш4 1 2 3 5 9 4

ш5 1 2 3 4 9 5

ш6 1 2 3 4 5 9

program sort_select;

const n = 30;

var a: array [1..n] of integer;

k, i, j, x: integer;

begin

for i := 1 to n do

read(a[i]); {формирование массива}

for i := 1 to n - 1 do

begin

k := i; {кандидат на минимальный - первый элемент из

неотсортированной части}

for j := i + 1 to n do {поиск минимального в неупорядоченной части}

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

x := a[i]; {меняются местами a[i] и минимальный}

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

end;

for i := 1 to n do

writeln (a[i]);

end.

Сортировка фон Неймана (слиянием)

Заданы два упорядоченных по возрастанию элементов одномерных массива: a - размерности n и b - размерности m. Требуется получить третий массив с - размерности n+m, который содержал бы все элементы исходных массивов, упорядоченные по возрастанию.

Алгоритм решения этой задачи известен как "сортировка фон Неймана" или сортировка слиянием. Идея алгоритма состоит в следующем. Сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен таким же образом, как исходные массивы.

program confluence;

const n = 10;

m= 20;

l = n + m;

var x: array [1..n] of integer;

y: array [1..m] of integer;

z: array [1..l] of integer;

k, i, j: integer;

begin

for i := 1 to n do

read(x[i]); {формирование первого упорядоченного массива}

for i := 1 to m do

read(y[i]); {формирование второго упорядоченного массива}

i := 1; j := 1; l := 1; {i -индекс первого массива, j - индекс второго массива

l -индекс результирующего массива}

while (i <= n) and (j <= m) do {пока не закончились элементы в одном из

массивов}

if x[i] < y[i] then {переписываем элемент из первого массива}

begin

z[k] := x[i];

i := i + 1; k := k + 1

end

else { переписываем элемент из второго массива}

begin

z[k] := y[j];

j := j + 1; k := k + 1

end;

while i <= n do {если не закончились элементы в первом массиве,}

begin {переписываем их в результирующий массив}

z[k] := x[i]; i := i + 1; k := k +1

end;

while j <= m do {если не закончились элементы во втором массиве,}

begin {переписываем их в результирующий массив}

z[k] := y[j]; j := j + 1; k := k +1

end;

for i := 1 to l do {вывод на экран упорядоченного массива, полученного}

writeln (z[i]); {слиянием}

end.

Задача. Задан одномерный массив. Нужно упорядочить только отрицательные его элементы, оставив положительные на старых местах.

Решение. Особенностью этой задачи является то, что сортировать надо не все элементы массива, а только отрицательные. При этом можно использовать любой метод сортировки.

Вариант 1. Перепишем отрицательные элементы во вспомогательный массив, отсортируем его, а затем перепишем элементы из отсортированного вспомогательного массива в позиции отрицательных элементов в исходном массиве.

program task;

const n = 20;

var mas, mas1: array [1..n] of real; {исходный, вспомогательный массивы}

i, j, t, k: integer;

x: real;

begin

for i := 1 to n do

read (mas[i]); {ввод массива}

t := 0; {формирование массива отрицательных элементов}

for i := 1 to n do

if mas[i] < 0 then begin t := t + 1; mas1[t] := mas[i] end;

for i := 1 to t - 1 do {сортировка вспомогательного массива}

begin

k := i;

for j := i + 1 to t do

if mas1[j] < mas1[k] then k := j;

x := mas1[i];

mas1[i] := mas1[k]; mas1[k] := x

end;

t := 1;

for i := 1 to n do

if mas[i] < 0 then begin mas[i] := mas1[t]; t := t +1 end;

for i := 1 to n do

write (mas[i], ‘ ‘);

end.

Вопрос. Какой алгоритм сортировки использован в этой программе?

Вариант 2. Используется сортировка без вспомогательного массива, но сортируются только отрицательные элементы.

program task;

const n = 20;

var mas: array [1..n] of real; {исходный массив}

i, j, t: integer;

r: real;

begin

for i := 1 to n do

read (mas[i]); {ввод массива}

for i := 1 to n do

begin

mas[i] := - 10 + random (20);

write (mas[i], ‘ ‘);

end;

for i := 1 to n - 1 do

if mas[i] < 0 then {проверка отрицательности элемента}

for j := i + 1 to n do

if mas[j] < 0 {проверка отрицательности элемента}

then if mas[i] > mas[j]

then begin r := mas[i];

mas[i] := mas[j];

mas[j] := r

end;

for i := 1 to n do

write (mas[i], ‘ ‘);

end.

Вопросы. 1. Какой алгоритм сортировки используется в этой программе?

2. Указать диапазон чисел, которыми заполняется массив.

Задача. Известны расстояния от дома любителя плова до любой из n существующей в городе П. закусочной. Известна цена плова в каждой закусочной. Проверьте утверждение любителя плова: “Чем дальше закусочная, тем меньше цена на плов”.

Решение. Исходные данные представим в виде двумерного массива из n столбцов (количество закусочных) и двух строк: первая строка - расстояние до закусочной, вторая - стоимость плова в этой закусочной. Далее необходимо упорядочить двумерный массив в порядке возрастания элементов первой строки, т.е. в порядке возрастания расстояний. Если после этого преобразования, вторая строка будет упорядочена по убыванию, значит, любитель плова прав.

program task;

const n = 20; {количество закусочных}

var a: array [1..2, 1..n] of integer; {исходный массив}

i, x, k : integer;

f: boolean;

begin

randomize;

for i := 1 to n do

begin

a[1, i] := random (100) + 10; {расстояние}

a[2, i] := random (30) + 5; {стоимость плова}

end;

{упорядочивание массива}

for i := 1 to n - 1 do

begin

k := i;

for j := i + 1 to n do

if a[1, j] < a[1, k] then k := j;

x := a[1, i]; a[1, i] := a[1, k]; a[1, k] := x;

x := a[2, i]; a[2, i] := a[2, k]; a[2, k] := x;

end;

{проверяем, упорядочена ли вторая строка по убыванию}

i := 1; f := true; {считаем, что любитель плова прав}

while (i <= n - 1) and f do {пока не проверили все закусочные и любитель

плова прав}

if a[2, i] < a[2, i + 1] then f := false {нарушено условие убывания}

else i := i + 1;

if f then writeln (‘любитель плова прав’)

else writeln (‘любитель плова не прав’);

end.

Тест 1. Расстояние 85 47 10 30 100

Стоимость плова 14 15 25 20 5

После упорядочивания: 10 30 47 85 100

25 20 15 14 5 Ответ: “Любитель плова прав”.

Тест 2. Расстояние 85 47 10 30 100

Стоимость плова 20 17 5 15 5

После упорядочивания: 10 30 47 85 100

5 15 17 20 5 Ответ:“Любитель плова не прав”.

Упражнения.

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

2. Известны цены на землянику на n рынках Перми. Известно расстояние от дома покупателя до каждого рынка. Найдите номер рынка, на котором можно дешевле всего купить ягоды, если покупатель согласен пройти расстояние не более r км.

3. Имеется n озер. Для каждого озера известно среднее количество рыбы в кг, которую можно выловить за день рыбалки. Известны расстояния от каждого озера до города П. Укажите озеро, где рыбак может поймать больше всего рыбы, если он согласен пройти до места рыбалки не менее p км, но не более r км.

4. В городе П. имеется n гостиниц известной вместимости. Известны расстояния от каждой гостиницы до вокзала. Укажите номера гостиниц, в которых можно разместить не менее R гостей так, чтобы они находились как можно ближе к вокзалу.