Организация циклов: с параметром, с предусловием и постусловием; обработка векторов и матриц, основные алгоритмы: сортировка, поиск

Циклы с параметром

Операторы цикла с параметром имеют переменную, называемую параметром (счетчиком) цикла, которая используется в качестве счетчика (или индекса) числа повторений цикла. В таком заголовке задаются начальное и конечное значения параметра цикла и приращение — разность между двумя
последовательными значениями параметра. При определении оператора цикла с параметром необходимо ответить на следующие вопросы:

1. 1. Какой тип и какую область видимости должен иметь параметр цикла?
2. 2. Чему равно значение параметра цикла при выходе из цикла?
3. 3. Следует ли разрешать изменять параметр цикла, его начальное, конечное значения и приращение в теле цикла, и если да, то как влияет такое изменение на управление циклом?
4. 4. Начальное и конечное значения параметра цикла и приращение должны вычисляться только один раз при входе в цикл, или эти вычисления следует делать на каждой итерации?

Цикл с предусловием

Типичный цикл с предусловием имеет следующий синтаксис:

while логическое_выражение do тело_цикла

В цикле с предусловием тело цикла выполняется до тех пор, пока результат логического выражения является истинным. 

Цикл с постусловием

Цикл с постусловием может быть представлен в виде:

do тело_цикла while логическое_выражение

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

В языке Pascal цикл с постусловием repeat . . . u n til отличается от операторов do . . . while тем, что он имеет противоположную логику управляющего логического выражения: тело цикла выполняется до тех пор, пока результат логического выражения имеет значение ложь. 

Обработка векторов и матриц

Матрица (matrix) представляет собой прямоугольный массив чисел. Используются заглавные буквы для обозначения матриц, а их элементы обозначаются соответствующими строчными буквами с нижними индексами. Множество всех матриц размером m × n, элементами которых являются действительные числа, обозначается как R_m×n. В общем случае множество матриц размером m × n, элементы которых принадлежат множеству S, обозначается как S_m×n.

Транспонированная (transpose) матрица A^T получается из матрицы A путем обмена местами ее строк и столбцов.

Нулевая матрица (zero matrix) — это матрица, все элементы которой равны 0. Такая матрица часто записывается просто как 0, поскольку неоднозначность между числом 0 и нулевой матрицей легко разрешается при помощи контекста. Если размер нулевой матрицы не указан, то он также выводится из контекста.

Часто приходится иметь дело с квадратными (square) матрицами размером n × n. 

Элементами матриц и векторов служат элементы некоторой числовой системы, такие как действительные числа, комплексные числа или, например, целые числа по модулю простого числа. Числовая система определяет, каким образом должны складываться и перемножаться числа. Эти определения можно распространить и на матрицы.

Матрицы обладают многими (но не всеми) алгебраическими свойствами, присущими обычным числам. Единичная матрица является нейтральным элементом

Вектор (vector) представляет собой одномерный массив чисел. Для обозначения векторов используют строчные буквы и обозначают i-й элемент вектора x как x_i. Стандартной формой вектора будем считать вектор-столбец (column vector), эквивалентный матрице n × 1. Соответствующий вектор-строка (row vector) получается путем транспонирования вектора-столбца.

Единичным вектором (unit vector) e_i называется вектор, i-й элемент которого равен 1, а все остальные элементы равны 0. Обычно размер единичного вектора ясен из контекста.

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

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

