Материал: Лабораторная работа №4 Массивы. Сортировка и поиск

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

Пузырьковая сортировка

Это первый вид сортировки с которым сталкиваются программисты при изучении программирования. Это самый медленный вид сортировки, но и самый простой для реализации алгоритм сортировки.

В качестве примера рассмотрим сортировку массива по возрастанию. Работает алгоритм следующим образом, проверяем два соседних элемента если первый элемент больше второго, то переставляем их местами. Продолжаем выполнять выше описанные действия до тех пор пока не будет отсортирован весь массив. В наихудшем случае минимальный элемент будет находится в конце массива. Так как, за одну итерацию элемент перемещается только на одну позицию, то потребуется n-1 итерация для сортировки всего массива. Программа реализующая данный алгоритм приведена в листинге 8.

Листинг 8

program BubbleSort;

{$APPTYPE CONSOLE}

const n=10;//длина массива

var a:array [0..n-1] of integer; i, j:integer;

buf:integer; begin

//инициализируем массив случайными числами

Randomize;

for i:=0 to n-1 do a[i]:=random(100);

//выводим значения не отсортированного массива writeln('Source array');

for i:=0 to n-1 do write(a[i], ' '); writeln;

writeln;

//сортируем массив for i:=0 to n-1 do

for j:=0 to n-2 do if a[j]>a[j+1] then

begin buf:=a[j]; a[j]:=a[j+1]; a[j+1]:=buf;

end;

writeln('Sort array');

//выводим значения отсортированного массива for i:=0 to n-1 do write(a[i], ' ');

readln;

end.

Приведенный ниже алгоритм можно немного улучшить следующим образом. Если массив будет отсортирован раньше, чем за n-1 итерацию, то можно досрочно завершить внешний цикл. Приведенный алгоритм реализован в программе приведенной в листинге 9.

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

Листинг 9

program BubbleSort2;

{$APPTYPE CONSOLE}

const n=10;//длина массива

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

flag:Boolean;

buf:integer; begin

//инициализируем массив случайными числами

Randomize;

for i:=0 to n-1 do a[i]:=random(100);

//выводим значения не отсортированного массива writeln('Source array');

for i:=0 to n-1 do write(a[i], ' '); writeln;

writeln;

//сортируем массив flag:=False;

while not flag do begin

flag:=True;

for i:=0 to n-2 do if a[i]>a[i+1] then

begin buf:=a[i]; a[i]:=a[i+1]; a[i+1]:=buf; flag:=False;

end;{for}

end;{while}

writeln('Sort array');

//выводим значения отсортированного массива for i:=0 to n-1 do write(a[i], ' ');

readln;

end.

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

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

Листинг 10

program SelectSort;

{$APPTYPE CONSOLE}

const n=10;//длина массива

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

var a:array [0..n-1] of integer; i, j:integer;

buf:integer;

minIndex:Integer; begin

//инициализируем массив случайными числами

Randomize;

for i:=0 to n-1 do a[i]:=random(100);

//выводим значения не отсортированного массива writeln('Source array');

for i:=0 to n-1 do write(a[i], ' '); writeln;

writeln;

//сортируем массив for i:=0 to n-2 do

begin minIndex:=i;

for j:=i+1 to n-1 do

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

if minIndex<>i then begin

buf:=a[i];

a[i]:=a[minIndex];

a[minIndex]:=buf;

end; end;{for i}

writeln('Sort array');

//выводим значения отсортированного массива for i:=0 to n-1 do write(a[i], ' ');

readln;

end.

Рассмотрение других методов сортировок продолжим в последующих лабораторных работах.

Задания к лабораторной работе

1.Наберите и отладьте программы приведенные в лабораторной работе.

2.Напишите программу для нахождения среднего значения массива по формуле

∑n ai

aср = i=0n

3.Напишите программу для вычисления скалярного произведения векторов.

4.Напишите программу для умножения двух матриц.

5.Реализуйте алгоритм последовательного поиска с помощью цикла while do.

6.Реализуйте алгоритм, приведенный в листинге 9, только с помощью цикла for to do.

7.Напишите программу, реализующую ввод и вывод списка студентов, а также его сортировку.

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

Вопросы к лабораторной работе

1.Как задается тип множество?

2.Какие операторы для работы с множествами вы знаете?

3.Как задать массив в Object Pascal?

4.Объясните алгоритм работы бинарного поиска?

5.Объясните алгоритм пузырьковой сортировки7

6.Объясните алгоритм сортировки методом выбора?

7.Сколько перестановок в худшем случае надо сделать при применении алгоритма сортировки методом выбора?

8.Сколько сравнений в худшем случае нужно сделать при применении алгоритма пузырьковой сортировки?