Алгоритмика: быстрая сортировка, стратегия «разделяй и властвуй», рекурсия

Glossary overview

Алгоритм быстрой сортировки использует стратегию «разделяй и властвуй».

Алгоритм не особенно полезен, если он способен решать задачу только одного типа, “разделяй и властвуй” помогает выработать новый подход к решению задач. Это всего лишь еще один инструмент в вашем арсенале. Столкнувшись с новой задачей, не впадайте в ступор. Вместо
этого спросите себя: «А нельзя ли решить эту задачу, применив стратегию “разделяй и властвуй”?

«Разделяй и властвуй»

Решение задачи методом «разделяй и властвуй ~ состоит из двух шагов:

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

Пример

Представьте, что вы фермер, владеющий земельным участком.

Вы хотите равномерно разделить землю на одинаковые квадратные участки. Участки должны быть настолько большими, насколько это возможно.

А теперь воспользуемся стратегией “разделяй и властвуй” для поиска решения этой задачи. Каков самый большой размер квадрата, который может использоваться?
Для начала нужно определить базовый случай. Самая простая ситуация – если длина одной стороны кратна длине другой стороны. До этого момента будем делить.

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

Теперь нужно вычислить рекурсивный случай. Здесь-то вам на помощь и приходит стратегия “разделяй и властвуй” . В соответствии с ней при каждом рекурсивном вызове задача должна сокращаться. Как сократить эту задачу? Для начала разметим самые большие участки, которые можно использовать.

В исходном наделе можно разместить два участка 640 х 640, и еще останется
место. Тут-то и наступает момент истины. Нераспределенный остаток – это
тоже надел земли, который нужно разделить. Так почему бы не применить
к нему тот же алгоритм?

Итак, мы начали с надела 1680 х 640, который необходимо разделить на участки. Но теперь разделить нужно меньший сегмент – 640 х 400. Если вы найдете самый большой участок, подходящий для этого размера, это будет самый большой участок, подходящий для всей фермы. Мы только что сократили задачу с размера 1680 х 640 до 640 х 400!

Применим тот же алгоритм снова. Если начать с участка 640 х 400, то размеры самого большого
квадрата, который можно создать, составляют 400 х 400 м. Остается меньший сегмент с

Отсекая поделенную часть, мы приходим к еще меньшему размеру сегмента, 240 Х 160 М.

После очередного отсечения получается еще меньший сегмент.

Эге, да мы пришли к базовому случаю: 160 кратно 80. Если разбить этот сегмент на квадраты, ничего лишнего не останется!

Итак, для исходного надела земли самый большой размер участка будет равен 80 х 80 м.

Вспомните, как работает стратегия ~разделяй и властвуй•:

Определите простейший случай как базовый.
Придумайте, как свести задачу к базовому случаю.

“Разделяй и властвуй” – не простой алгоритм, который можно применить для решения задачи. Скорее, это подход к решению задачи.

Пример с массивом чисел

Нужно просуммировать все числа и вернуть сумму. Сделать это в цикле совсем не сложно.

Но как сделать то же самое с использованием рекурсивной функции?

Шаr 1: определить базовый случай. Как выглядит самый простой массив, который вы можете получить? Подумайте, как должен выглядеть простейший случай, и продолжайте читать. Если у вас будет массив с 0 или 1 элементом, он суммируется достаточно просто.

Итак, с базовым случаем мы определились.

Шаr 2: каждый рекурсивный вызов должен приближать вас к пустому массиву. Как уменьшить размер задачи? Один из возможных способов:

В любом случае результат равен 12. Но во второй версии функции sum передается меньший массив. А это означает, что вы сократили размер своей задачи!
Функция sum может работать по следующей схеме:

А вот как это выглядит в действии.

Вспомните, что при рекурсии сохраняется состояние.

Идея “разделяй и властвуй” такая:

возьми первый элемент
остальное пусть посчитает рекурсия

Вот пример кода:

function sumRec(array $arr): int {
    if (count($arr) === 0) {
        return 0; // базовый случай
    }

    return $arr[0] + sumRec(array_slice($arr, 1)); // делаем задачу меньше
}

Стек вызовов по шагам

Тут важно: сначала мы “углубляемся” (стек растет), а потом “поднимаемся” (стек уменьшается и появляются ответы). Мы доходим до базового случая и с него начинаем считать:

sum([]) = 0 – базовый случай
sum([6]) = 6 + sum([])
sum([4,6]) = 4 + sum([6])
sum([2,4,6]) = 2 + sum([4,6])

Шаг	Что вызываем/делаем	Стек	Что вернулось
1	`sumRec([2,4,6])`	`[ main -> sumRec([2,4,6]) ]`	—
2	надо `2 + sumRec([4,6])`, вызываем `sumRec([4,6])`	`[ main -> sumRec([2,4,6]) -> sumRec([4,6]) ]`	—
3	надо `4 + sumRec([6])`, вызываем `sumRec([6])`	`[ main -> sumRec([2,4,6]) -> sumRec([4,6]) -> sumRec([6]) ]`	—
4	надо `6 + sumRec([])`, вызываем `sumRec([])`	`[ main -> sumRec([2,4,6]) -> sumRec([4,6]) -> sumRec([6]) -> sumRec([]) ]`	—
5	`sumRec([])` это база, `return 0`	`[ main -> sumRec([2,4,6]) -> sumRec([4,6]) -> sumRec([6]) ]`	0
6	возвращаемся в `sumRec([6])`: `6 + 0 = 6`, `return 6`. Тут 0 – это то, что вернул sumRec([])	`[ main -> sumRec([2,4,6]) -> sumRec([4,6]) ]`	6
7	возвращаемся в `sumRec([4,6])`: `4 + 6 = 10`, `return 10`	`[ main -> sumRec([2,4,6]) ]`	10
8	возвращаемся в `sumRec([2,4,6])`: `2 + 10 = 12`, `return 12`	`[ main ]`	12

Главное:

на спуске функция только “откладывает” умножение/сложение и ждет ответ снизу.
на подъеме она получает число и наконец складывает.

По сути что мне надо:

Сформировать стек вызовов функций – каждый рекурсивный вызов кладет функцию в стек и делает задачу проще.
И сделать базовый случай когда сработает return и мы пойдем вверх по стеку и начнем считать. Каждый уровень получает результат снизу, делает свое действие, возвращает значение выше.

Короткая формула, чтобы больше не путаться: базовый случай = самый маленький вход, для которого ответ очевиден.

В сумме:

пустой массив
или массив из 1 элемента

в факториале:

n <= 1

в дереве:

узел без детей

СОВЕТ!!
Когда вы пишете рекурсивную функцию, в которой задействован массив, базовым случаем часто оказывается пустой массив или массив из одного элемента. Если вы не знаете, с чего начать, – начните с этого.

Упражнения

4.1 Напишите код для функции sum.

<?php

$arr = [2, 7, 1, 8, 22, 5, 19];

function sum($arr) {
	/*базовый случай*/
	if (count($arr) == 0) return;
	
	/*в рекурсии уменьшаем массив на каждый вызов*/
	return $arr[0] + sum(array_slice($arr, 1));
}

$result = sum($arr);

var_dump($result); // 64

Из интересного, то:

рекурсия не выполняется только снизу вверх или только сверху вниз
код до рекурсивного вызова выполняется на спуске
код после рекурсивного вызова выполняется на подъеме
на подъеме выполняется только та часть функции, которая стоит ПОСЛЕ рекурсивного вызова, + сам return, который отдает результат выше.
все, что стоит до рекурсивного вызова, уже отработало на спуске и второй раз не выполняется.

<?php

$arr = [2, 7, 1, 8, 22, 5, 19];

function sum($arr) {
	/*базовый случай*/
	if (count($arr) == 0) return;
	
	var_dump(count($arr));
	
	/*в рекурсии уменьшаем массив на каждый вызов*/
	return $arr[0] + sum(array_slice($arr, 1));
}