• А. Сортировка методом вставок. Элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. (Именно таким способом игроки в бридж упорядочивают свои карты, беря по одной.)
• В. Обменная сортировка. Если два элемента расположены не по порядку, то они меняются местами. Этот процесс повторяется до тех пор, пока элементы не будут упорядочены.
• С. Сортировка посредством выбора. Сначала выделяется наименьший (или, быть может, наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся и т. д.
• D. Сортировка путем подсчета. Каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется после подсчета числа меньших ключей.
• Е. Без сравнений.

Пузырьковый метод — популярный алгоритм сортировки. В его основе лежит многократная перестановка соседних элементов: алгоритм проходит по массиву, сравнивает последовательные пары элементов и меняет их местами, если они расположены в неправильном порядке.

Сортировка вставкой (insertion sort). Этот алгоритм эффективно работает при сортировке небольшого количества элементов. Сортировка вставкой напоминает способ, к которому прибегают игроки для сортировки имеющихся на руках карт: элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

Карманная, или блочная сортировка. Алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.

Идея, лежащая в основе карманной сортировки, заключается в том, чтобы разбить интервал [0, 1) на n одинаковых интервалов, или карманов (buckets), а затем распределить по этим карманам n входных величин. Поскольку входные числа равномерно распределены в интервале [0, 1), мы предполагаем, что в каждый из карманов попадет не много элементов. Чтобы получить выходную последовательность, нужно просто выполнить сортировку чисел в каждом кармане, а затем последовательно перечислить элементы каждого кармана.

Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой. Относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).

Сортировка выбором. Делит входной массив на упорядоченную и неупорядоченную части. Затем последовательно переносит в первую часть наименьшие элементы из второй. Сначала определяется наименьший элемент массива A, который ставится на место элемента A [1], затем производится поиск второго наименьшего элемента массива A, который ставится на место элемента A [2]. Этот процесс продолжается для первых n − 1 элементов массива A.

Сортировка слиянием. Рекурсивно сортирует половины массива, а затем комбинирует их в один.

Алгоритм сортировки слиянием (merge sort) в большой степени соответствует парадигме метода разбиения. На интуитивном уровне его работу можно описать таким образом.

• Разделение: сортируемая последовательность, состоящая из n элементов, разбивается на две меньшие последовательности, каждая из которых содержит n/2 элементов.
• Покорение: сортировка обеих вспомогательных последовательностей методом слияния.
• Комбинирование: слияние двух отсортированных последовательностей для получения окончательного результата.

Рекурсия достигает своего нижнего предела, когда длина сортируемой последовательности становится равной 1. В этом случае вся работа уже сделана, поскольку любую такую последовательность можно считать упорядоченной.

Быстрая сортировка (сортировка Хоара). Выбирается опорный элемент p. Все ключи, меньшие, либо равные p перемещаются, влево от него, а все ключи, большие, либо равные p вправо. Далее алгоритм рекурсивно применяется к каждой из частей.

Быстрая сортировка, подобно сортировке слиянием, основана на парадигме “разделяй и властвуй”. Ниже описан процесс сортировки подмассива A [p..r], состоящий, как и все алгоритмы с использованием декомпозиции, из трех этапов.

• Разделение. Массив A [p..r] разбивается (путем переупорядочения его элементов) на два (возможно, пустых) подмассива A [p..q − 1] и A [q + 1..r]. Каждый элемент подмассива A [p..q − 1] не превышает элемент A[q], а каждый элемент подмассива A [q + 1..r] не меньше элемента A[q]. Индекс q вычисляется в ходе процедуры разбиения.
• Покорение. Подмассивы A [p..q − 1] и A [q + 1..r] сортируются путем рекурсивного вызова процедуры быстрой сортировки.
• Комбинирование. Поскольку подмассивы сортируются на месте, для их объединения не нужны никакие действия: весь массив A [p..r] оказывается отсортирован.

Пирамидальная сортировка (сортировка кучей).  На основе исходных данных строится двоичная куча, в которой последовательно собираются минимальные значения.

