Книга является наиболее полным руководством по разработке эффективных ал

ЧАСТЬ I 
Практическая
разработка алгоритмов 

---

---

ГЛАВА 1 
Введение
в разработку алгоритмов 
Что такое алгоритм? Это процедура выполнения определенной задачи. Алгоритм явля-
ется основополагающей идеей любой компьютерной программы. 
Чтобы представлять интерес, алгоритм должен решать общую, корректно поставлен-
ную 
задачу
.
Определение задачи, решаемой с помощью алгоритма, дается описанием 
всего множества 
экземпляров
, которые должен обработать алгоритм, и выхода, т. е. 
результата, получаемого после обработки одного из этих экземпляров. Описание одно-
го из экземпляров задачи может заметно отличаться от формулировки общей задачи. 
Например, постановка 
задача сортировки 
делается таким образом: 
ЗАДАЧА.
Сортировка. 
Вход.
Последовательность из 
n
элементов: 
a
1
, ..., 
a
n
. 
Выход.
Перестановка элементов входной последовательности таким образом, что для 
ее членов справедливо соотношение 
a
'
1
≤
a
'
2
≤ ... ≤
a
'
n
–1
≤
a
'
n
. 
Экземпляром
задачи сортировки может быть массив имен, например {Mike, Bob, Sally, 
Jill, Jan}, или набор чисел, например {154, 245, 568, 324, 654, 324}. Первым шагом к 
решению — определить общую задачу. 
Алгоритм
— это процедура, которая принимает любой из возможных входных экземп-
ляров и преобразует его в соответствии с требованиями, указанными в условии задачи. 
Для решения задачи сортировки существует много разных алгоритмов. В качестве 
примера одного из таких алгоритмов можно привести метод 
сортировки вставками
. 
Сортировка этим методом заключается во вставке в требуемом порядке элементов из 
неотсортированной части списка в отсортированную часть, первоначально содержа-
щую один элемент. Реализация этого алгоритма на языке С представлена в листин-
ге 1.1. 
Листинг 1.1. Реализация алгоритма сортировки вставками 
insertion_sort(item s[], int n) 
{ 
int i,j; /* Счетчики */ 
for (i=1; ij=i; 
while ((j>0) && (s[j] < s[j-1])) { 
swap(&s[j],&s[j-l]); 
j = j-1; 
} 
} 
} 

---

22