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

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

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

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

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

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

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

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

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

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

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

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