Пирамида (binary heap) – это структура данных, представляющая собой объект-массив, который можно рассматривать как почти полное бинарное дерево. Каждый узел этого дерева – соответствует определенному элементу массива. На всех уровнях, кроме, может быть, последнего, дерево полностью заполнено (заполненный уровень – это такой, который содержит максимально возможное количество узлов). Последний уровень заполняется слева направо до тех пор, пока в массиве не закончатся элементы. Представляющий пирамиду массив А является объектом с двумя атрибутами: length (А), т.е. количество элементов массива, и heap_size (А), т.е. количество элементов пирамиды, содержащихся в массиве А. Другими словами, несмотря на то, что в массиве А [1.. length (А]) все элементы могут быть корректными числами, ни один из элементов, следующих после элемента A [heap_size (А)], где heap_size
(A) ≤ length (А), не является элементом пирамиды. В корне дерева находится элемент А [1], а дальше оно строится по следующему принципу: если какому-то узлу соответствует индекс i, то индекс его родительского узла вычисляется с помощью описанной ниже процедуры Parent(i), индекс левого дочернего узла – с помощью процедуры Left(i), а индекс правого дочернего узла – с помощью процедуры Right(i):

Parent(i)
 return [i/2]
 Left(i)
 return 2i
 Right(i)
 return 2i + 1  

Сортировка подсчетом. Подсчитывается количество вхождений каждого целого числа из диапазона ключей в массив. Затем выводится значения всех ненулевых значений. Предполагается, что все n входных элементов – целые числа, принадлежащие интервалу от 0 до k, где k – некоторая целая константа. Основная идея сортировки подсчетом заключается в том, чтобы для каждого рассматриваемого элемента х определить количество элементов, которые меньше х. С помощью этой информации элемент х можно разместить на той позиции выходного массива, где он должен находиться. Исходный массив- A[1..n], результат – B[1..n], вспомогательный массив – С[0..k]. 

Поразрядная сортировка. Алгоритм сортировки, который выполняется за линейное время. Этот алгоритм можно описать следующим образом:

а) Последовательность сортируется по старшему значащему двоичному разряду так, чтобы все ключи, начинающиеся с 0, оказались перед всеми ключами, начинающимися с 1. Для этого необходимо найти крайний слева ключ /G, начинающийся с 1, и крайний справа ключ Kj, начинающийся с 0, после чего Ri и Rj поменяются местами, и процесс будет повторяться, пока не получится i > j.
б) Пусть Fo — множество элементов, начинающихся с 0, a Fi — множество всех остальных элементов. Будем применять к Fo поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество Fq полностью не рассортируется. Затем проделаем то же самое с Fi.

Топологическая сортировка. Это сортировка элементов, для которых определен частичный порядок, то есть отношение порядка задано для некоторых, но не для всех пар элементов. Топологическая сортировка (topological sort) ориентированного ациклического графа G = = (V,E) представляет собой такое линейное упорядочение всех его вершин, что если граф G содержит ребро (u, v), то u при таком упорядочении располагается до v (если граф не является ацикличным, такая сортировка невозможна). Топологическую сортировку графа можно рассматривать как такое упорядочение его вершин вдоль горизонтальной линии, что все ребра направлены слева направо. Таким образом, топологическая сортировка существенно отличается от обычных видов сортировки. 

Сортировка перемешиванием (шейкерная сортировка). Двунаправленный, оптимизированный вариант сортировки пузырьком, где последовательность записей просматривается попеременно в обоих направлениях.

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

"Гномья сортировка основана на технике, используемой обычным голландским садовым гномом. Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на текущий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил" (Дик Грун).

Сортировка с помощью двоичного дерева. Алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока.

Сортировка Timsort. Гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием.

• По специальному алгоритму входной массив разделяется на подмассивы.
• Каждый подмассив сортируется сортировкой вставками.
• Отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием.

Сортировка расчёской.  Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом, мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди. Сначала расстояние между элементами максимально, то есть равно размеру массива минус один. Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае сравниваются соседние элементы как и в сортировке пузырьком, но такая итерация одна.

Сортировка Шелла. Является модификацией алгоритма сортировки вставками, которая состоит в следующем: вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и тд, где h – положительная константа. Таким образом, формируется массив, в котором «h- серии» элементов, отстоящих друг от друга на h, сортируются отдельно. Процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h=1.

