Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 3.9. Быстрая сортировка. Нерекурсивный вариант 
void QuickStack()
{ 
int left = 0; int right = arr.Length - 1; 
MyStack stack = new MyStack(); 
TInf LRRange = new TInf(left, right); 
stack.PushStack(LRRange); 
do { 
LRRange = stack.PopStack(); 
left = LRRange.l; right = LRRange.r; 
13 / 23

---

60 
do { 
int i = left; int j = right;
int x = arr[(left+right)/2]; 
do { 
while (arr[i] < x) i++; 
while (arr[j] > x) j--; 
if (i <= j) { 
int tmp = arr[i]; arr[i] = arr[j];
arr[j] = tmp; 
i++; j--; 
} 
} 
while (i<=j); 
if (j - left < right - i) { 
if (i < right) { 
LRRange.l = i; LRRange.r = right; 
stack.PushStack(LRRange); 
} 
right = j; 
} 
else { 
if (left < j) { 
LRRange.l = left; LRRange.r = j; 
stack.PushStack(LRRange); 
} 
left = i; 
} 
} 
while (left < right); 
14 / 23

---

61 
} 
while (!stack.StackIsEmpty()); 
} 
Алгоритм быстрой сортировки следует применять для больших (N>15) 
массивов, так как для массивов меньшего размера он становится неэффек-
тивным. Неэффективен этот алгоритм и на частично упорядоченных масси-
вах. Поэтому рекомендуется прерывать алгоритм быстрой сортировки, когда 
размер обрабатываемого подмассива достигнет порогового значения, и про-
должить сортировку каким-либо другим методом, например, вставками, бо-
лее эффективным для частично упорядоченного массива.
3.4. А
ЛГОРИТМЫ С ВОЗВРАТОМ
 
Поиском с возвратом или бэктрекингом (от англ. backtrack – отходить, 
отступать) называется метод решения задач, сводящихся к перебору элемен-
тов некоторого множества. При этом элементы множества не являются изна-
чально заданными, но конструируются в процессе решения. Классическими 
примерами таких задач являются задачи поиска пути в лабиринте, задача 
коммивояжера, шахматные задачи. Целью перебора может быть нахождение 
элемента множества, обладающего определенными свойствами (пути, веду-
щего к выходу из лабиринта, или последовательности ходов, обеспечиваю-
щих выигрыш в некоторой шахматной позиции). Но может стоять задача пе-
ребора всех возможных элементов множества, например, всех путей между 
двумя вершинами графа. Подобные задачи особенно часто встречаются в 
области искусственного интеллекта. 
Отличительной особенностью алгоритмов, реализующих метод поиска 
с возвратом, является наличие точек множественного ветвления, в которых 
вместо выбора единственного из вариантов продолжения вычислений иссле-
дуются все возможные варианты. Если тот или иной вариант не приводит к 
желаемому результату, то происходит возврат в ближайшую точку ветвления 
и выбирается один из оставшихся вариантов. Тем самым нужное решение 
строится не по фиксированным правилам, а методом проб и ошибок, т. е. 
перебором всех возможных вариантов с отбрасыванием непригодных. Отбра-
сывание непригодных можно производить, используя эвристические сообра-
жения, и тем самым сводить количество вычислений к разумным пределам.
Алгоритм решения задачи методом бэктрекинга разделяется на отдель-
ные этапы, которые наиболее естественно описываются с помощью рекур-
сии. Каждый из этапов завершается одной из трех возможных ситуаций: 
− решение найдено; 
− достигнута новая точка множественного ветвления с неиспробо-
ванными вариантами продолжения; 
15 / 23

---

62 
− достигнута новая точка множественного ветвления, но все вари-
анты продолжения испробованы (тупиковая ситуация). 
В первом случае алгоритм можно считать завершенным, если нужно 
было найти едиственное решение. Во втором случае алгоритм должен вы-
брать один из возможных путей для дальнейшего поиска решений. Третий 
случай – это необходимость вернуться назад к ближайшей точке ветвления 
(и соответствующему этапу), для которой остались неисследованные пути, и 
выбрать новую альтернативу. Если такая точка ветвления не будет обнару-
жена, то решение завершается.
Схема алгоритма с возвратом представлена в листинге 3.10.