Организация поиска и сортировки в массивах

Лабораторная  работа № 6.

Тема: Организация поиска и сортировки в массивах.

Цель  работы:

1. Закрепить знания и навыки по работе с массивами.
2. Познакомиться с понятием сортировка массива, изучить различные алгоритмы сортировки ( сортировка методом прямого выбора и методом обмена).
3. Научиться находить элементы массива с заданными свойствами с помощью метода перебора.
4. Изучить и реализовать в виде программы алгоритм бинарного поиска. ( метод деления пополам, двоичного поиска ).

Программное обеспечение: Pascal (TP или BP),  или ABCPascal, или FreePascal.

Аппаратное  обеспечение: ЭВМ типа IBM.

Порядок выполнения работы

1. Записать тему и цель лабораторной работы.
2. Ознакомиться с краткими теоретическими сведениями по теме лабораторной работы.
3. Ответить на контрольные вопросы (ответы на контрольные вопросы оформить в отчет).
4. Выполнить практическую часть работы.

4.1Сортировка

Познакомиться с алгоритмами сортировки « метод прямого выбора» и «метод пузырька».

Реализовать их на компьютере для своего варианта ( индивидуальные задания).

4.2 Поиск

Познакомиться с алгоритмом бинарного поиска и алгоритмом поиска методом перебора элементов.

Реализовать его  на компьютере и произвести бинарный поиск для массива, состоящего из n+50 (n-ваш номер варианта) элементов и поиск методом перебора для этого же массива.  Организовать поиск числа n в массиве.

5. Составить отчет. Во всех программах использовать краткие комментарии. (блок-схемы разрабатывать не надо). 

 

6. Защитить работу и сдать ее преподавателю. 

 

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

1. Опишите идею сортировки по возрастанию методом прямого выбора на примере сортировки следующего массива:

i	1	2	3	4	5	6	7
a [i]	n	10	-9	N+8	-90-n	0	-56

2. Опишите идею сортировки по убыванию  методом обмена на примере сортировки следующего массива:

i	1	2	3	4	5	6	7	8
b [i]	78	-10+n	-9	N+8	-90-n	33	400	n

 

3. Опишите идею поиска методом перебора элемента n на примере следующего массива:

i	1	2	3	4	5	6
c [i]	0	25	90	n	-n	-8

 

4. Опишите идею бинарного поиска элемента n на примере следующего массива:

 

i	1	2	3	4	5	6	7	8	9	10
d[i]	n	55	33	n-4	-90-n	0	-56	10	-9	N+8

 

 

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ  СВЕДЕНИЯ

СОРТИРОВКА МАССИВА

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

Примером задачи сортировки может служить следующая: в массиве из N различных чисел необходимо осуществить их перестановку так, чтобы после нее в массиве первым элементом было самое большое число. Каждое следующее должно быть меньше - предыдущего, а последнее — самое маленькое из чисел данного массива. Такой порядок расположения чисел называют убывающим.

Если в массиве есть равные числа, то задачу можно переформулировать  следующим образом: в массиве  из N чисел осуществить их перестановку так, чтобы после перестановки в массиве первым элементом было самое большое число. Каждое следующее должно быть не больше предыдущего, а последнее — самое маленькое из чисел данного массива. Такой порядок расположения чисел называют невозрастающим.

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

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

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

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

Ниже рассматривается  метод сортировки линейного массива по убыванию (невозрастанию). Сортировка по возрастанию (неубыванию) производится аналогично.

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

Давайте представим, что перед нами поставлена задача расставить N чисел по убыванию. Как бы мы ее решали?

Наверное, пришлось бы сначала  найти максимальное из всех чисел  и поменять местами с первым числом. Затем из еще неотсортированных  элементов надо было бы опять выбрать  максимальный элемент и поменять местами с первым элементом из еще не отсортированной части.

Примененный нами метод и  называется сортировкой выбором.

Формально его можно описать  следующим образом.

На  i - м шаге ( i = 1, ..., N — i ):

выбираем из элементов  с индексами от i до N максимальный элемент;

меняем местами найденный максимальный и элемент А [i], на i-м месте оказывается максимальный элемент из еще неотсортированной части массива.

После выполнения N—1-го шага в позиции A [N] будет находиться самый маленький элемент массива.

