Лабораторная работа

Тема: Поиск элементов массива. Сортировка массивов. (6 часов)

Цель: Сформировать практические навыки: реализация  процессов обработки одномерных и двумерных массивов; построение однооконных интерфейсов с помощью визуального компонента «окно» (класс TForm) и визуальных компонентов панели инструментов Standard: «метка» (класс TLabel), «редактор» (класс TEdit), «кнопка» (класс TButton), (класс TStringGrid).

Поиск минимального (максимального) элемента массива

Будем искать минимальный элемент в целочисленном массиве. Для этого немного изменим обработчик события OnClick для кнопки:

procedure TForm1.Button1Click(Sender: TObject);

var i:integer;//номер элемента, сравниваемого с минимальным

a:array[1..10] of integer; 

min:integer;//номер минимального элемента

begin

//Введем массив

for i:=1 to 10 do

//Преобразуем полученные подстроки в числа

 a[i]:=StrToInt(GetSubStr(Edit1.text,' ',i));//используем пробел в качестве разделителя

//Найдем минимальный элемент

min:=1; //пусть номер минимального элемента = 1

for i:= 2 to 10 do // начнем искать со следующего 

if a[i] < a[min] then min:=i;

Form1.caption:=IntToStr(a[min]); // выводим в заголовок

формы минимальный элемент

end;

В этом примере a[min] минимальный элемент массива, а min - номер минимального элемента. Алгоритм очень простой: сравниваем каждый следующий элемент с минимальным, если он меньше минимального, то запоминаем его номер в переменной min, и продолжаем сравнивать уже с ним.

Чтобы найти максимальный элемент, нужно изменить всего одну строку:

>>> 

if a[i] < a[min] then min:=i;

Надо заменить на:

 if a[i] > a[min] then min:=i;

Только теперь a[min] - максимальный элемент, а min - номер максимального элемента.

Поиск заданного элемента в массиве

Поступим методом простого перебора. Для этого будем перебирать все элементы массива, пока не встретим искомый элемент, или пока не дойдем до конца массива.

Элемент, совпадение с которым нам надо найти будем хранить в текстовом поле Edit2. Обработчик события OnClick нашей кнопки будет иметь такой вид:

procedure TForm1.Button1Click(Sender: TObject);

var i:integer;

a:array[1..10] of integer;

n:integer;//образец

found:boolean;

begin

//Введем массив

for i:=1 to 10 do

//Преобразуем полученные подстроки в числа

 a[i]:=StrToInt(GetSubStr(Edit1.text,' ',i));//используем пробел в качестве разделителя

n:=StrToInt(Edit2.text);

found:=false;

i:=1;

REPEAT

if a[i] = n then found:=true

 else i:=i+1;

UNTIL (i > 10) or (found = true);

if found then showmessage('Совпадение с элементом номер '+IntToStr(i));

end;

Сортировка массива

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

а[1] < а[2] < .. .< a[SIZE]

где SIZE — верхняя граница индекса массива.

Примечание

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

Существует много методов (алгоритмов) сортировки массивов.

Рассмотрим два из них:

·       метод прямого выбора;

·       метод прямого обмена.

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

Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:

1. Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального.

2. Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального.

3. И так далее до предпоследнего элемента.

Ниже представлена программа сортировки массива целых чисел по возрастанию, диалоговое окно которой изображено на рис. 5.15.

Рис. 5.15. Диалоговое окно программы сортировки массива простым выбором

Процедура сортировки, текст которой приведен в листинге 5.9, запускается нажатием кнопки Сортировка (Button1). Значения элементов массива вводятся из ячеек компонента StringGrid1. После выполнения очередного цикла поиска минимального элемента в части массива процедура выводит массив в поле метки (Label2).

Листинг 5.9. Сортировка массива простым выбором

procedure TForm1.ButtonlClick(Sender: TObject);

const

SIZE=10;

var

