6. Задача поиска элементов с заданным ключом

Пусть имеется массив A = (a₁, a₂, … a_n) и задан ключ поиска X. Необходимо найти элемент (элементы) массива с ключом X, или определить, что элемента с заданным ключом в массиве нет. Если массив не упорядочен, то единственный путь поиска – просмотр всех элементов массива (линейный поиск) до тех пор, пока не будет найден этот элемент, или просмотрен весь массив. Трудоёмкость поиска в этом случае равна O(n), n→ ∞. Более эффективные алгоритмы поиска можно построить, если предполагать, что массив отсортирован, т.е. a₁≤ a₂ ≤ a₃ ≤ … ≤ a_n. Трудоемкость метода поиска будем оценивать по количеству сравнений, требуемых для поиска нужного элемента, при этом нас интересует только асимптотическая оценка трудоемкости.

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

1. Перечислите основные типы данных

2. Сформулируйте задачу сортировки массивов.

3. Как измеряется трудоемкость сортировки массивов?

4. Сформулируйте задачу сортировки последовательностей

5. Сформулируйте задачу поиска заданного элемента в массиве

6. Назовите предельную сложность для задачи сортировки массивов.

2. Методы сортировки с квадратичной трудоемкостью

   1. Метод прямого выбора

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

Пример. Упорядочим слово методом прямого выбора.

Условные обозначения

Х сравнение элемента Х с текущим максимальным элементом

текущий максимальный элемент

Перестановка элементов

•			•
К	У	Р	А	П	О	В	А
	•	•	•			•	•
А	У	Р	К	П	О	В	А
		•	•			•
А	А	Р	К	П	О	В	У
			•
А	А	В	К	П	О	Р	У
				•	•
А	А	В	К	П	О	Р	У
					•
А	А	В	К	О	П	Р	У
						•
А	А	В	К	О	П	Р	У
А	А	В	К	О	П	Р	У

Рисунок 2 Метод прямого выбора