Лекция 9. Методы сортировки и поиска информации

Методы сортировки и поиска информации

1. Сортировака

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

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

Сортировка методом прямого включения

Сортировка методом слияний

Обменная сортировака с разделением (сортировка Хоара)

2. Алгоритмы поиска информации

2.1. Линейный поиск

2.2. Линейный поиск с использованием барьера

2.3. Бинарный поиск

3. Поиск подстроки в строке

3.1. Прямой поиск

3.2. Алгоритм Р. Бойера и Дж. Мура

4. Пример

Для решения многих задач удобно сначала упорядочить данные по определенному признаку. Процесс упорядочивания заданного множества объектов по заданному признаку называется сортировкой.

Данные, например, элементы массива, можно отсортировать:

· по возрастанию – каждый следующий элемент больше предыдущего:

a[1] < a[2] <... < a[n];

· по неубыванию – каждый следующий элемент не меньше предыдущего:

a[1] ≤ a[2] ≤... ≤ a[n];

· по убыванию – каждый следующий элемент меньше предыдущего:

a[1] > a[2] >... >a[n];

· по невозрастанию – каждый следующий элемент не больше предыдущего: a[1] ≥ a[2] ≥... ≥ a[n].

Простейшими примерами могут служить следующие задачи.

Сортировка