Задание для самостоятельной работы

1. Введите в поле Memo список студентов, состоящий из фамилии, имени и отчества отсортируйте список в алфавитном порядке.

2. Дан массив 12, 3, 5, 7, 9, 10. За один просмотр методом пузырька он становится отсортированным, остальные просмотры ничего не дают. Напишите приложение, исключающее лишние просмотры.

3. Массив 12, 3, 5, 7, 9, 10 сортируется методом пузырька за один просмотр, а массив 5, 7, 9, 10, 12, 3 – за пять просмотров (N-1). Явное неравноправие. Устранить его можно путем смены направлений просмотров, то есть первоначально в направлении → получаем 5, 7, 9, 10, 3, 12, а затем в направлении ←результат – 3, 5, 7, 9, 10, 12. Написать приложение, которое чередует направления, таким образом, пока массив не будет отсортирован.

4. Объедините задания из пунктов 2 и 3 в единое целое. Этот метод называется «шейкерной сортировкой». Реализуйте его.

Контрольные вопросы

1. Опишите алгоритм сортировки обменом

2. Опишите алгоритм сортировки простым выбором

3. Опишите алгоритм сортировки простыми вставками

Лабораторная работа № 11. Поиск данных в массиве

ЦЕЛЬ РАБОТЫ: Изучение методов поиска данных в отсортированном и не отсортированном массивах. Получение навыков использования методов поиска при создании простых приложений.

ПОДГОТОВКА К РАБОТЕ: Изучить алгоритмы работы методов поиска данных в массивах.

ЗАДАНИЕ. Создайте приложение, выполняющее последовательный и бинарный поиск данных в массиве (см. рисунок 11.1).

Последовательность действий по созданию приложения:

1. Создайте новое приложение и перенесите на него компоненты, из таблицы 11.1.

Таблица 11.1 Компоненты приложения

Компонент	Описание
1	2
Label 1	Метка «Количество элементов»
Label 2	Метка «Найти элемент»
Label 3	Метка «Элемент найден и находится в …. Позиции». В начальный момент свойство Caption=’’
Edit1	Окно, в которое вводится количество элементов в массиве

Продолжение таблицы 11.1

1	2
Edit2	Окно, в которое вводится значение элемента, который надо найти
Memo1	В данном поле содержится массив, в котором надо найти элемент
Button1	Командная кнопка «Очистить массив»
Button2	Командная кнопка «Заполнить массив»
Button3	Командная кнопка «Последовательный поиск»
Button4	Командная кнопка «Бинарный поиск»

2. В области глобальных переменных объявите массив:

var

Form1: TForm1;

a: Array[1..100] of Integer;

implementation

…………………

3. Для события OnClick кнопки «Очистить массив» напишите следующий программный код:

procedure TForm1.Button1Click(Sender: TObject);

begin

Memo1.Clear; Edit1.Text:='';

end;

4. Для события OnClick кнопки «Заполнить массив» напишите следующий программный код:

procedure TForm1.Button2Click(Sender: TObject);

var i,n:Integer;

begin

memo1.Clear; n:=StrToInt(Edit1.Text); Randomize;

For i:=1 to n do

begin

a[i]:=-50+Random(100); Memo1.Lines.Add(IntToStr(a[i]));

end;

end;

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

Этот метод должен использоваться для неотсортированных данных,  но он также может использоваться для отсортированных данных.  Программный код для последовательного поиска (событие OnClick кнопки «Последовательный поиск») имеет вид:

procedure TForm1.Button3Click(Sender: TObject);

Var i,key,n:Integer;

begin

key:=StrToInt(Edit2.Text); n:=StrToInt(Edit1.Text);

i:=1;

While (key<>a[i]) and (i<=n) do i:=i+1;

If i<=n then Label3.Caption:=Элемент найден и находится в ' + IntToStr(i)+' позиции'

else Label3.Caption:='Элемент не найден';

end;

6. Напишите программный код для бинарного (двоичного) поиска. Бинарный поиск производится только в отсортированном массиве. При таком поиске сначала производится проверка среднего элемента. Если его значение больше значения требуемого элемента,  то делается проверка для среднего элемента из первой половины.  В противном случае делается проверка среднего элемента из второй половины.  Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки. Например, для поиска числа 4 в массиве 1, 2, 3, 4, 5,   6,   7,  8,   9 указанным методом сначала делается проверка среднего элемента, которым является число 5.  Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел      1, 2, 3, 4, 5.  Здесь средним элементом является 3. Это значение меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел     4, 5. На следующем шаге нужный элемент будет найден. При бинарном число сравнений в худшем случае равно log n.  Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице. Программный код для бинарного поиска (событие OnClick кнопки «Бинарный поиск») имеет вид:

procedure TForm1.Button4Click(Sender: TObject);

Var Low,High,mid,key,n,i,j,k:Integer;

Found:Boolean;

begin

Memo1.Clear;

// Сортировка массива методом пузырька

n:=StrToInt(Edit1.Text);

For j:=1 to n-1 do {Цикл по номеру просмотра}

For i:=1 to n-j do

If a[i]> a[i+1] then {Перестановка элементов}

Begin

k:=a[i];

a[i]:=a[i+1];

a[i+1]:=k;

end;

For i:=1 to n do memo1.Lines.Add(IntToStr(a[i]));

// Бинарный поиск

key:=StrToInt(Edit2.Text);

Low:=1;

High:=n;

Found:=False;

While (Low<=High) and (not found)do

begin

mid:=(low+high) div 2;

If key<a[mid] then High:=mid-1

else If key>a[mid] then low:=mid+1

else found:=True;

end;

If Found then Label3.Caption:=Элемент найден и находится в '+ IntToStr(mid)+' позиции'

else Label3.Caption:='Элемент не найден';

end;

7. Откомпилируйте приложение и проверьте его работу.