Название метода, «сортировка выбором» определяется тем, что на каждом шаге мы находим (выбираем) максимальный элемент из еще неотсортированной части массива.

Запишем алгоритм сортировки выбором:

нц   для i от 1 до N — 1 

K : = i 

max : = A [ i ]

нц для j от i + 1 до N

если A [ i ] > max

то     max : = A [ j ]

K : = j

все

кц

A [ K ] : = A [ i ]

A [ i ] :  = max

кц

Внутренний  цикл ДЛЯ j ОТ i + 1 ДО N является ничем иным, как алгоритмом поиска максимального алгоритма среди элементов с номерами от i+1 до N. Рассмотрим работу данного метода на массиве   А = {0, 1, 9, 2, 4, 3, 6, 5}.

Максимальный элемент  будем подчеркивать.

1) 0, 1, 9, 2, 4, 3, 6, 5

2) 9, 1, 0, 2, 4, 3, 6, 5

3) 9, 6, 0, 2, 4, 3, 1, 5

4) 9, 6, 5, 2, 4, 3, 1, 0

5) 9, 6, 5, 4, 2, 3, 1, 0

6) 9, 6, 5, 4, 3, 2, 1, 0

7) 9, 6, 5, 4, 3, 2, 1, 0

8) 9, 6, 5, 4, 3, 2, 1, 0

Подсчитаем  количество сравнений, которые пришлось сделать для упорядочения массива.

На первом шаге для нахождения максимального элемента необходимо (N—1) сравнение, на втором (N—2), на третьем (N—3), ..., на последнем шаге —одно сравнение. Найдем сумму:

N – 1 + N –  2 + N – 3 + . . . + 1 = N ( N – 1 ) / 2 = ( N² — N ) / 2 .

Примечание. Сумму можно посчитать исходя из следующих соображений. Количество слагаемых равно (N—1), сумма первого и последнего, второго и предпоследнего и т. д. равна N. Произведение N (N—1) даст удвоенную сумму, так как каждое слагаемое будет входить в эту сумму дважды, поэтому его нужно разделить на 2.

Количество  перестановок элементов равно (N—1). Это количество определяется внешним циклом ДЛЯ.

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

 

Рассмотрим  еще один метод сортировки, который  формально можно описать так:

На i-м шаге (i = 1, ..., N — 1 ) выполняем:

1. Сравниваем  первые два элемента. Если первый  меньше второго, то меняем их  местами.

2. Сравниваем  второй и третий, третий и четвертый, .... N—i и N — i + 1, при необходимости меняя элементы местами. Самый маленький окажется на i-м месте в массиве.

После первого  шага самый маленький элемент  массива помещается на N-e место. Массив будет отсортирован после просмотра, в котором участвуют только первый и второй элементы.

Название метода «сортировка обменом» определяется тем, что алгоритм основывается на обмене местами двух элементов массива.

Описанный метод  сортировок обменом называют также пузырьковой сортировкой.

Алгоритм  метода сортировки обменом:

нц для i от 1 до N — 1

нц  для j от 1 до N — i

если A [ j ] < A [ j + 1 ]

то  x : = A [ j ]

A [ j ] : = A [ j + l ]

A [ j + l ] : = x 

все

кц 

кц

Рассмотрим его на примере  того же массива A = {0, 1, 9, 2, 4, 3, 6, 5}.

1) 1, 9, 2, 4, 3, 6, 5, 0

2) 9, 2, 4, 3, 6, 5, 1, 0

3) 9, 4, 3, 6, 5, 2, 1, 0

4) 9, 4, 6, 5, 3, 2, 1. 0

5) 9, 6, 5, 4, 3, 2, 1, 0

6) 9, 6, 5, 4, 3, 2, 1, 0

7) 9, 6, 5, 4, 3, 2, 1, 0

Число сравнений в данном алгоритме равно также (N  ²  - N ) / 2.

При каждом сравнении возможна перестановка двух элементов в массиве. Поэтому количество перестановок (в  худшем случае) будет равно количеству сравнений, т. е. (N²—N)/2.

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

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

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

Алгоритм  простого перебора

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

 

Цикл завершается, если в  массиве обнаружен элемент, равный образцу (в этом случае значение переменной found равно true), или если проверены  все элементы массива. По завершении цикла по значению переменной found можно определить, успешен поиск или нет.

Быстрый последовательный доступ ( бинарный поиск ).