Алгоритмы сортировки и поиска

Алгоритмы сортировки и поиска

Последовательный поиск

Индексно-последовательный поиск

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


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

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

Сортировка прямым обменом (метод "пузырька")

Шейкер-сортировка

Сортировка включениями с убывающими приращениями (сортировка Шелла)

Сортировка с помощью дерева

Пирамидальная сортировка

Быстрая сортировка

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


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

Все алгоритмы поиска делятся на

  • поиск в неупорядоченном множестве данных;
  • поиск в упорядоченном множестве данных.

Упорядоченность – наличие отсортированного ключевого поля.

Сортировка - упорядочение (перестановка) элементов в подмножестве данных по какому-либо критерию. Чаще всего в качестве критерия используется некоторое числовое поле, называемое ключевым. Упорядочение элементов по ключевому полю предполагает, что ключевое поле каждого следующего элемента не больше предыдущего (сортировка по убыванию).  Если ключевое поле каждого последующего элемента не меньше предыдущего, то говорят о сортировке по возрастанию.

Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве при обработке данных.

Все алгоритмы сортировки делятся на

  • алгоритмы внутренней сортировки (сортировка массивов);
  • алгоритмы внешней сортировки (сортировка файлов).

 

Сортировка массивов

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

Методы сортировки массивов можно разбить на три класса:

  • сортировка включениями;
  • сортировка выбором;
  • сортировка обменом.

 

Сортировка файлов

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

Прокрутить вверх