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

Одной из наиболее распространенных операций при работе с массивами является операция поиска элемента по значению. Для решения этой задачи существует несколько различных подходов:
поиск перебором – в том случае, когда имеется массив данных, заполненный в произвольном порядке, и больше нет ни какой дополнительной информации, единственное решение задачи поиска - полный перебор элементов массива до тех пор, пока не будет найден нужный элемент, либо пока массив не закончится. Очевидно, что в худшем случае (когда искомый элемент является последним) придется просмотреть все элементы массива, что будет очень затратно на больших объемах данных;
поиск с барьером – предыдущий вид поискка требует дополнительных операций – постоянного увеличения счетчика, в котором хранится текущий рассматриваемый индекс массива, а также проверка логического выражения достижения конца массива. От подобных операций можно избавиться путем изменения логического выражения. Для этого в массив добавляется еще один элемент – «барьер», который позволяет не выходить за границы массива. Таким образом, если по завершении алгоритма поиска найденный индекс является индексом барьера, искомый элемент будет отсутствовать;
бинарный поиск – для упрощения поиска в данном случае требуются дополнительные данные. Самый простой способ при этом – упорядочивание элементов массива. Бинарный поиск на каждой итерации сокращает размер просматриваемого массива в два раза. Первая операция сравнения выполняется для центрального элемента массива

. Если он больше искомого, дальнейший поиск будет вестись на левой половине массива, иначе – на правой. При этом в качестве элемента сравнения всегда выбирается центральный элемент из рассматриваемого участка.
Очевидно, что поиск элемента в заранее отсортированном массиве будет максимально быстрым. Для реализации сортировки также существует несколько алгоритмов, эффективность которых оценивается двумя критериями:
числом произведенных сравнений;
числом перестановок элементов.
Стоит отметить, что для перестановки элементов всегда треубется использование дополнительной переменной. При этом алгоритм перестановки состоит из следующих шагов:
сохранение значения первого элемента в промежуточной переменной;
запись значения второго элемента в первый элемент;
запись значение промежуточной переменной во второй элемент.
Алгоритмы сортировки бывают трех видов:
посредством включения (сортировка простым методом) – при использовании алгоритмов данной группы массив разбивается на две части – упорядоченую и неупорядоченную. На начальном этапе упорядоченная часть содержит только первый элемент массива. Далее, на каждом шаге из неотсортированной части выбирается один элемент и добавляется в отсортированную часть таким образом, чтобы не нарушать свойство упорядоченности. На рисунке 1 изображены две первых итерации данного алгоритма. Здесь упорядоченная и неупорядоченная части отделены вертикальной чертой