Плавная сортировка. Разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо. Куча состоит из последовательности куч, размеры которых равны одному из чисел Леонардо, а корни хранятся в порядке возрастания. Преимущества таких специальных куч перед двоичными состоят в том, что если последовательность отсортирована, её создание и разрушение займёт O(n) времени, что будет быстрее. Разбить входные данные на кучи просто: крайние слева узлы массива составят самую большую кучу, а оставшиеся будут разделены подобным образом.

• Массив любой длины может быть также разбит на части размера L(x).
• Не должно быть двух куч одинакового размера, потому что в этом случае последовательность превратится в строго убывающую по размерам.
• Не должно быть двух куч, размеры которых равны двум последовательным числам Леонардо, за исключением массива длины 2. 

Интроспективная сортировка. Использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Так как оба алгоритма используют сравнения, этот алгоритм также принадлежит классу сортировок на основе сравнений.

Придурковатая (блуждающая) сортировка. 

Bogosort
Сортировка перестановкой
Гравитационная сортировка
Сортировка им. Сталина

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

Последовательный поиск. Алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и, в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило, поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.

Бинарный (двоичный) поиск. Алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины.

Алгоритм Кнута-Морриса-Прата. Алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно. 

Алгоритм Бойера-Мура. Алгоритм общего назначения, предназначенный для поиска подстроки в строке. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск), шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускается как заведомо не дающая результата. 

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

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.

Алгоритм Рабина-Карпа. Алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте, используя хеширование.

Одно из простейших практических применений алгоритма Рабина — Карпа состоит в определении плагиата. Скажем, например, что студент пишет работу по Моби Дику. Коварный профессор находит различные исходные материалы по Моби Дику и автоматически извлекает список предложений в этих материалах. Затем алгоритм Рабина — Карпа может быстро найти в проверяемой статье примеры вхождения некоторых предложений из исходных материалов. Для устранения чувствительности алгоритма к небольшим различиям можно игнорировать детали, такие как регистр или пунктуация, при помощи их удаления. Поскольку количество строк, которые мы ищем, k, очень большое, обычные алгоритмы поиска одиночных строк становятся неэффективными.

Вместо того, чтобы использовать более умный пропуск, алгоритм Рабина — Карпа пытается ускорить проверку эквивалентности образца с подстроками в тексте, используя хеш-функцию. Хеш-функция — это функция, преобразующая каждую строку в числовое значение, называемое хеш-значением (хеш); например, мы можем иметь хеш от строки «hello» равным 5. Алгоритм использует тот факт, что если две строки одинаковы, то и их хеш-значения также одинаковы. Таким образом, всё, что нам нужно, это посчитать хеш-значение искомой подстроки и затем найти подстроку с таким же хеш-значением.

Однако существуют две проблемы, связанные с этим. Первая состоит в том, что, так как существует очень много различных строк, между двумя различными строками может произойти коллизия — совпадение их хешей. В таких случаях необходимо посимвольно проверять совпадение самих подстрок, что занимает достаточно много времени, если данные подстроки имеют большую длину (эту проверку делать не нужно, если приложение допускает ложные срабатывания). При использовании достаточно хороших хеш-функций коллизии случаются крайне редко, и в результате среднее время поиска оказывается невелико.

Наивный поиск. В наивном поиске левый конец образца P ставится вровень с левым концом текста Т и все символы P сравниваются с соответствующими символами Т слева направо, пока либо не встретится несовпадение, либо не исчерпается Р. В последнем случае констатируется, что найдено вхождение P в текст. При любом исходе P сдвигается на одну позицию вправо, и сравнения возобновляются, начиная с левого конца Р. Процесс продолжается, пока правый конец P не зайдет за правый конец Т. 

1. Опалева Э. А., Самойленко В. П. Языки программирования и методы трансляции. — СПб.: БХВ-Петербург, 2005. — 480 с.
2. Кормен Т. Х. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS / Томас Х. Кормен Т. Х., Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. — 2-е изд. — М.: «Вильямс», 2006. —  1296. с.
3. Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с.
4. Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона + CD / Пер. с англ. Ткачев Ф. В. - М.: ДМК Пресс, 2010. - 272 с.