$result = sum($arr);

// Output
int(7)
int(6)
int(5)
int(4)
int(3)
int(2)
int(1)

если бы написал так:

function sum($arr) {
    if (count($arr) == 0) return 0;

    $res = $arr[0] + sum(array_slice($arr, 1));
    var_dump(count($arr)); // <-- теперь после рекурсии
    return $res;
}

// Output
int(1)
int(2)
int(3)
int(4)
int(5)
int(6)
int(7)

потому что теперь var_dump срабатывает на подъеме, когда стек уже разматывается.

если сказать совсем коротко, одной фразой, чтобы закрепить:

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

Еще один пример:

function f($x) {
    // 1. код ДО рекурсии
    doSomethingBefore();

    // 2. рекурсивный вызов
    $result = f($x - 1);

    // 3. код ПОСЛЕ рекурсии
    doSomethingAfter($result);

    return $result;
}

Что происходит:

СПУСК (формируем стек):

выполняется doSomethingBefore()
вызывается f($x - 1)
функция “замораживается” на этой строке

ПОДЪЕМ (разматываем стек):

f($x - 1) вернул значение
выполняется doSomethingAfter()
выполняется return
управление возвращается уровнем выше

Очень важная мысль:

👉 каждый уровень функции “просыпается” ровно в том месте, где он ждал рекурсивный вызов.

он не начинает функцию заново.
он продолжает с того же места.

поэтому:

код после рекурсии выполняется один раз, при выходе
код до рекурсии выполняется один раз, при заходе

4.2 Напишите рекурсивную функцию для подсчета элементов в списке.

<?php

$arr = [2, 7, 1, 8, 22, 5, 19];

function length($arr) {
	/* базовый случай */
	if ($arr == []) {
        return 0;
    }
	
	/*рекурсия*/
	return 1 + length(array_slice($arr, 1));
}

$result = length($arr);

var_dump($result); // 7

4.3 Найдите наибольшее число в списке.

<?php

$arr = [2, 7, 1, 8, 22, 5, 19];

function biggest($arr) {
    /* базовый случай */
    if (count($arr) == 1) {
        return $arr[0];
    }
    
    /*рекурсия*/
	$biggest = biggest(array_slice($arr, 1));
    
    if ($arr[0] > $biggest) {
    	return $arr[0];
    }
	
	
	return $biggest;
}

$result = biggest($arr);

var_dump($result);

Базовый случай – если в массиве один элемент, он и есть максимум.

Быстрая сортировка

Воспользуемся быстрой сортировкой для упорядочения массива. Как выглядит самый простой массив, с которым может справиться алгоритм сортировки? Некоторые массивы вообще не нуждаются в сортировке.

Пустые массивы и массивы, содержащие всего один элемент, станут базовым случаем. Такие массивы можно просто возвращать в исходном виде – сортировать ничего не нужно:

def quick sor t(array):
  if len(array) < 2:
     return array

Теперь перейдем к массивам большего размера. Массив из двух элементов тоже сортируется без особых проблем.

А как насчет массива из трех элементов?

Помните: мы используем стратегию «разделяй и властвуй» . Следовательно, массив должен разделяться до тех пор, пока мы не придем к базовому случаю.

Алгоритм быстрой сортировки работает так:

сначала в массиве выбирается элемент, который называется опорным.

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

Теперь мы находим элементы, меньшие опорного, и элементы, большие опорного.

Этот процесс называется разделением. Теперь у вас имеются :

подмассив всех элементов, меньших опорного;
опорный элемент;
подмассив всех элементов, больших опорного.

Два подмассива не отсортированы – они просто выделены из исходного массива. Но если бы они были отсортированы, то провести сортировку всего массива было бы несложно.

Если бы подмассивы были отсортированы, то их можно было бы объединить в порядке “левый подмассив – опорный элемент – правый подмассив” и получить отсортированный массив . В нашем примере получается [10, 15] + [33] + [] = [10, 15, 33], то есть отсортированный массив.
Как отсортировать подмассивы? Базовый случай быстрой сортировки уже знает, как сортировать массивы из двух элементов (левый подмассив) и пустые массивы (правый подмассив). Следовательно, если применить алгоритм быстрой сортировки к двум подмассивам, а затем объединить результаты, получится отсортированный массив!

