3. Схемы алгоритмов пузырьковой и шейкерной сортировок

Н а рисунке 1 представлена схема алгоритма пузырьковой сортировки, а на рисунке 2 — шейкерной сортировки.

Рис. 1. Схема алгоритма пузырьковой сортировки.

Рис. 2. Схема алгоритма шейкерной

сортировки.

4. Пример программы на языке Pascal

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

program lab5;

{$APPTYPE CONSOLE}

uses

SysUtils;

const n = 20;

var a:array [0..n] of real;

var i,j:integer; x:real;

begin

Write('Упорядочивание последовательности, состоящей из 20');

Writeln('случайных чисел, с помощью пузырьковой сортировки');

Writeln('Несортированная последовательность:');

randomize;

for i:=0 to n-1 do

begin

a[i]:=random(100);

write(a[i],' ');

end;

for i:=1 to n-1 do

begin

for j:=n-1 downto i do

begin

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

begin

x:=a[j-1];

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

a[j]:=x;

end;

end;

end;

Writeln('Отсортированная последовательность:');

for i:=0 to n-1 do

begin

Write (a[i], ' ');

end;

readln;

end.

5. Варианты заданий

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

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

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

4. Упорядочить массив методом прямой обменной сортировки, состоящий из n² элементов (где n=1, 2, 3, ...) и вывести его в виде спирали (матрицы n на n).

Пример:

исходный массив для n=3:

1 9 8 2 3 7 6 4 5

после упорядочивания:

1 2 3 4 5 6 7 8 9

вывод:

1 2 3

8 9 4

7 6 5

5. Задается массив, упорядоченный по возрастанию. В него добавляются три произвольных элемента. Используя метод пузырьковой сортировки, упорядочить массив по возрастанию.

6. Задается массив, упорядоченный по убыванию. В него добавляются пять произвольных элементов. Используя метод шейкерной сортировки, упорядочить массив по возрастанию.

7. Даны два массива. Построить третий массив, который включает элементы двух предыдущих. Отсортировать его по возрастанию, используя метод прямой сортировки обменом. Если встречаются два и более одинаковых элемента, удалить их, оставив один.

8. Даны два массива A и B, каждый из которых состоит из n элементов (n=1, 2, 3, ...). Построить третий массив C, таким образом, что c_i=a_i+b_i (i=1,…,n). Отсортировать его по возрастанию, используя метод прямой обменной сортировки.

9. Дан массив, состоящий более чем из десяти элементов. Используя методы прямой сортировки обменом, упорядочить первую его половину по возрастанию, а вторую – по убыванию.

10. Даны два массива A и B, каждый состоит из n элементов (n=1,2,3, ...). Построить третий массив C, при условии, что c_i=a_i×b_i (i=1,...,n). Отсортировать его по убыванию, используя метод прямой обменной сортировки.

11. Даны два массива. Построить третий массив, который включает элементы двух предыдущих. Отсортировать его по убыванию, используя прямой метод сортировки обменом. Если встречаются два и более одинаковых элемента, оставить только один из них.

12. Даны два массива A и B, каждый состоит из n элементов (n=1,2,3,...). Построить третий массив C, при условии c_i=a_i–b_i (i=1,...,n). Отсортировать его по возрастанию, используя метод прямой обменной сортировки.

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

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

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

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