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

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

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

Мы будем записывать алгоритмы с помощью псевдокода (pseudocode), который напомнит вам знакомые языки программирования (Си, Паскаль, Алгол). Разница в том, что иногда мы позволяем себе описать действия алгоритма «своими словами», если так получается яснее. Кроме того, мы опускаем технологические подробности (обработку ошибок, скажем), которые необходимы в реальной программе, но могут заслонить существо дела.

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

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

Запишем этот алгоритм в виде процедуры Insertion-Sort, параметром которой является массив А[1.. п] (последовательность длины п, подлежащая сортировке). Мы обозначаем число элементов в массиве А через length[A]. Последовательность сортируется «на месте» (in place), без дополнительной памяти (помимо массива мы используем лишь фиксированное число ячеек памяти). После выполнения процедуры Insertion-Sort массив А упорядочен по возрастанию.

Рис. 1.1 Сортировка карт вставками

Insertion-Sort (А)

1 for j <- 2 to length[A]

2 do key <3> добавить A[j] к отсортированной части A[l. .j - 1].

4г <- j - 1

5while i > 0 and А [г] > fcet/

6do A[i + A[i]

7г <- i - 1

8A[i + l]<r- key

Рис. 1.2 Работа процедуры INSERTION-SORT для входа А = (5,2,4,6,1,3). Позиция j показана кружком.

На рис. 1.2 показана работа алгоритма при А = (5,2,4,6,1,3). Индекс j указывает «очередную карту» (только что взятую со стола). Участок А[1. .j - 1] составляют уже отсортированные карты (левая рука), a A[j + 1. .га] - ещё не просмотренные. В цикле for индекс j пробегает массив слева направо. Мы берём элемент A[j]

(строка 2 алгоритма) и сдвигаем идущие перед ним и большие его по величине элементы (начиная с j - 1-го) вправо, освобождая место для взятого элемента, (строки 4-7). В строке 8 элемент A[j] помещается в освобождённое место.

Псевдокод

Вот основные соглашения, которые мы будем использовать:

1.Отступ от левого поля указывает на уровень вложенности. Например, тело цикла for (строка 1) состоит из строк 2-8, а тело цикла while (строка 5) содержит строки 6-7, но не 8. Это же правило применяется и для if-then-else. Это делает излишним специальные команды типа begin и end для начала и конца блока. (В реальных языках программирования такое соглашение применяется редко, поскольку затрудняет чтение программ, переходящих со страницы на страницу.)

2.Циклы while, for, repeat и условные конструкции if, then, else имеют тот же смысл, что в Паскале.

3.Символ > начинает комментарий (идущий до конца строки).

4.Одновременное присваивание i <- j <- е (переменные i и j получают значение е) заменяет два присваивания j <- е и г <- j (в этом порядке).

5.Переменные (в данном случае i,j,key) локальны внутри процедуры (если не оговорено противное).

6.Индекс массива пишется в квадратных скобках: A[i] есть г-ж элемент в массиве А. Знак «..» выделяет часть массива: А[1. .j] обозначает участок массива А, включающий А[1], А[2],..., A[j].

7.Часто используются объекты (objects), состоящие из нескольких полей (fields), или, как говорят, имеющие несколько атрибутов (attributes). Значение поля записывается как имя-Поля[имя-объекта]. Например, длина массива считается его атрибутом и обозначается length, так что длина массива А запишется как length[A]. Что обозначают квадратные скобки (элемент массива или поле объекта), будет ясно из контекста.

Переменная, обозначающая массив или объект, считается указателем на составляющие его данные. После присваивания у <- х для любого поля / выполнено f[y] = f[x]. Более того, если мы теперь выполним оператор f[x] <- 3, то будет не только f[x] = 3, но и f[y] = 3, поскольку после у <- х переменные хну указывают на один и тот же объект.

Указатель может иметь специальное значение NIL, не указывающее ни на один объект.

8.Параметры передаются по значению (by value): вызванная процедура получает собственную копию параметров; изменение параметра внутри процедуры снаружи невидимо. При передаче объек-