quicksort([lS, 10]) + [33) + quicksort([])
> [ 10, 15, 33]

Этот метод работает при любом опорном элементе. Допустим, вместо 33 в качестве опорного был выбран элемент 15.

Оба подмассива состоят из одного элемента, а вы уже умеете сортировать такие подмассивы. Получается, что вы умеете сортировать массивы из трех элементов. Это делается так:

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

Как насчет массива из четырех элементов?

Предположим, опорным снова выбирается элемент 33.

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

Следовательно, вы можете отсортировать массив из четырех элементов.
А если вы можете отсортировать массив из четырех элементов, то вы также можете отсортировать массив из пяти элементов. Почему? Допустим, имеется массив из пяти элементов.

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

Все эти подмассивы содержат от 0 до 4 элементов. А вы уже знаете , как отсортировать массив, содержащий от 0 до 4 элементов, с использованием быстрой сортировки! Таким образом, независимо от выбора опорного элемента вы можете рекурсивно вызывать быструю сортировку для двух подмассивов.
Например, предположим, что в качестве опорного выбирается элемент 3.
Вы применяете быструю сортировку к подмассивам.

Подмассивы отсортированы, и теперь из них можно собрать отсортированный массив. Решение работает даже в том случае, если выбрать в качестве опорного элемент 5:

Итак, решение работает независимо от выбора опорного элемента. Следовательно, вы можете отсортировать массив из пяти элементов. По той же логике вы можете отсортировать массив из шести элементов и т. д.

А вот как выглядит программный код быстрой сортировки:

def quicksort(array):
    # Базовый случай:
    # массивы с 0 или 1 элементом уже "отсортированы"
    if len(array) < 2:
        return array
    else:
        # Рекурсивный случай

        # опорный элемент (pivot)
        pivot = array[0]

        # подмассив всех элементов, меньших или равных опорному
        less = [i for i in array[1:] if i <= pivot]

        # подмассив всех элементов, больших опорного
        greater = [i for i in array[1:] if i > pivot]

        # рекурсивно сортируем подмассивы и собираем результат
        return quicksort(less) + [pivot] + quicksort(greater)


print(quicksort([10, 5, 2, 3]))

Стек вызовов

Массив каждый раз делится надвое.

Мое решение на PHP

<?php

$arr = [2, 7, 1, 8, 22, 5, 19, 33, 91, 220, 44, 66, 91, 177, 3, 9];

function fastSort($arr) {
	
	$length = count($arr);
	
	$mid = round($length / 2);
	
	/* базовый случай */
	if ($length < 2) {
        return $arr;
    }
    
    /*Выбираем опорную точку*/
    $pivot = $arr[$mid];
    
    /*Формируем 2 массива: 1-й с числами меньше опорного*/
    $smaller = [];
    
    foreach($arr as $num) {
    	if ($num < $pivot) {
    		$smaller[] = $num;
    	}
    }
    
    /*Формируем 2 массива: 2-й с числами больше опорного*/
	$bigger = [];
    
    foreach($arr as $num) {
    	if ($num > $pivot) {
    		$bigger[] = $num;
    	}
    }
    
    
    /* Рекурсия: продолжаем каждый подмассив делать на 2 части*/
	$sortedSmaller = fastSort($smaller);
	$sortedBigger = fastSort($bigger);
	$result = array_merge($sortedSmaller, [$pivot], $sortedBigger);
	
	return $result;
}

$result = fastSort($arr);

var_dump($result);

// Output
array(15) {
  [0]=>
  int(1)
  [1]=>
  int(2)
  [2]=>
  int(3)
  [3]=>
  int(5)
  [4]=>
  int(7)
  [5]=>
  int(8)
  [6]=>
  int(9)
  [7]=>
  int(19)
  [8]=>
  int(22)
  [9]=>
  int(33)
  [10]=>
  int(44)
  [11]=>
  int(66)
  [12]=>
  int(91)
  [13]=>
  int(177)
  [14]=>
  int(220)
}