a:array[1..SIZE] of integer;

min:integer; { номер минимального элемента в части

массива от i до верхней границы массива }

j:integer; { номер элемента, сравниваемого с минимальным }

buf:integer; { буфер, используемый при обмене элементов массива }

i,k:integer;

begin

// ввод массива

for i:=l to SIZE do

a[i]:=StrToInt(StringGridl.Cells[i-1,0]) ; Iabel2.caption:='';

for i:=l to SIZE-1 do begin

{ поиск минимального элемента в части массива от а[1] до a[SIZE]} min:=i;

for j:=i+l to SIZE do if a[j] < a [min]

then min:=j;

{ поменяем местами a [min] и a[i] }

buf:=a[i]; a[i]:=a[min]; a[min]:=buf;

{ вывод массива }

for k:=l to SIZE do

Label2.caption:=label2.caption+' '+IntTostr(a[k]);

Label2.caption:=label2.caption+#13; end;

Label2.caption:=label2.caption+#13+'MaccMB отсортирован.';

end;

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

Рис. 5.16. Диалоговое окно программы Сортировка массива

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

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

На рис. 5.17 цифрой 1 обозначено исходное состояние массива и перестановки на первом проходе, цифрой 2 — состояние после перестановок на первом проходе и перестановки на втором проходе, и т. д.

Рис. 5.17. Процесс сортировки массива

Рис. 5.18. Диалоговое окно программы Сортировка методом обмена

На рис. 5.18 приведено диалоговое окно программы сортировки массива методом обмена.

Процедура сортировки, текст которой приведен в листинге 5.10, запускается нажатием кнопки Сортировка (Button1). Значения элементов массива вводятся из ячеек компонента stringGrid1. Во время сортировки, после выполнения очередного цикла обменов элементов массива, программа выводит массив в поле метки Label2.

Листинг 5.10. Сортировка массива методом обмена

procedure TForm1.Button1Click(Sender: TObject);

const

SIZE=5;

var

a:array[1..SIZE] of integer;

k:integer; // текущий элемент массива

i:integer; // индекс для ввода и вывода массива

changed:boolean; // TRUE, если в текущем цикле были обмены

buf:integer; // буфер для обмена элементами массива

begin

// ввод массива

for i:=1 to SIZE do

a[i] := StrToInt(StringGrid1.Cells[i-1, 0] );

label2.caption:='';

// сортировка массива repeat

Changed:=FALSE; // пусть в текущем цикле нет обменов

for k:=l to SIZE-1 do

if a[k] > a[k+l] then

begin // обменяем k-й и k+1-й элементы

buf := a[k]; a[k] := a[k+l]; a[k+l] := buf;

changed := TRUE;

end;

// вывод массива

for i:=l to SIZE do

Label2.caption:=label2.caption+' '+IntTostr(a[i]);

Label2.caption:=label2.caption+#13;

until not changed; // если не было обменов, значит

// массив отсортирован

Label2.caption:=label2.caption

+#13+'Maccив отсортирован.';

end;

Следует отметить, что максимальное необходимое количество циклов проверки соседних элементов массива равно количеству элементов массива минус один. Вместе с тем возможно, что массив реально будет упорядочен за меньшее число циклов. Например, последовательность чисел 5 1 2 3 4, если ее рассматривать как представление массива, будет упорядочена за один цикл, и выполнение оставшихся трех циклов не будет иметь смысла.

Поэтому в программу введена логическая переменная changed, которой перед выполнением очередного цикла присваивается значение FALSE. Процесс сортировки (цикл repeat) завершается, если после выполнения очередного цикла проверки соседних элементов массива (цикл for) ни один элемент массива не был обменен с соседним, и, следовательно, массив уже упорядочен.

Рис. 5.19. Пример работы программы сортировки массива методом обмена

На рис. 5.19 приведено диалоговое окно программы сортировки массива методом обмена после завершения процесса сортировки.