Swap алгоритм XOR предоставляет средства для замены значений в двух целочисленных переменных без использования третьих, временной переменной. Этот алгоритм интересно узнать, хотя его использование не является необходимым в языках высокого уровня.

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

При составлении псевдокода использовались следующие соглашения.

Инварианты цикла и корректность сортировки вставкой

На рис. продемонстрировано, как этот алгоритм работает для массива
А = (5,2,4,6,1,3). Элементы массива обозначены квадратиками, над
которыми находятся индексы, а внутри — значения соответствующих элементов. Части
а-д этого рисунка соответствуют итерациям цикла for в строках 1-8 псевдокода.
В каждой итерации черный квадратик содержит значение ключа, которое
сравнивается со значениями серых квадратиков, расположенных слева от него (строка
псевдокода 5). Серыми стрелками указаны те значения массива, которые
сдвигаются на одну позицию вправо (строка 6), а черной стрелкой — перемещение
ключа (строка 8). В части е показано конечное состояние сортируемого массива.

Наш первый алгоритм, алгоритм сортировки методом вставок, предназначен
для решения задачи сортировки (sorting problem), сформулированной в первой статье.

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

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

Что такое алгоритмы? Стоит ли тратить время на их изучение? Какова роль
алгоритмов и как они соотносятся с другими компьютерными технологиями? Эта
статья дает ответы на поставленные вопросы.