⚠️ Важное замечание

В вашем коде теряются дубликаты! В исходном массиве две 91, а в результате только одна. Это потому что условия < pivot и > pivot не включают == pivot, и все элементы равные pivot (кроме одного) исчезают. Но для учебного примера упустим.

Стек вызовов быстрой сортировки

#	Глубина	Вызов	Массив	pivot	smaller	bigger
1	0	`fastSort([2,7,1,8,22,5,19,33,91,220,44,66,91,177,3,9])`	16 эл.	33	[2,7,1,8,22,5,19,3,9]	[91,220,44,66,91,177]
2	1	`fastSort([2,7,1,8,22,5,19,3,9])`	9 эл.	5	[2,1,3]	[7,8,22,19,9]
3	2	`fastSort([2,1,3])`	3 эл.	1	[]	[2,3]
4	3	`fastSort([])`	0 эл.	—	—	—
5	3	`fastSort([2,3])`	2 эл.	3	[2]	[]
6	4	`fastSort([2])`	1 эл.	—	—	—
7	4	`fastSort([])`	0 эл.	—	—	—
8	2	`fastSort([7,8,22,19,9])`	5 эл.	22	[7,8,19,9]	[]
9	3	`fastSort([7,8,19,9])`	4 эл.	8	[7]	[19,9]
10	4	`fastSort([7])`	1 эл.	—	—	—
11	4	`fastSort([19,9])`	2 эл.	9	[]	[19]
12	5	`fastSort([])`	0 эл.	—	—	—
13	5	`fastSort([19])`	1 эл.	—	—	—
14	3	`fastSort([])`	0 эл.	—	—	—
15	1	`fastSort([91,220,44,66,91,177])`	6 эл.	66	[44]	[91,220,91,177]
16	2	`fastSort([44])`	1 эл.	—	—	—
17	2	`fastSort([91,220,91,177])`	4 эл.	91	[]	[220,177]
18	3	`fastSort([])`	0 эл.	—	—	—
19	3	`fastSort([220,177])`	2 эл.	177	[]	[220]
20	4	`fastSort([])`	0 эл.	—	—	—
21	4	`fastSort([220])`	1 эл.	—	—	—

Визуализация стека (дерево вызовов)

fastSort([2,7,1,8,22,5,19,33,91,220,44,66,91,177,3,9]) pivot=33
├── fastSort([2,7,1,8,22,5,19,3,9]) pivot=5
│   ├── fastSort([2,1,3]) pivot=1
│   │   ├── fastSort([]) → []
│   │   └── fastSort([2,3]) pivot=3
│   │       ├── fastSort([2]) → [2]
│   │       └── fastSort([]) → []
│   │       → [2,3]
│   │   → [1,2,3]
│   └── fastSort([7,8,22,19,9]) pivot=22
│       ├── fastSort([7,8,19,9]) pivot=8
│       │   ├── fastSort([7]) → [7]
│       │   └── fastSort([19,9]) pivot=9
│       │       ├── fastSort([]) → []
│       │       └── fastSort([19]) → [19]
│       │       → [9,19]
│       │   → [7,8,9,19]
│       └── fastSort([]) → []
│       → [7,8,9,19,22]
│   → [1,2,3,5,7,8,9,19,22]
└── fastSort([91,220,44,66,91,177]) pivot=66
    ├── fastSort([44]) → [44]
    └── fastSort([91,220,91,177]) pivot=91
        ├── fastSort([]) → []
        └── fastSort([220,177]) pivot=177
            ├── fastSort([]) → []
            └── fastSort([220]) → [220]
            → [177,220]
        → [91,177,220]
    → [44,66,91,177,220]
→ [1,2,3,5,7,8,9,19,22,33,44,66,91,177,220]

Discover other Guides

View all guides View all guides