Сортировка без магии

Sorting Without a Hat TODO у автора обыгран sorting hat из ГП В этой главе мы поймём: In this chapter, you will learn:

• Что алгоритмы сортировки основаны на сравнении и пользуются двумя основными действиями: • How comparison-based sorting algorithms require two fundamental operations:

  • определением порядка элементов A[i] < A[j], — less(i,j) determines whether A[i] < A[j].

  • обменом элементов A[i] и A[j] местами. — swap(i,j) swaps the contents of A[i] and A[j].

• Как использовать компаратор и сравнение по ключу для сортировки последовательности в произвольном порядке или для сортировки объектов, порядок которых вообще не определён — например, координат точек (x, y) на плоскости. • How to provide a comparator function when sorting; for example, you can sort integers or string values in descending order. The comparator function can also sort complex data structures with no default ordering; for example, it is not clear how to sort a collection of two-dimensional (x, y) points.

• Как по тексту программы понять, что некоторые алгоритмы, например, сортировка вставками и сортировка выбором, имеют неоправданно высокую сложность O(N²). • How to identify inefficient O(N2) sorting algorithms, such as Insertion Sort and Selection Sort, from the structure of their code.

• Как использовать одно из важнейших понятий в программировании — рекурсию, когда функция вызывает сама себя — для решения задач с помощью алгоритмов типа «разделяй и властвуй». • Recursion, where a function can call itself. This fundamental computer science concept forms the basis of a divide-and-conquer strategy for solving problems.

• Как стратегия «разделяй и властвуй» помогает сортировке слиянием и быстрой сортировке упорядочивать массив из N элементов за O(N log N) действий, и как пирамидальная сортировка достигает того же быстродействия без этой стратегии. • How Merge Sort and Quicksort can sort an array of N values in O(N log N) using divide and conquer. How Heap Sort also guarantees O(N log N).

• Как сортировка Тима (которая используется в Python по умолчанию) объединяет преимущества сортировки вставками и сортировки слиянием и тоже показывает быстродействие O(N log N). • How Tim Sort combines Insertion Sort and functionality from Merge Sort to implement Python’s default sorting algorithm in guaranteed O(N log N).

Опять автор использует имя функции в качестве английского слова, пришлось заменить; также см. ниже замечание относительно выбора между компаратором и ключом -- FrBrGeorge 2022-10-22 22:17:41

В этой главе мы будем рассматривать алгоритмы, которые решают такую задачу: переставить элементы в массиве размером N так, чтобы они шли в порядке возрастания. Многие более сложные задачи можно упростить и решать более эффективно, если набор данных предварительно отсортировать; временами без сортировки вообще не обойтись. Сортировка очень часто возникает и в повседневных задачах — например, листок со списком сотрудников и их телефонами обычно отсортирован по именам, а список рейсов на табло в аэропорту — по времени вылета. In this chapter, I present algorithms that rearrange the N values in an array so they are in ascending order. Organizing a collection of values in sorted order is an essen‐ tial first step to improve the efficiency of many programs. Sorting is also necessary for many real-world applications, such as printing staff directories for a company with the names and phone numbers of employees, or displaying flight departure times on an airport display.

Если данные в массиве не отсортированы, поиск элемента в наихудшем случае имеет сложность O(N), а если отсортированы — можно применить двоичный поиск, сложность которого в наихудшем случае O(log N). With an unordered array, searching for a value, in the worst case, is O(N). When the array is sorted, Binary Array Search, in the worst case, can locate a target value in O(log N) performance.

Обмен элементов в сортировке

Sorting by Swapping

Попробуем отсортировать массив A, изображённый на иллюстрации 5-1 сверху. Можно написать числа на клочках бумаги или делать пометки карандашом в прямо книге (только стереть их потом!). Условие: можно использовать только два действия: сравнение двух элементов и обмен местами двух элементов. Какое наименьшее количество обменов потребуется? Заодно стоит посчитать количество сравнений. В примере массив отсортирован посредством пяти обменов — а можно ли было меньше?¹ Try sorting the values in the array, A, at the top of Figure 5-1. Use a pencil to copy the values from Figure 5-1 onto a piece of paper (or bring out a pen and just write on these pages!). I challenge you to sort these values in ascending order by repeatedly swapping the location of two values in the array. What is the fewest number of swaps that you need? Also, count the number of times you compare two values together. I have sorted these values with five swaps. Is it possible to use fewer?11 No. See the challenge exercises at the end

Иллюстрация 5-1. Сортировка некоторого массива A

Считать количество попарных сравнений элементов не мене важно, чем считать число их обменов. Итак, найти наименьший элемент в A — число 2 — можно за семь сравнений, как это было показано в главе 1. Минимум найден в A[3], так что меняем его местами с A[0], и теперь в начале массива, на своём месте, стоит наименьший элемент. Элементы, которые меняются местами на очередном шаге, выделены на иллюстрации 5-1 серым. Жирной рамкой обведены области массива, элементы которых гарантированно стоят на своих местах и не больше переместятся. Это две непрерывные области с двух концов массива, а всю середину нужно сортировать дальше. While it’s important to count the number of swaps, you also need to count the num‐ ber of comparisons between two values. To start, you can determine that 2 is the small‐ est value in A, with just seven comparisons, something I showed in Chapter 1. The smallest value is found at A[3], so it is swapped with A[0]. This moves the smallest value to the front of the array where it belongs. In Figure 5-1, I highlight values when they are swapped. I use bold borders to mark the values that are guaranteed to be in their final location; these will not be swapped again. All values outside of the bolded borders remain to be sorted.

Осталось семь элементов, из которых за шесть сравнений мы находим наибольший, 24 в позиции A[5], и меняем его местами с последним элементом, A[7]. В оставшемся отрезке из шести элементов за пять сравнений мы находим наименьший, 5 в позиции A[6], и меняем его местами с начальным элементом отрезка, A[1]. Теперь снова находим наибольший, 21, оказывается, он уже на своём месте, и обменов не требуется. I scan the remaining values to find the largest value, 24, (using six comparisons) and swap A[5] and A[7] to move the largest value to the end of the array. I then locate the smallest remaining value, 5, (using five comparisons) and swap A[1] and A[6] to move 5 into its proper place. It looks like 21 is in its right spot, which takes four com‐ parisons to validate; no need for a swap here!

Среди четырёх элементов отрезка за три сравнения находим наименьший, 15, и меняем местами с началом отрезка — A[4] меняем c A[2]. Снова поищем минимум, уже за два сравнения, это снова окажется 15, и оно стоит на своём месте. Теперь сравним оставшиеся два элемента, A[4] и A[5] и поменяем их местами. Это последнее действие на иллюстрации 5-1, и можно заметить, что оба элемента при этом оказываются на своих местах, например, 20 не меньше каждого элемента слева от него, и не больше каждого элемента справа. Итак, массив отсортирован за 28 сравнений и 5 обменов. With three comparisons, I find that 15 is the smallest remaining value, and I choose to swap the second occurrence of 15, A[4], with A[2]. With two comparisons, you can validate that 15 belongs in index position 3, which leaves just one more compari‐ son to swap A[4] and A[5], moving 19 into its proper spot. In the final step shown in Figure 5-1, the value 20 is in the right location, since it is larger than or equal to all values to its left and is smaller than or equal to all values to its right. With five exchanges and 28 comparisons, I have sorted this array.

Никакого конкретного алгоритма в нашей сортировке не наблюдалось — мы искали то минимум, то максимум без особых причин. Тем не менее число сравнений на каждом шаге уменьшалось на единицу, и было не более одного обмена за шаг (что куда меньше числа сравнений). Давайте теперь опишем чёткий алгоритм для массива из N элементов, и оценим его производительность. I didn’t follow a specific algorithm to sort this small group of values; sometimes I looked for the smallest value, while other times I looked for the largest. The number of comparisons is reduced after each swap, and there are far more comparisons than swaps. I now define a sorting algorithm that works on any array of N values and eval‐ uate its runtime performance.

Сортировка выбором

Selection Sort

Сортировка выбором названа так из-за того, что в ней массив просматривается справа налево, и на каждую очередную позицию выбирается наименьший из оставшихся элементов и меняется местами с тем, что находится в этой позиции сейчас. Для сортировки N элементов массива A сначала надо найти наименьший по всему массиву и поменять его местами с A[0], затем — наименьший среди оставшихся N - 1 элементов, и поменять его местами с A[1]. Останется N - 2 неотсортированных элемента, и так следует повторять, пока не останется один — наибольший. Selection Sort is named because it incrementally sorts an array from left to right, repeatedly selecting the smallest value remaining and swapping it into its proper loca‐ tion. To sort N values, find the smallest value and swap it with A[0]. Now only N – 1 values remain to be sorted, since A[0] is in its final spot. Find the location of the smallest remaining value and swap it with A[1], which leaves N – 2 values to sort. Repeat this process until all values are in place.

Что делать, если на некотором шаге наименьший элемент уже находится на своём месте? В примере ниже это значит, что по окончании цикла по j значение i окажется равным min_index. Да ничего! Программа попытается поменять местами A[i] и A[min_index], и массив не изменится. Можно попробовать проверять, что i и min_index не равны, и только тогда менять местами ячейки, но заметного прироста производительности это не даст.

В примере 5-1 внешний цикл по i перебирает почти все позиции в массиве, от 0 до N - 2. Внутренний цикл по j перебирает позиции оставшихся неотсортированными элементов, от i + 1 до N - 1 — среди них нужно найти наименьшее. В конце цикла по i элемент массива в позиции i меняется местами с найденным наименьшим элементом в позиции min_index. In Listing 5-1, there is an outer for loop over i that iterates through nearly every index position in the array, from 0 to N – 2. The inner for loop over j iterates through the remaining index positions in the array, from i+1 up to N – 1 to find the smallest remaining value. At the end of the for loop over i, the value at index posi‐ tion i is swapped with the smallest value found at index position min_index.

   1 def selection_sort(A):
   2   N = len(A)
   3   for i in range(N-1):                          # 1
   4     min_index = i                               # 2
   5     for j in range(i+1, N):
   6       if A[j] < A[min_index]:                   # 3
   7         min_index = j
   8       A[i], A[min_index] = A[min_index], A[i]   # 4

• Пример 5-1. Сортировка выбором. Listing 5-1. Selection Sort

1. На каждом шаге цикла по i мы знаем, что A[0 … i-1] уже отсортированы. Before each pass through the i for loop, you know A[0 .. i-1] is sorted. /

2. Индекс наименьшего элемента среди A[i … N-1] будет занесён в min_index. /* min_index is the index location of the smallest value in A[i .. N-1].

3. Если какой-то A[j] окажется меньше A[min_index], надо обновить min_index — запомнить позицию наименьшего на данный момент элемента. If any A[j] < A[min_index], then update min_index to remember index location for this newly discovered smallest value.

4. После обмена A[i] и A[min_index] отсортированы будут уже A[0 … i]. Swap A[i] with A[min_index] to ensure that A[0 .. i] is sorted.

Внешний цикл сортировки выбором работает с набором данных размера N (всем массивом), а затем размер задействованного набора уменьшается на 1 с каждым оборотом цикла — сначала до N - 1, затем — до N - 2 и так до конца сортировки. Иллюстрация 5-2 показывает, что для этого требуется ровно N - 1 обмен. At a high level, Selection Sort starts with a problem of size N and reduces it one step at a time, first to a problem of size N – 1, then to a problem of size N – 2, until the whole array is sorted. As shown in Figure 5-2, it takes N – 1 swaps to sort an array.

После N - 1 обмена все элементы оказываются на своих местах, включая последний, A[N - 1] — он не участвовал в поиске минимума, но остался один, и значит, он наибольший. Теперь попробуем посчитать количество сравнений — это чуть-чуть сложнее. На иллюстрации 5-2 сравнений всего 28, что равно сумме чисел от 1 до 7. After these swaps have properly placed N – 1 values into their final location, the value at A[N–1] is the largest remaining unsorted value, which means it is already in its final location. Counting the number of comparisons is more complicated. In Figure 5-2, it was 28, which is the sum of the numbers from 1 through 7.

Сумму значений от 1 до K можно вычислить как K · (K + 1) / 2. Такие числа в математике называются треугольными, потому что K · (K + 1) / 2 предмета можно расположить в виде треугольника. На иллюстрации 5-3 наглядно представлено само треугольное число 28, и идея, на которой основана формула. Mathematically, the sum of the numbers from 1 to K is equal to K × (K + 1)/2; Figure 5-3 shows a visualization to provide the intuition behind this formula. Num‐ ber 28 is called a triangle number, from the shape formed by the arrangement of cells.

Расположим предметы в виде треугольника из K строк и K элементов в самой длинной строке. Продублируем этот треугольник, перевернём вверх ногами, и приложим к исходному. Получим прямоугольник размером K на K + 1. Выходит, что количество предметов в треугольнике — это ровно половина количества предметов в прямоугольнике. Для треугольника из семи строк «двойной» прямоугольник будет состоять из 7 · 8 = 56 предметов, значит, в треугольнике их 28. В сортировке K = N - 1, это количество сравнений на первом шаге, необходимое для поиска минимума. Общее число сравнений равно (N - 1) · N / 2. If you make a second triangle equal in size to the first and rotate it 180 degrees, the two triangles combine to form a K by K + 1 rectangle. The count of the squares in each triangle is half the number of squares in the 7 x 8 rectangle. In this figure, K = 7. When sorting N values, K = N – 1 since that is the number of comparisons in the first step to find the smallest value: the total number of comparisons is (N – 1) × N/2 or ½ × N2 – ½ × N.

Мало того, что это материал четвёртого класса средней школы, автор умудрился нарушить логическую последовательность рассуждений и привести потенциально некорректную формулу ½N²-½N. Исправил как мог. -- FrBrGeorge 2022-09-21 09:17:53

Иллюстрация 5-2. Сортировка произвольного массива выбором

Иллюстрация 5-3. Наглядное представление формулы треугольного числа: 28 как сумма от 1 до 7

Структура квадратичных алгоритмов сортировки

Anatomy of a Quadratic Sorting Algorithm

Доминирующая составляющая в оценке сложности сортировки выбором — это количество сравнений, их порядка N², значит, и быстродействие окажется ей под стать — O(N²). В самом деле, в алгоритме сортировки N элементов ровно N - 1 шаг. На первом шаге для поиска минимума необходимо N - 1 сравнение, и только один элемент встаёт на своё место. На оставшихся N - 2 шагах количество сравнений уменьшается, но так медленно, что только под самый конец в них отпадает необходимость. При таком подходе число сравнений будет строго соответствовать формуле, то есть иметь квадратичный порядок. Можно ли как-то уменьшить это число? The analysis for Selection Sort shows that the number of comparisons is dominated by the N2 term, which means its performance will be O(N2) since that is the dominant operation. To explain why, look at how Selection Sort has N – 1 distinct steps when sorting N values. In the first step, it finds the smallest value in N – 1 comparisons, and only one value is moved into its proper location. In each of the subsequent N – 2 steps, the number of comparisons will (ever so slowly) decrease until there is no work done in the final step. Can something be done to reduce the number of comparisons?

Сортировка вставками — это другой подход, в котором для упорядочивания массива слева направо тоже нужно проделать N - 1 отдельных шагов. Начнём с того, что массив из одного элемента всегда упорядочен; а вдруг A[0] — и вправду наименьший, ведь и такое случается?. Если на первом шаге окажется, что A[1] меньше A[0], A[1] надо поставить в начало — в данном случае, поменять местами с A[0]. На втором шаге мы рассматриваем A[2] и пробуем вставить его на своё место, считая, что массив пока состоит только из трёх элементов. Возможны три варианта: A[2] и так на своём месте; его надо вставить между A[0] и A[1]; его надо вставить в начало, перед A[0]. Однако нельзя просто так вставить в классический массив один элемент между другими — можно только «сдвинуть» все ячейки поэлементно. Для этого надо запомнить исходный элемент, поставить соседа на его место, поставить следующего соседа на место соседа и т. д. до нужной позиции, но которую поставить исходный элемент. Другой вариант — менять местами элементы попарно до тех пор, пока исходный не встанет на своё место². Insertion Sort is a different sorting algorithm that also uses N – 1 distinct steps to sort an array from left to right. It starts by assuming that A[0] is in its proper location (hey, it could be the smallest value in the array, right?). In its first step, it checks if A[1] is smaller than A[0] and swaps these two values as needed to sort in ascending order. In the second step, it tries to insert the A[2] value into its proper sorted loca‐ tion when just considering the first three values. There are three possibilities: either A[2] is in its proper spot, or it should be inserted between A[0] and A[1], or it should be inserted before A[0]. However, since you cannot insert a value between two array positions, you must repeatedly swap values to make room for the value to be inserted.

Как показано на иллюстрации 5-4, каждый шаг завершается последовательным обменом соседних ячеек, пока те не упорядочены. At the end of each step, as shown in Figure 5-4, Insertion Sort repeatedly swaps neighboring out-of-order values.

Иллюстрация 5-4. Сортировка вставками в произвольный массив

Все элементы, которые пришлось менять местами, выделены серым, а отсортированная область массива обведена жирной чертой. На иллюстрации видно, что элементы в отсортированной области время от времени тоже переставляются (в сортировке выбором было не так). Количество последовательных обменов, приводящих к вставке элемента на своё место, иногда довольно велико (как, например, при вставке 5), а иногда (как, например, при вставке 21 и 24), обменов вовсе не требуется — очередное значение и так больше остальных, и порядок сохраняется. В нашем примере 20 сравнений и 14 обменов. При сортировке вставками число сравнений всегда больше числа обменов, но по сравнению с сортировкой выбором обменов больше, а сравнений меньше. Неожиданно простая реализация этого алгоритма приведена в примере 5-2. All swapped values are highlighted, and bold borders identify the sorted values in the array. Unlike Selection Sort, values within the bold borders may continue to be swap‐ ped, as you can see in the figure. At times (like when the value 5 is inserted) there is a sequence of cascading swaps to move that value into its proper place because the value to insert is smaller than most of the already sorted values. At other times (like when 21 or 24 is inserted), no swaps are needed because the value to insert is larger than all of the already-sorted values. In this example, there are 20 comparisons and 14 swaps. For Insertion Sort, the number of comparisons will always be greater than or equal to the number of swaps. On this problem instance, Insertion Sort uses fewer comparisons than Selection Sort but more swaps. Its implementation, in Listing 5-2, is surprisingly brief.

   1 def insertion_sort(A):
   2   for i in range(1, len(A)):            # 1
   3     for j in range(i, 0, -1):           # 2
   4       if A[j-1] <= A[j]:                # 3
   5         break
   6       A[j], A[j-1] = A[j-1], A[j]       # 4

Listing 5-2. Insertion Sort

1. На каждом шаге цикла по i мы знаем, что A[0 … i-1] уже отсортированы. Before each pass through the i for loop, you know A[0 .. i-1] is sorted.

2. Индекс j уменьшается от i до 1 включительно — это возможные положения элемента, с которым нужно менять местами вставляемый. Decrement j from index location i back to 0 but not including 0.

3. Если A[j-1] не больше A[j], место для вставки найдено, и цикл останавливается. If A[j-1] ≤ A[j], then A[j] has found its proper spot, so stop.

4. В противном случае меняем местами два элемента: они нарушали порядок Otherwise, swap these out-of-order values.

Больше всего работы достаётся сортировке вставками, когда очередное добавляемое значение меньше всех уже отсортированных. Наихудший случай для сортировки вставками — значения, упорядоченные по убыванию. При этом на каждом шаге и количество сравнений, и количество обменов увеличивается на 1, так что обе характеристики оказываются уже знакомыми нам треугольными числами. Insertion Sort works the hardest when each value to be inserted is smaller than all already-sorted values. The worst case for Insertion Sort occurs when the values are in descending order. In each successive step, the number of comparisons (and swaps) increases by one, summing in total to the triangle numbers mentioned earlier.

Оценка производительности сортировки выбором и сортировки вставками

Analyze Performance of Insertion Sort and Selection Sort

Сортировка N значений выбором всегда делает N · (N - 1) сравнение и N - 1 обмен. В случае сортировки вставками посчитать количество действий труднее, потому что оно зависит от порядка самих значений в массиве. Сортировка выбором в среднем менее эффективна, но наихудший случай для сортировки вставками — значения, упорядоченные по убыванию — даёт N · (N - 1) сравнений и столько же обменов. Как бы мы ни улучшали эти алгоритмы, порядок сравнений в них — N²; на иллюстрации 5-5 приведены графики быстродействия. Чем это нас не устраивает? Как обычно, сравним, насколько понижается быстродействие, когда входной набор данных увеличивается. Набор из 524288 элементов в 512 раз больше набора из 1024 элементов, а оба алгоритма сортировки работают на нём почти в 275000 раз медленнее.³ Сортировка 524288 значений вставками заняла в эксперименте около двух часов, а сортировка выбором — почти четыре. Если объёмы данных будут больше, очень скоро счёт пойдёт на дни и недели. Это никуда не годится, но квадратичные алгоритмы (сложность которых O(N²)) на лучшее не способны. Selection Sort will always have ½ × N2 – ½ × N comparisons and N – 1 swaps when sorting N values. Counting the operations for Insertion Sort is more complicated because its performance depends on the order of the values themselves. On average, Insertion Sort should outperform Selection Sort. In the worst case for Inser‐ tion Sort, the values appear in descending order, and the number of comparisons and swaps is ½ × N2 – ½ × N. No matter what you do, both Insertion Sort and Selec‐ tion Sort require on the order of N2 comparisons, which leads to the runtime perfor‐ mance visualized in Figure 5-5. Another way to explain this poor behavior is to observe that the problem instance size 524,288 is 512 times as large as 1,024, yet the runtime performance for both Selection Sort and Insertion Sort takes about 275,000 times longer.2 Sorting 524,288 values takes about two hours for Insertion Sort and nearly four hours for Selection Sort. To solve larger problems, you would need to 2 275,000 is about 512 squared. measure the completion times in days or weeks. This is what a quadratic, or O(N2), algorithm will do to you, and it is simply unacceptable performance.

Иллюстрация 5-5. Время работы сортировки вставками и сортировки выбором

Что если мы хотим отсортировать массив в каком-нибудь другом порядке? Хоть бы и по убыванию? В общем случае у нас даже может не быть операции сравнения самих элементов массива, а порядок их важен, что делать тогда? Простой подход состоит в том, чтобы вместо арифметической операции «меньше, чем» использовать заранее заданную функцию-компаратор, которая определит, не нарушается ли порядок в паре значений. Функция эта передаётся в качестве дополнительного параметра алгоритму сортировки. Все алгоритмы в этой главе можно модифицировать таким образом, так что впредь будем для простоты рассматривать только сортировку по возрастанию. В примере 5-3 представлена сортировка вставками с компаратором. What if you wanted to sort an array in descending order? Or what if the values have a complex structure and there is no default less-than operation defined? Each of the sorting algorithms in this chapter can be extended with a parameter for a comparator function to determine how values are to be ordered, as shown in Listing 5-3. For sim‐ plicity, the implementations of the remaining algorithms assume the values are sorted in ascending order.

   1 def less_than(one, two):
   2   return  one <= two
   3 
   4 def insertion_sort_cmp(A, less=less_than):
   5   N = len(A)
   6   for i in range(1, N):
   7     for j in range(i, 0, -1):
   8       if less(A[j-1], A[j]):            # 1
   9         break
  10       A[j], A[j-1] = A[j-1], A[j]

• Пример 5-3. Использование компаратора в алгоритме сортировки Listing 5-3. Providing a comparator function to a sorting algorithm

1. Порядок сортировки определяется возвращаемым значением функции-компаратора, less(). Если less(A[j-1], A[j]) истинно, A[x] должно предшествовать A[y]. Determine sorting order using a provided comparator function, less. If less(A[x],A[y]) is True, then A[x] should appear before A[y].

Компаратор — не просто функция, возвращающая True или False. Он должен обладать свойством сохранения порядка (на математическом языке — транзитивностью), при котором из того, что A предшествует B, а B предшествует C, с необходимостью следует, что A предшествует также и C. Типичный пример нетранзитивного компаратора — определение победителя в игре «камень, ножницы, бумага», в которой ножницы побеждают бумагу, камень побеждает ножницы, но бумага побеждает камень. Задание нетранзитивного компаратора может привести к вечному зацикливанию алгоритма или неоднозначности результата. Для большей безопасности используют т. н. сравнение по ключу, когда переданная алгоритму сортировки функция вычисляет из элемента массива некоторое значение (обычно числовое или строковое) — ключ — а для определения порядка ключи элементов сравниваются заведомо транзитивной операцией «меньше, чем». Именно так устроена стандартная функция sort() в Python.

И сортировка выбором, и сортировка вставками упорядочивают массив за N - 1 шаг, на каждом из которых объём входных данных уменьшается на 1. Совершенно другой подход, который можно назвать «разделяй и властвуй», состоим в том, чтобы разбить задачу на две подзадачи, и решать их по отдельности. Both Selection Sort and Insertion Sort use N – 1 steps to sort an array of N values, where each step reduces the problem size by just one. A different strategy, known as divide and conquer, breaks a problem up into two sub-problems to be solved.

Рекурсия: разделяй и властвуй!

Recursion and Divide and Conquer

Идея рекурсии возникла в математике сотни лет назад. В программировании рекурсия появляется, когда функция вызывает саму себя. The concept of recursion has existed in mathematics for centuries—it occurs when a function calls itself.

Последовательность Фибоначчи начинается с двух целых чисел, 0 и 1. Каждый следующий член этой последовательности — сумма двух предыдущих. Первые несколько чисел последовательности Фибоначчи: 1, 2, 3, 5, 8, 13, и так далее. Можно записать рекуррентное соотношение для n-го члена последовательности Фибоначчи: Fn=Fn-1+Fn-2. Если запрограммировать это вычисление рекурсивно, функция F(n) будет дважды вызывать саму себя.

Факториал натурального числа N — это произведение всех натуральных числе, не превосходящих N. Обозначается он N!, так что 5! = 5 · 4 · 3 · 2 · 1 = 120. Можно записать и рекуррентное соотношение: N! = N · (N - 1)!. Действительно, 120 = 5! = 5 * 4!, где 4! = 24. Пользуясь этим соотношением можно реализовать вычисление факториала рекурсивно. The factorial of an integer, N, is the product of all positive integers less than or equal to N. It is written as “N!”; thus 5! = 5 × 4 × 3 × 2 × 1 = 120. Another way to represent this operation is to state that N! = N × (N – 1)! For example, 120 = 5 × 4!, where 4! = 24. A recursive implementation is shown in Listing 5-4.

   1 def fact(N):
   2   if N <= 1                     # 1
   3     return 1
   4   return N * fact(N - 1)        # 2

• Пример 5-4. Рекурсивное вычисление факториала Listing 5-4. Recursive implementation of factorial

1. Основание рекурсии: если N ⩽ 1, возвращается 1. Base case: return 1 for fact(1) or any N ≤ 1.

2. Рекурсивный вызов: вычислим (N-1)! и домножим его на N. Recursive case: recursively compute fact(N–1) and multiply its result by N.

Функция fact() вызывает сама себя. Это подозрительно! А вдруг она никогда не закончится? Чтобы этого не произошло, в каждую рекурсивную функцию добавляют основание рекурсии — условие, при котором вызова не происходит, и действия не становятся бесконечными. Основание для факториала — N = 1. В этом случае функция сразу возвращает 1 и не выполняет рекурсивного вызова.⁴. Рекурсивный вызов в fact(N) — это fact(N - 1), результат домножается на N, и это и есть факториал. It may seem odd to see a function calling itself—how can you be sure that it will not do so forever? Each recursive function has a base case that prevents this infinite behavior. fact(1) will return 1 and not call itself.3 In the recursive case, fact(N) calls itself with an argument of N – 1 and multiplies the returned computation by N to produce its final result.

На иллюстрации 5-6 показано, как Python интерпретирует команду y = fact(3) (каждое следующее по времени состояние интерпретатора отображается под предыдущим). Прямоугольниками обозначены контексты вызова функции fact() с соответствующими параметрами (3, 2 и 1). Вызов fact(3) приводит к рекурсивному вызову fact(2). В это время вычисление fact(3) «приостанавливается» (на иллюстрации выделено серым) до тех пор, пока не станет известно значение fact(2). Вызову fact(2) в свою очередь требуется рекурсивно вызвать fact(1), так что он тоже приостанавливается (и мы его отмечаем серым) до вычисления fact(1). Тут мы достигаем основания рекурсии, и fact(1) возвращает 1. Контекст вызова fact(1) уничтожается, остаётся только возвращаемое значение (оно выделено пунктирной окружностью), которое передаётся в контекст вызова fact(2), и вычисления в нём возобновляются: возвращается 2 · 1 = 2. Остаётся только исходный контекст вызова fact(3) со значением 2, теперь возобновляется он, вычисляет и позвращает 3 · 2 = 6, и в результате y становится равным 6. Figure 5-6 visualizes the execution of the statement y = fact(3) as time advances downward. Each box represents an invocation of fact() with the given argument (whether 3, 2, or 1). Invoking fact(3) recursively calls fact(2). When that happens, the original fact(3) function will be “paused” (grayed out in the figure) until the value of fact(2) is known. When fact(2) is invoked, it also must recursively call fact(1), so it is paused (and grayed out in the figure) until the value of fact(1) is known. Finally at this point, the base case stops the recursion, and fact(1) returns 1 as its value, shown inside a dashed circle; this resumes the paused execution of fact(2), which returns 2 × 1 = 2 as its value. Finally, the original fact(3) resumes, returning 3 × 2 = 6, which sets the value of y to 6.

Итак, рекурсивный вызов fact(N) порождает цепочку контекстов, приостановленных до тех пор, пока в самом последнем не будет достигнуто основание рекурсии. Затем Python начинает «отматывать» эту цепочку обратно, по одному вызову, до тех пор, пока не завершится самый первый. During recursion, any number of fact(N) invocations can be paused until the base case is reached.4 Then, the recursion “unwinds” one function call at a time until the original invocation is complete.

Иллюстрация 5-6. Рекурсивный вызов fact(3)

Следующий текст — мой, это антитеза авторского «ограничение в 1000 введено "по техническим причинам"», что в контексте данной книги просто неверно. -- FrBrGeorge 2022-09-25 10:10:25

Рекурсивное вычисление факториала — самый популярный, но, к сожалению, неправильный пример использования рекурсии. Из иллюстрации 5-6 понятно, что на реализацию каждого шага рекурсии затрачивается ощутимое количество памяти. Кроме того, язык программирования вынужден выполнять довольно много работы по обслуживанию самого механизма рекурсии: например, Python на каждом шаге создаёт отдельное пространство имён и заводит там локальные переменные; при выходе из рекурсивного вызова всё это надо ещё удалить. Реализация того же алгоритма обычным циклом будет работать в несколько раз быстрее, и, что ещё важнее, будет иметь более низкий порядок сложности по памяти (в нашем случае — O(1), а не O(N)).

Поэтому стоит запомнить одно простое правило. Если в рекурсивно организованном алгоритме, который обрабатывает входные данные размера N, глубина рекурсии (сколько раз максимум функция вложенно вызвала сама себя,) пропорциональна N, то вы, скорее всего реализовали обычный цикл, и так делать не надо. Как мы уже знаем, для этого достаточно увидеть, что объём входных данных при каждом вызове уменьшается на константу (чаще всего, на 1). А вот если объём входных данных при каждом вложенном вызове уменьшается в несколько раз (например, вдвое), глубина рекурсии окажется логарифмической — O(log N) — и это хорошее, годное её применение.

По этим двум причинам (относительная «дороговизна» рекурсивного вызова и бессмысленность замены линейного цикла рекурсией) максимальное количество вложенных вызовов функций друг другом ограничено в Python тысячей. С одной стороны, тысяча контекстов вызова — всё ещё не слишком большое потребление памяти, с другой — очевидно, что даже для двоичного логарифма логарифмическая глубина рекурсии в 1000 актуально недостижима (размер входных данных не может быть 2¹⁰⁰⁰, то есть примерно 10³⁰²).

Наш алгоритм этому логарифмическому критерию не соответствует: в нём объём входных данных N на каждом шаге уменьшается только на единицу. Иллюстрация 5-6 наглядно показывает, что числа от N до 1 — это именно входные данные: все они одновременно хранятся в контекстах вызова и занимают память. Вот если бы было можно разбить входные данные на две примерно равные N / 2 части, и решать две получившихся подзадачи раздельно! Две подзадачи с наборами размера N / 2 в свою очередь разделятся на четыре с размером N / 4, и так далее. Будет ли в этом случае останавливаться рекурсия? Да, потому что последовательное деление конечного N пополам непременно выведет это значение за пределы основания рекурсии, и вычисление каждой подзадачи остановится. In reviewing this algorithm, it still solves a problem of size N by reducing it into a smaller problem of size N – 1. What if the problem of size N could be divided into two problems of, more or less, N/2? It might seem like this computation could go on forever, since each of these two sub-problems are further subdivided into four sub- problems of size N/4. Fortunately the base case will ensure that—at some point—the computations will complete.

Давайте вспомним знакомую нам задачу поиска макcимума в неупорядоченном массиве из N элементов. Напишем вспомогательную функцию rmax(lo, hi), которая ищет наибольшее значение на отрезке массива A[lo … hi]; она-то и будет вызываться рекурсивно.⁵ В примере 5-5 вызов find_max(A) превращается в вызов rmax(0, len(A)–1), в котором задаются исходные границы поиска — lo = 0 и hi = N - 1 (N — это размер массива A). Основанием для rmax() будет единичный размер отрезка — равенство lo и hi, потому что в наборе из одного элемента максимум не нужно искать. Результатом rmax(), наибольшем числом в объединении отрезков, будет наибольший из максимумов в левом и правом отрезке. Consider a familiar problem, trying to find the largest value in an unordered array of N values. In Listing 5-5, find_max(A) invokes a recursive helper function,5 rmax(0,len(A)–1), to properly set up the initial values for lo = 0 and hi = N – 1, where N is the length of A. The base case in rmax() stops the recursion once lo = hi because this represents looking for the largest value in a range containing just a single value. Once the largest values are determined for the left and right sub-problems, rmax() returns the larger of these two values as the largest value in A[lo .. hi].

Переведённые или преобразованные сноски 3 To avoid crashing the Python interpreter because of infinite recursion, this code returns 1 when given any integer less than or equal to 1. 4 In Python, the recursion limit is technically less than 1,000 to prevent crashing the Python interpreter. 5 rmax stands for recursive max.

   1 def find_max(A):
   2 
   3   def rmax(lo, hi):
   4     if lo == hi:                # 2
   5         return A[lo]
   6 
   7     mid = (lo+hi) // 2          # 3
   8     L = rmax(lo, mid)           # 4
   9     R = rmax(mid+1, hi)         # 5
  10     return max(L, R)            # 6
  11 
  12   return rmax(0, len(A)-1)      # 1

• Пример 5-5. Рекурсивный алгоритм поиска максимума в неупорядоченном списке Listing 5-5. Recursive algorithm to find largest value in unordered list

• Исходный вызов рекурсивной функции с заданием стартовых значений для lo и hi. Invoke the initial recursive call with proper arguments for lo and hi.

• Основание рекурсии: единичный размер отрезка A[lo … hi] (равенство lo и hi), единственный элемент и есть максимум. Base case: when lo == hi, the range A[lo .. hi] contains a single value; return it as the largest value.

• Примерная середина отрезка A[lo … hi]. Индексы массива могут быть только целыми, так что используем целочисленное деление. Find midpoint index location in the range A[lo .. hi]. Use integer division // in case range has odd number of values.

• L — максимум в левой половине отрезка, A[lo … mid]. L is the largest value in the range A[lo .. mid].

• R — максимум в правой половине отрезка, A[mid+1 … hi]. R is the largest value in the range A[mid+1 .. hi].

• Максимум на A[lo … hi] — это наибольшее среди L и R. The largest value in A[lo .. hi] is the maximum of L and R.

Функция  rmax(lo, hi) ищет максимум так: делит отрезок исходного массива от lo до hi включительно на два отрезка половинной длины, ищет максимумы в них и сравнивает результаты. На иллюстрации 5-7 показано, как работает rmax(0, 3) на массиве A длиной 4. Для этого решаются две подзадачи — поиск максимума в девой половине массива, rmax(0, 1), и в правой, rmax(2, 3). Поскольку rmax() дважды вызывает рекурсивно сама себя, важно знать в каком именно месте функции вычисление приостановилось. Понадобится новая раскраска: серым фоном, как и прежде, мы будем обозначать контекст функции, чьё выполнение сейчас приостановлено, и там же вдобавок чёрным фоном будем отмечать строки, которые ещё предстоит выполнить, когда вычисления возобновятся. The function rmax(lo, hi) solves this problem recursively by dividing a problem of size N into two problems of half the size. Figure 5-7 visualizes the execution of rmax(0,3) on the given array, A, with four values. To solve this problem, it solves two sub-problems: rmax(0,1) finds the largest value in the left-hand side of A, and rmax(2,3) finds the largest value in the right-hand side of A. Since rmax() makes two recursive calls within its function, I introduce a new visualization to describe where, in rmax(), the execution is paused. I still use a gray background to show that rmax() is paused when it makes a recursive call: in addition, the lines highlighted with a black background will execute once the recursive call returns.

Места на иллюстрации 5-7 хватило только на три первых рекурсивных вызова, в результате которых был найден максимум левой части массива, 21. Мы видим, что две последние строки в соответствующем контексте всё ещё помечены чёрным, напоминая про оставшуюся часть вычислений: продолжением будет очередной рекурсивный вызов, rmax(2,3). Он приведёт ещё к трём похожим рекурсивным вызовам, а уже после них наконец можно будет вычислить и исходное rmax(0, 3): возвращаемое значение вычислится из max(21, 20). In Figure 5-7, I only have space to show the three recursive calls that complete to determine that 21 is the largest value in the left-hand side of A. As you can see, the final two lines in the invocation box for rmax(0,3) are highlighted in black to remind you that the rest of the computation will resume with the recursive call to rmax(2,3). A similar sequence of three additional recursive calls would complete the right-hand sub-problem, ultimately allowing the original recursive invocation rmax(0,3) to return max(21,20) as its answer.

Иллюстрация 5-7. Протокол рекурсивного вызова rmax(0, 3) для массива A = [15, 21, 20, 2]

На иллюстрации 5-8 представлен полный протокол работы rmax(0, 7). Здесь так же, как и в разборе fact(), серым обозначена приостановка вычислений: например, во время того, как rmax(0, 3) дожидается ответа от рекурсивного вызова rmax(0, 1). Исходный массив делится на всё меньшие отрезки до тех пор, пока в очередном вызове оба параметра rmax() не окажутся равными. На иллюстрации мы видим восемь таких случаев, потому что в массиве N = 8 элементов. Во всех восьми случаях мы имеем дело с основанием рекурсии, и, следовательно, дальнейших вызовов не происходит. Максимум массива A, очевидно, 24, и на иллюстрации отдельно отмечены рекурсивные вызовы, которые возвращают этот максимум. Figure 5-8 visualizes the full recursive behavior of rmax(0,7). Similar to my explana‐ tion for fact(), this figure shows how the invocation of rmax(0,3) is paused while it recursively computes the first sub-problem, rmax(0,1). The original problem is repeatedly subdivided until rmax() is invoked where its parameters lo and hi are equal; this will happen eight different times in the figure, since there are N = 8 values. Each of these eight cases represents a base case, which stops the recursion. As you can see in Figure 5-8, the maximum value is 24, and I have highlighted the rmax() recur‐ sive calls that return this value.

Иллюстрация 5-8. Полный протокол рекурсивного вызова rmax(), 7)

Сортировка слиянием

Merge Sort

Смотрим мы на наши примеры, и возникает вопрос: а нельзя ли и для сортировки применить методику «разделяй и властвуй»? Идея в том, чтобы, как это показано в примере 5-6, рекурсивно отсортировать левую половину массива, затем рекурсивно отсортировать правую, а затем как-нибудь быстренько объединить уже отсортированные половины. Тогда и весь массив окажется упорядоченным. Inspired by these examples, we can now ask, “Is there a recursive divide-and-conquer approach to sort an array?” Listing 5-6 contains the gist of an idea: to sort an array, recursively sort its left half, and recursively sort its right half; then somehow merge the partial results to ensure the whole array is sorted.

   1 def sort(A):
   2 
   3   def rsort(lo, hi):            # 1
   4     if hi > lo:                 # 2
   5       mid = (lo+hi) // 2
   6       rsort(lo, mid)            # 3
   7       rsort(mid+1, hi)
   8       merge(lo, mid, hi)        # 4
   9 
  10   rsort(0, len(A)-1)

• Пример 5-6. Идея рекурсивной сортировки Listing 5-6. Idea for sorting recursively

1. Вспомогательная функция, которая сортирует отрезок A[lo … hi]. Recursive helper method to sort A[lo .. hi].

2. Пустой или единичный отрезок сортировать не надо, это основание рекурсии. В противном случае надо вычислять дальше. Base case: a range with one or fewer values is already in sorted order.

3. Рекурсивные вызовы: сортировка левого и правого отрезков массива. Recursive case: sort the left half of A and the right half of A.

4. Слияние двух упорядоченных отрезков и замена их на результат слияния. Merge both sorted halves of the array in place.

Здесь мы воспользовались схемой, которую придумали для функции find_max() и показали в примере 5-5. Если реализация вспомогательной функции merge() окажется достаточно простой, у нас получится настоящая сортировка слиянием — рекурсивный алгоритм, который использует дополнительную память, но в результате сортирует исходный массив за O(N log N) действий — то есть мы наконец-то преодолеем квадратичный порог сложности! The structure of Listing 5-6 is identical to the find_max(A) function described in Listing 5-5. Completing this implementation leads to Merge Sort, an in-place recur‐ sive sorting algorithm that requires extra storage but provides the breakthrough we were looking for, namely an O(N log N) sorting algorithm.

Главное в сортировке слиянием — это функция merge(), слияние двух отрезков массива «по месту», когда отсортированная правая и отсортированная левая половины массива заменяются на результат из слияния. Принцип работы merge() знаком всем, кто когда-либо превращал две упорядоченные колоды карт в одну, тоже упорядоченную. Наглядно этот принцип показан на иллюстрации 5-9. «Карты» на этой иллюстрации — это просто карточки с номерами. The key to Merge Sort is the merge function that merges in place the sorted left half of an array with the sorted right half of an array. The mechanics of merge() might be familiar if you’ve ever had two sorted stacks of paper that you want to merge into one final sorted stack, as shown in Figure 5-9.

Иллюстрация 5-9. Слияние двух колод в одну

Если у нас есть две упорядоченных колоды, сделать из них одну с сохранением порядка можно так. Сравним две карты на вершинах колоды, выберем наименьшую из них и положим на место, где будет формироваться полная колода. Все остальные карты мы будем подсовывать под полную колоду, чтобы сохранить тот же порядок (в нашем случае — возрастания снизу вверх). В примере на первых двух шагах сначала подсовываем 2 из левой колоды, а затем — 5 из правой. Теперь в обеих колодах значения одинаковы — 15; возьмём сначала из левой, затем из правой. Продолжим повторять эти действия до тех пор, пока какая-нибудь из колод не опустеет — это будет предпоследний шаг слияния. На последнем шаге просто заберём все карты из оставшейся непустой колоды — они и так не меньше всех остальных, и уже отсортированы. To merge these two stacks into one stack, look at the topmost remaining value in each stack and choose the smallest one. In the first two steps, 2 is removed from the left stack, and then 5 is removed from the right. When faced with two values that are the same, arbitrarily take the value from the left stack, first removing 15 from the left stack, then removing 15 from the right stack. Repeat this process until one of the stacks is exhausted (which happens in the final eighth step). When only one stack remains, just take all those values as a group, since they are already sorted.

Обратите внимание на то, что нам понадобилось «место, где будет формироваться полная колода». Это означает, что при программировании такого алгоритма понадобится дополнительное хранилище данных. Самым эффективным для сортировки слиянием оказался самый простой способ: завести ещё один массив размером с исходный, и хранить там подлежащие сортировки отрезки, выполняя слияние обратно в исходный массив. Вариант функции merge() приведён в примере 5-7. The merge process sketched in Figure 5-9 works because of the extra storage into which the values are placed. The most efficient way to implement Merge Sort is to initially allocate extra storage equal to the size of the original array being sorted, as shown in Listing 5-7.

   1 def merge_sort(A):
   2     aux = [None] * len(A)                                               # 1
   3 
   4     def rsort(lo, hi):
   5         if hi > lo:                                                     # 2
   6           mid = (lo+hi) // 2
   7           rsort(lo, mid)                                                # 3
   8           rsort(mid+1, hi)
   9           merge(lo, mid, hi)
  10 
  11     def merge(lo, mid, hi):
  12         aux[lo:hi+1] = A[lo:hi+1]                                       # 4
  13         left, right = lo, mid+1                                         # 5
  14         for i in range(lo, hi+1):
  15             if left > mid or right <= hi and aux[right] < aux[left]:    # 6
  16                 A[i] = aux[right]
  17                 right += 1                                              # 7
  18             else:                                                       # 8
  19                 A[i] = aux[left]
  20                 left += 1
  21 
  22     rsort(0, len(A)-1)                                                  # 9

• Пример 5-7. Рекурсивная реализация сортировки слиянием Listing 5-7. Recursive Merge Sort implementation

1. Заводим дополнительное хранилище размером с исходный массив. Allocate auxiliary storage equal in size to original array.

2. Основание рекурсии — отрезок не более чем единичной длины; в противном случае вычисления продолжаются. Base case: with 1 or fewer values, there is nothing to sort.

3. Два рекурсивных вызова: сортировка левой и правой половин отрезка, а затем их слияние. Recursive case: sort left and right sub-arrays and then merge.

4. Копируем элементы двух отсортированных отрезков в хранилище: их предстоит объединить. Copy sorted sub-arrays from A into aux to prepare for merge.

5. Задаём начало левого отрезка, left, и правого — right. Set left and right to be the starting index positions of the corresponding sub-arrays.

6. Элемент правого отрезка мы берём в двух случаях:
   • левый отрезок уже пуст,

   • оба отрезка непусты, и элемент в начале правого отрезка меньше. When left sub-array is exhausted, take value from right sub-array. When right sub-array is exhausted, take value from left sub-array.

7. Сдвигаем начало правого отрезка на следующий его элемент.

8. В двух других случаях — правый отрезок пуст или оба непусты и левый элемент меньше — берём элемент и сдвигаем начало левого отрезка. When right value is smaller than left value, take value from right sub-array. When left value is smaller than or equal to right value, take value from left sub-array.

9. Исходный вызов рекурсивной функции. Invoke the initial recursive call.

В условном операторе внутри цикла функции merge() проявляется свойство ленивых вычислений Python: правый операнд, B, логического выражения «A or B» вычисляется только если значение A ложно, а выражения «A and B» — только если A истинно. В нашем случае нельзя проверять right <= hi и aux[right] < aux[left] одновременно: если первое сравнение ложно, второе, скорее всего, просто ошибочно, и его не нужно даже пытаться интерпретировать. Именно так и работает операция «and»! То же самое и со сравнением left > mid: если оно истинно, не стоит пытаться выполнить остальные сравнения, но именно так (с учётом приоритета and над or) и работает операция or.

На иллюстрации 5-10 по шагам показано, как работает merge(). На первом шаге вызова merge(lo, mid, hi) элементы массива A[lo … hi] копируются в aux[lo … hi] — потому что именно этот отрезок и надо отсортировать. Figure 5-10 visualizes the dynamic behavior of merge(). The first step of merge(lo,mid,hi) is to copy the elements from A[lo .. hi] into aux[lo .. hi] since this is the sub-problem range being sorted.

Цикл по i выполнится восемь раз, потому что всего в массиве восемь элементов, из которых состоят два объединяемых отрезка. Начиная с третьего ряда иллюстрации 5-10 мы можем обращаться к переменным left, right и i, которые хранят интересующие нас индекcы: The for loop over i will execute 8 times, because that is the total size of the two sub- problems being merged. Starting in the third row of Figure 5-10, the variables left, right, and i each keep track of specific locations:

• В переменной left хранится индекс очередного элемента левого отрезка. Если он окажется меньшим, возьмём именно его. • left is the index position of the next value in the left sub-array to be merged.

• В переменной right хранится индекс очередного элемента правого отрезка, он тоже может участвовать в слиянии. • right is the index position of the next value in the right sub-array to be merged.

  • В переменной i хранится индекс элемента основного массива, куда мы записываем значения в порядке возрастания. На последнем шаге весь отрезок A[li … hi] окажется отсортированным. i is the index position in A where successively larger values are copied until, by the last step, all values in A[lo .. hi] are in sorted order.

Иллюстрация 5-10. Слияние отрезков массива по 4 элемента в каждом

left и right не переводятся -- FrBrGeorge 2022-09-30 13:52:51

В цикле for при необходимости сравниваются два значения из aux (выделены серым на иллюстрации 5-10), выбирается меньшее, и оно записывается в A[i]. Переменная i увеличивается на каждом шаге, а left и right — только когда соответствующее значение, aux[left] или aux[right], оказывается очередным наименьшим и переносится в A. Время работы merge() прямо пропорционально сумме длин обоих отрезков, то есть hi - lo + 1. Within the for loop, up to two values in aux (highlighted in Figure 5-10) are com‐ pared to find the lower value, which is then copied into A[i]. With each step, i is incremented, while left and right advance only when the value at aux[left] or aux[right] is found to be the next smallest one to be copied into A. The time to com‐ plete merge() is directly proportional to the combined size of the sub-problems (or hi – lo + 1).

Сортировка слиянием — отличный пример алгоритма в стиле «разделяй и властвуй», быстродействие которого оценивается как O(N log N). В целом произвольную задачу можно решить за O(N log N) действий, если в ней соблюдаются такие условия: Merge Sort is a great example of a divide-and-conquer algorithm that guarantees O(N log N) performance. If you have a problem that satisfies the following checklist, then an O(N log N) algorithm exists:

1. Исходный набор данных можно поделить пополам, и независимо решить две получившиеся подзадачи. Допустимо делить не строго пополам, различие в длина на небольшую константу погоды не делает. • If you can subdivide a problem of size N into two independent sub-problems of size N/2; it is perfectly fine for one sub-problem to be slightly larger than the other.

2. Если в основании рекурсии лежит фиксированное количество действий, или не лежит никаких действий, как в сортировке слиянием. • If you have a base case that either does nothing (like with Merge Sort) or per‐ forms some operations in constant time.

3. Если на каждом шаге рекурсии — и до, и после разделения данных и рекурсивного вызова — количество выполняемых действий прямо пропорционально объёму обрабатываемых данных. Например, в функции merge(), которая выполняется после рекурсивного вызова, количество итераций цикла for равно размеру сортируемого отрезка. • If you have a processing step (either before the problem is subdivided or after‐ ward as a post-processing step) that requires time directly proportional to the number of values in the sub-problem. For example, the for loop in merge() repeats a number of times equal to the size of the sub-problem being solved.

Стоит вспомнить, что время работы программы зависит от конкретной реализации, и его нужно измерять. Таким образом, время работы не может являться свойством задачи. А вот количество действий в алгоритме — может. Если адекватно оценить количество действий, можно предположить, что быстродействие будет удовлетворять той же оценке.

Автор сразу вёл речь о быстродействии как о свойстве задачи, что, по-моему, неверно. -- FrBrGeorge 2022-09-30 13:52:51

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

Quicksort

Быстрая сортировка — ещё один весьма известный и очень эффективный алгоритм в стиле «разделяй и властвуй»⁶. Идея в том, чтобы выбрать в массиве некоторый элемент p (назовём его опорным), и поставить его на своё место, туда, где он окажется в отсортированном массиве. Для этого предлагается переставить местами элементы массива так, чтобы слева от p оказались только не большие p элементы, а справа — только не меньшие. Затем надо рекурсивно отсортировать два отрезка массива слева и справа от позиции p. На иллюстрации 5-11 показан такой массив; можно проверить, что он и правда «разгорожен» элементом p. Another sorting algorithm that follows divide-and-conquer is Quicksort, one of the most heavily studied and efficient sorting algorithms ever designed.6 It recursively sorts an array by selecting an element in A to use as a pivot value, p, and then it inserts p into its proper location in the final sorted array. To do this, it rearranges the contents of A[lo .. hi] such that there is a left sub-array with values that are ≤ p, and a right sub-array with values that are ≥ p. You can confirm in Figure 5-11 that the parti‐ tioned array has this property. 6 Invented by Tony Hoare in 1959, Quicksort is well over 50 years old!

Иллюстрация 5-11. Результат работы partition(A, 0, 7 ,0) с опорным элементом A[0]

Это кажется каким-то трюком на грани мошенничества: как можно знать заранее, куда попадёт p в отсортированном массиве? Оказывается, массив A для этого не нужно сортировать — достаточно переставить местами некоторые элементы по отношению к p. В действительности мы уже видели алгоритм, который умеет это делать: функция partition() встречалась в тренировочных заданиях к главе 1. Именно она и превратила массив на иллюстрации 5-11 в два отрезка: левый состоит из двух элементов, а правый — из семи. Теперь достаточно рекурсивно применить к этим отрезкам быструю сортировку, как в примере 5-8, и задача будет решена. This amazing feat may at first seem impossible—how do you know where p exists in the final sorted array without actually sorting the entire array? It turns out that parti‐ tioning doesn’t sort all elements in A but rearranges just a few based on p. In the chal‐ lenge exercises found in Chapter 1, you can find the implementation of partition(). After partition() completes in Figure 5-11, the left sub-array to be sorted contains two values, while the right sub-array contains five values. Each of these sub-arrays is recursively sorted using Quicksort, as shown in Listing 5-8.

   1 def quick_sort(A):
   2 
   3   def qsort(lo, hi):
   4     if hi > lo:                                   # 1
   5       pivot_idx = lo                              # 2
   6       location = partition(A, lo, hi, pivot_idx)  # 3
   7       qsort(lo, location-1)                       # 4
   8       qsort(location+1, hi)
   9 
  10   qsort(0, len(A)-1)                              # 5

• Пример 5-8. Рекурсивная реализация быстрой сортировки Listing 5-8. Recursive Quicksort implementation

1. Основание рекурсии: если отрезок не длиннее одного элемента, сортировать его не надо, иначе работу следует продолжить. Base case: with 1 or fewer values, there is nothing to sort.

2. Опорным элементом p массива выберем A[lo]. Choose A[lo] as the pivot value, p.

3. Переставим элементы A и вернём позицию p в нём: Return location in A such that:

   • location — это позиция p

   • Все элементы левого отрезка A[lo … location–1] не больше p. • All values in left sub-array A[lo .. location–1] are all ≤ p

   • Все элементы правого отрезка A[location+1 … hi] не меньше p. • All values in right sub-array A[location+1 .. hi] are all ≥ p

4. Рекурсивный вызов: отсортируем элементы обоих отрезков по месту, а p и так уже находится так, где следует — в A[location]. Recursive case: sort in place left and right sub-arrays, since p is already in its proper sorted location, A[location].

5. Исходный вызов рекурсивной функции Invoke the initial recursive call.

Быстрая сортировка — красивое рекурсивное решения задачи, но её эффективность каждого её шага зависит от того, где в отсортированном массиве располагается опорный элемент. Например, если так случится, что функция partition() выберет в качестве опорного наименьший элемент отрезка A[lo … hi] длины N элементов, результатом будет пустой левый отрезок и правый отрезок длины N-1. Если на каждом шагу объём данных уменьшается только на 1, как в сортировке вставками или сортировке выбором, сложность алгоритма станет такой же неэффективной — O(N²). Верхняя часть иллюстрации 5-12 отображает основные шаги быстрой сортировки массива с иллюстрации 5-11. В нижней части перечислены все рекурсивные вызовы. В этой части справа показан сам массив A, и можно пронаблюдать, как меняются его значения при каждом вызове. Здесь опорной точкой отрезка A[lo … hi] всегда выбирается A[lo], так что функция partition() всегда вызывается с параметрами lo, hi, lo. Стечением времени — сверху вниз — становится понятно, что каждый вызов partition() сопровождается одним или двумя рекурсивными вызовами qsort(). Например, partition(0, 7, 0) ставит нас своё место в массиве A число 15 (это место выделено серым), после чего дважды вызывается рекурсивно сначала qsort(0, 1) на левом отрезке, а затем — qsort(3, 7) на правом. Понятно, что qsort(3, 7) запустится только после того, как завершит работу qsort(0, 1). Quicksort presents an elegant recursive solution whose success depends on the parti‐ tioning function. For example, if partition() is invoked on a sub-array A[lo .. hi] containing N values and the smallest value in that sub-array is used as the pivot, then the resulting left sub-array is empty, whereas the right sub-array contains N – 1 val‐ ues. Reducing a sub-problem by 1 is exactly how Insertion Sort and Selection Sort performed, leading to inefficient O(N2) sorting. The top of Figure 5-12 summarizes the key steps of Quicksort applied to the array from Figure 5-11. The bottom of Figure 5-12 shows the full recursive execution. On the right side of the figure, you can see A, the array being sorted, and how its values change in response to the recursive execution. For each partition of a range A[lo .. hi], the selected pivot is always A[lo], which is why each box reads partition(lo,hi,lo). As time moves vertically down the figure, you can see how each partition() invocation leads to 1 or 2 recur‐ sive calls to qsort(). For example, partition(0,7,0) on A places 15 into its final index location (which is why it is grayed out on the right), leading to two subsequent recursive invocations: qsort(0,1) on the left sub-array and qsort(3,7) on the right sub-array. The invocation of qsort(3,7) does not start until qsort(0,1) has comple‐ ted its work.

Каждый вызов partition() приводит к тому, что некоторый элемент массива оказывается на своём месте — на иллюстрации он подкрашивается серым. Если при вызове qsort(lo, hi) отрезок оказывается единичной длины, то есть lo == hi, соответствующий элемент уже на своём месте, и тоже подкрашивается серым. Each time partition is invoked, a different value is placed into its proper index loca‐ tion and grayed out. When qsort(lo,hi) is invoked on a range where lo = hi, that value is in its proper location, and it is also grayed out.

Если вызов partition(lo, hi, lo) привёл только к единственному вызову qsort(), значит, опорный элемент оказался или в позиции A[lo], или в позиции A[hi] — а это означает, что длина сортируемого отрезка уменьшилась только на 1. Таким образом реализация быстрой сортировки из примера 5-8 покажет рекордно низкую — O(N²) — производительность на… уже отсортированном массиве! Поскольку уже отсортированные данные встречаются часто, быструю сортировку пытаются улучшить, выбирая опорный элемент случайно из диапазона A[lo … hi]. В примере для этого достаточно заменить pivot_idx = lo на pivot_idx = random.randint(lo, hi). Десятилетия исследований показали, что теоретическая вероятность наихудшего случая, на котором быстрая сортировка показывает производительность всего O(N²), есть всегда⁷. Несмотря на такой недостаток, именно этот алгоритм часто используют на практике — потому, например, что он не требует дополнительной памяти (как сортировка слиянием). Так-то быстрая сортировка отвечает всем трём требованиям к алгоритму со сложностью O(N log N). When a partition(lo,hi,lo) produces only a single recursive call to qsort(), it is because the pivot value is placed in either A[lo] or A[hi], thus reducing the problem size by just 1. For example, given the implementation in Listing 5-8, Quicksort will degrade its performance to O(N2) when called on an array of already-sorted values! To avoid this behavior, Quicksort is often modified to choose the pivot value ran‐ domly from within the range A[lo .. hi] by replacing pivot_idx = lo in Listing 5-8 with pivot_idx = random.randint(lo, hi). Decades of research have con‐ firmed that there is always a theoretical possibility that in the worst case, Quicksort will have a runtime performance of O(N2). Despite this weakness, Quicksort is often the sorting algorithm of choice because, unlike Merge Sort, it does not require any extra storage. In reviewing the structure for Quicksort, you can see that it conforms to the checklist for O(N log N) algorithms.

Иллюстрация 5-12. Полный протокол рекурсивного вызова функции quicksort()

Больше ничего переводить не надо -- FrBrGeorge 2022-10-07 15:31:29

Есть и другой способ добиться производительности O(N log N): выполнить N шагов, каждый из которых будет не сложнее O(log N). В пирамидальной сортировке используется уже знакомая нам структура данных — куча, и можно ожидать, что N операций добавления произвольных элементов в кучу и N операций снятия (уже упорядоченных элементов), при сложности этих операций не более log N, и дадут нам искомое O(N log N). Another way to achieve O(N log N) is to have N steps where the runtime perfor‐ mance of each step is O(log N). Using the heap data structure introduced in the last chapter, I now present Heap Sort, whose runtime performance is O(N log N).

Пирамидальная сортировка

Heap Sort

Давайте разберёмся, как с помощью кучи отсортировать массив. На иллюстрации 5-13 показан массив с иллюстрации 4-17, то есть обладающий свойствами кучи. Наибольший его элемент находится в A[1]. Когда мы снимаем наибольший элемент с кучи, содержимое массива перестраивается, при этом в куче становится одним элементом меньше. И тут оказывается, что последний, теперь неиспользуемый, индекс в массиве — A[18] — это то самое место, куда надо поместить только что снятый наибольший элемент, если мы собираемся сортировать массив по возрастанию. Ещё раз снимем элемент — это будет второе максимальное значение из кучи — и поместим его на освободившуюся позицию A[17]. To see why a max binary heap can help sort an array, consider Figure 5-13 that presents the array storage for the heap from Figure 4-17. The largest value in A is found in A[1]. When this max value is dequeued, the underlying array storage is updated to reflect the modified max binary heap containing one less value. More importantly, the index position A[18] is not only unused, it is exactly the index posi‐ tion that should contain the maximum value if the array were sorted. Simply place the dequeued value there. Perform another dequeue, and this value (the second-largest value in the heap) can be placed in index position A[17], which is now unused.

Иллюстрация 5-13. Схема использования двоичной кучи с частичным убыванием для сортировки

Чтобы эта красота заработала, надо разобраться с двумя нюансами: To make this promising approach work, I need to address the following issues:

• Куча в нашей реализации не использует нулевой элемент массива (это сделано для наглядности алгоритма), так что для хранения N элементов понадобится массив размером N+1. • The heap data structure ignores the value in index position 0 to simplify its com‐ putations using an array of size N + 1 to store N values.

• Изначально куча пуста, и мы умеем добавлять в неё только по одному элементу. Возможно, имеет смысл научиться добавлять все N сразу, поскольку мы заранее знаем размер сортируемого массива. • The heap is initially empty, and new values are enqueued one at a time. When starting with N values to sort initially, there needs to be an efficient way to “bulk upload” all values.

Давайте разберёмся, как вычислять индексы в сортируемом массиве. Куча из 18 элементов (которые показаны на иллюстрации 5-13) использовала массив из 19 элементов. Можно было считать, что индексация массива начинаетс с 1, то есть A[1] — это начальный элемент кучи, а A[N] — последний. В примере 5-9 мы переопределили less(i, j) и swap(i, j): когда i и j используются как индексы массива A, из них вычитается по единице. Таким образом в самом алгоритме индексация у нас идёт с единицы, а для массива A она превращается в индексацию с нуля. Наибольшее значение кучи находится в A[0]; вызов swap(1, N) из метода sort() на самом деле меняет местами A[0] и A[N-1]; так же преобразует индексы и less(). Это небольшое изменение позволяет нам не менять метод sink(), а метод swim() пирамидальная сортировка не использует. Let’s fix how index positions are calculated. The original heap with 18 elements (as shown in Figure 5-13) was stored in an array with 19 elements. Any reference to A[i] uses 1-based indexing, meaning that A[1] stored the first value in the heap, and A[N– 1] stored the last. In Listing 5-9, the less(i,j) and swap(i,j) functions all subtract 1 from i and j whenever accessing A[i] or A[j]. This allows 1-based indexing to work with 0-based array storage. The largest value in the heap is now in A[0]. When swap(1, N) appears in the sort() function, it actually swaps the values in A[0] and A[N–1]. With this small adjustment, the sink() method remains the same. Note that Heap Sort never uses swim().

   1 class HeapSort:
   2   def __init__(self, A):
   3     self.A = A
   4     self.N = len(A)
   5 
   6       for k in range(self.N//2, 0, -1):                 # 2
   7         self.sink(k)
   8 
   9   def sort(self):
  10     while self.N > 1:                                   # 3
  11       self.swap(1, self.N)                              # 4
  12       self.N -= 1                                       # 5
  13       self.sink(1)                                      # 6
  14 
  15   def less(self, i, j):
  16     return self.A[i-1] < self.A[j-1]                    # 1
  17 
  18   def swap(self, i, j):
  19     self.A[i-1], self.A[j-1] = self.A[j-1], self.A[i-1]

• Пример 5-9. Частичная реализация пирамидальной сортировки Listing 5-9. Heap Sort implementation

1. Обе функции — less() и swap() — вычитают по единице из индексов, при этом можно считать, что индексация в них идёт с 1. и i // 2 — это индекс радетеля для i-й ячейки. To ensure that i // 2 computes the parent index location for i, both less() and swap() subtract 1 from i and j, as if they were using 1-based indexing.

2. Все элементы, у которых есть хотя бы один потомок, могут нарушать частичный порядок, поэтому их следует «утопить», начиная с последнего из них (в позиции N//2) и заканчивая первым. Наш сортируемый массив A при этом превращается в двоичную кучу с убыванием. Convert array to be sorted, A, into a max binary heap in bottom-up fashion, start‐ ing at N//2, the highest index position that has at least one child.

3. Цикл while заканчивается с опустошением кучи, в которой лежат сортируемые элементы. The while loop continues as long as there are values to sort.

4. Обменяем местами наибольшее и последнее значение в куче. Dequeue maximum value by swapping with last value in heap.

5. Тем самым мы сняли наибольшее значение, теперь нужно уменьшить размер кучи (иначе sink() может работать неправильно). Reduce size of heap by one for upcoming sink() to work.

6. На вершине кучи лежит только что добавленное значение. Его следует «утопить» на место, дабы восстановить частичный порядок. Sink the newly swapped value into its proper location, which reestablishes the heap-ordered property.

Самое важное происходит в начале пирамидальной сортировки: нужно превратить сортируемый массив в двоичную кучу с убыванием. Для этого в конструкторе HeapSort есть цикл for — его работа показана на иллюстрации 5-14. На превращение конкретного массива в кучу ушло всего 23 сравнения и 5 обменов. Цикл обрабатывает все элементы, у которых есть хотя бы один потомок, начиная с позиции N//2 вплоть до вершины кучи. Индекс k перебирает элементы в обратном порядке, и для каждого вызывается sink() — таким образом в куче в конце концов восстановится частичный порядок. Элемент в позиции k отмечен на иллюстрации 5-14 полужирной рамкой. The most important step in Heap Sort is constructing the initial max binary heap from the original array to be sorted. The for loop in HeapSort completes this task, and the result is shown in Figure 5-14, which required only 23 total comparisons and 5 swaps. This for loop constructs a heap from the bottom to the top by starting at index position N//2, the highest index position that has at least one child. In reverse order, the for loop calls sink() on the kth index position to ultimately ensure that all values in the array satisfy the heap-ordered property. These index positions are drawn with a bold border in Figure 5-14.

Часть элементов не нуждается в погружении — у них нет потомков. Половина из оставшихся погружаются не более, чем на один уровень, ещё в два раза меньше — не более, чем на два и т. д., вплоть до вершины, которая может погрузиться максимум на log₂ N уровней, а на каждый уровень погружения тратится не более двух сравнений. Аккуратный математический анализ показывает, что преобразование произвольного массива в кучу неожиданно выполняет не больше 2N сравнений в худшем случае. На иллюстрации 5-14 хорошо видно, как медленно (хотя и неуклонно) увеличивается количество сравнений. Элементы, находящиеся на одном и том же уровне кучи, как и в прошлом примере, отмечены либо серым, либо белым — тогда становится видно, как при обмене они переходят с уровня на уровень. Through a rather unexpected theoretical analysis, the total number of comparisons required to convert an arbitrary array into a max binary heap is no more than 2N in the worst case. The intuition behind this result can be seen in the running total of comparisons in Figure 5-14, which shows a steady, but slow, growth rate. I continue to alternatively shade the index positions within A by the computed level of the max binary heap to show how values are swapped between levels.

Иллюстрация 5-15. Преобразование массива в двоичную кучу с убыванием

Последняя строка — это уже настоящая двоичная куча (на самом деле — в точности такая же, что и на иллюстрации 4-16, только индексирование в ней идёт с нуля, а не с единицы, чтобы использовать все N ячеек). Теперь метод sort() из примера 5-9 может снимать наибольшее значение с кучи и помещать его в её конец (пользуясь уловкой с иллюстрации 5-13). При этом конец постоянно уменьшающейся кучи — это и есть то место, где очередной элемент будет стоять в отсортированном массиве. Размер кучи уменьшает сам sort(), и он же «топит» элемент, некогда стоявший в её конце — так восстанавливается её частичный порядок. В главе 4 мы оценили сложность такой процедуры как O(log N). The final row in Figure 5-14 represents a max binary heap—in fact, the exact same one depicted in Figure 4-16, now offset by one index position to use all N index posi‐ tions. The sort() function in Listing 5-9 now repeatedly swaps the largest value in the heap with the last value in the heap (using the trick hinted at in Figure 5-13), which has the effect of placing that value in exactly its proper location in the final sor‐ ted array. sort() then reduces the size of the heap by one, and sink() properly re- establishes the heap-ordered property with runtime performance of O(log N), as described in Chapter 4.

Сравнение быстродействия алгоритмов со сложностью O(N log N)

Performance Comparison of O(N log N) Algorithms

Итак, у нас есть уже несколько алгоритмов сортировка, сложность которых оценивается как O(N log N). Хорошо бы теперь сравнить их быстродействие друг с другом. В таблице 5-1 приведены результаты экспериментов с различными реализациями сортировки. Размер сортируемого массива указан в первой колонке — он увеличивается в двое с каждой новой строкой, а время работы — в колонках, соответствующих алгоритмам. Можно заметить, что при удвоении входных данных затраченное время растёт чуть больше, чем вдвое — это и есть, грубо говоря, признак того, что алгоритм имеет сложность O(N log N). How does the runtime performance of these different sorting algorithms—all classi‐ fied as O(N log N)—compare with each other? Let’s start with some empirical results, as shown in Table 5-1. Reading the numbers down in a column reports the timing results of an algorithm as the problem size doubles; you can see that each timing value is a bit more than twice as large as its previous value. This relative performance is the signature behavior of an O(N log N) algorithm.

• Таблица 5-1. Время работы различных алгоритмов сортировки в секундах Table 5-1. Runtime performance (in seconds) for different sorting algorithms

Время работы разных алгоритмов на одном и том же наборе данных в каждой строке различно. В главе 2 мы рассматривали понятие мультипликативной постоянной, которая может отличать быстродействие алгоритмов одного класса. Подтверждение этому — последние строки таблицы: начиная с некоторого достаточного размера массива, быстрая сортировка на 15% превосходит сортировку слиянием, а пирамидальная сортировка медленнее её вчетверо. Now in each row, the absolute runtime performance of each algorithm is different. In Chapter 2, I discussed how different behaviors within a classification can vary by a multiplicative constant. This table provides evidence of this observation. Once the problem size is large enough, Quicksort is about 15% faster than Merge Sort, while Heap Sort is more than four times slower.

Две последние колонки таблицы 5-1 — это тест производительности ещё двух алгоритмов. Предпоследняя колонка — это сортировка Тима: в 2002 году Тим Петерс реализовал этот метод сортировки в качестве стандартного для Python. Метод пришёлся по душе многим разработчикам языков программирования, и теперь он используется в большинстве современных языков — в самом Python, в Java, Swift, Rust и т. д., по сути превратясь в стандарт. В таблице рассматривается упрощённый вариант сортировки Тима — по этой причине он слегка уступает в производительности быстрой сортировке — тем не менее он тоже показывает быстродействие O(N log N). Последняя колонка — это работа встроенной в Python функции sort() на типе данных list. Функция sort() также реализует сортировку Тима, но в полном варианте, допускающем массу оптимизаций. К тому же она встроенная, и с такими простыми объектами, как list, работает непосредственно — в результат чего она раз пятнадцать быстрее быстрой сортировки. Саму сортировку Тима имеет смысл рассмотреть отдельно: в ней объединены достоинства сразу двух алгоритмов, что делает её весьма эффективной. The last two columns in Table 5-1 report on the performance of a new sorting algo‐ rithm, Tim Sort, invented by Tim Peters for Python in 2002. This algorithm is quickly becoming the standard sorting algorithm used by major programming languages, such as Java, Python, and Swift. Column “Tim Sort” represents the runtime perfor‐ mance for a simplified Tim Sort implementation, which also exhibits O(N log N) behavior. The final column, labeled “Python Sort,” represents the runtime perfor‐ mance using the built-in sort() method in the list data type. Because it is implemented internally, it will naturally be the most efficient—as you can see, it is around 15 times faster than Quicksort. It is worthwhile to investigate Tim Sort because it mixes together two different sorting algorithms to achieve its outstanding performance.

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

Tim Sort

В сортировке Тима используется подход сортировки вставками с применением функции merge() из сортировки слиянием, но в несколько иных условиях. На повседневных данных получившийся алгоритм обгоняет все уже известные нам алгоритмы сортировки! В частности, сортировка Тима пользуется тем, что некоторые отрезки массива уже отсортированы — это позволяет основательно поднять производительность. Tim Sort combines Insertion Sort and the merge() helper function from Merge Sort in a novel way to provide a fast sorting algorithm that outperforms other sorting algorithms on real-world data. In particular, Tim Sort dynamically takes advantage of long sequences of partially sorted data to deliver truly outstanding results.

Когда сортируешь относительно небольшой отрезок, разница между алгоритмом O(N²) и O(N log N) может оказаться не в пользу последнего! В самом деле, допустим, что точная (с учётом мультипликативных коэффициентов) оценка сложности алгоритма A — это 2 N² действий, а алгоритма B — это 50 N log₂ N действий. Получится, что отрезки длиной менее 190 элементов выгоднее сортировать алгоритмом A, а не алгоритмом B, потому что 2 · 189² = 71442 < 71841 ≈ 50 · 189 · log₂ 189. Как видно из примера 5-10, в сортировке Тима так и происходит. Сначала сортируются вставками все N/size отрезков длиной size, при этом size заранее вычисляется функцией compute_min_run(). Поскольку обычно size — это число в диапазоне от 32 до 64, можно считать его константой, не зависящей от N⁸. В результате мы получаем массив с упорядоченными отрезками, достаточно длинными для того,чтобы на них эффективно работала вспомогательная функция merge() из сортировки слиянием, которая из два отсортированных отрезка сливает в один. As shown in Listing 5-10, Tim Sort first partially sorts N/size sub-arrays of a compu‐ ted size, based on compute_min_run(). size will typically be an integer between 32 and 64, which means we can treat this number as a constant that is independent of N. This stage ensures there are sequences of partially sorted data, which improves the behavior of merge(), the helper function from Merge Sort that merges two sorted sub-arrays into one.

   1 def tim_sort(A):
   2   N = len(A)
   3   if N < 64:                                    # 1
   4     insertion_sort(A, 0, N-1)
   5     return
   6 
   7   size = compute_min_run(N)                     # 2
   8   for lo in range(0, N, size):                  # 3
   9     insertion_sort(A, lo, min(lo+size-1, N-1))
  10 
  11   aux = [None]*N                                # 4
  12   while size < N:
  13     for lo in range(0, N, 2*size):
  14       mid = min(lo + size - 1, N-1)             # 5
  15       hi = min(lo + 2*size - 1, N-1)
  16       merge(A, lo, mid, hi, aux)                # 6
  17     size = 2 * size                             # 7

• Пример 5-10. Базовая реализация сортировки Тима Listing 5-10. Basic Tim Sort implementation

1. Небольшие массивы можно сразу сортировать вставками. Small arrays are sorted instead using Insertion Sort.

2. Вычислим size — размер отрезков, которые мы будем сортировать вставками (обычно это целое в диапазоне от 32 до 64). Compute size—a value typically between 32 and 64—to use for the length of the sub-arrays to be sorted.

3. Отсортируем вставками все отрезки A[lo … lo+size-1] (не забудем, что последний из них может быть короче size). Use Insertion Sort to sort each sub-array A[lo .. lo+size–1], handling special case when final sub-array is smaller.

4. Для сортировки слиянием требуется дополнительная память размером с исходный массив. merge() uses extra storage equal in size to the original array.

5. Вычислим границы отрезков, которые на надо объединить, A[lo … mid] и A[mid+1 … hi]; не забудем о том, что отрезок может оказаться меньшей длины. Compute index positions for two sub-arrays to be merged, A[lo .. mid] and A[mid+1 .. hi]. Take special care with partial sub-arrays.

6. Объединим два отрезка и получим отсортированный A[lo … hi]; в качестве дополнительной памяти используем aux. Merge sub-arrays together to sort A[lo .. hi] using aux for auxiliary storage.

7. На следующем проходе цикла while, после того, как все отрезки длиной size попарно объединены, начнём объединять отрезки вдвое большего размера. Once all sub-arrays of length size are merged with another, prepare for next iter‐ ation through while loop to merge sub-arrays twice as large.

Дополнительный массив aux создаётся единожды, а затем используется в каждом вызове merge(). Полная реализация сортировки Тима намного сложнее, чем наша. В ней сразу определяются отрезки, уже упорядоченные по возрастанию или убыванию, и функция merge() работает не с изолированными элементами, как у нас, а сразу с отрезками. На иллюстрации 5-15 показаны основные преобразования сортируемого массива. Сортировку изучали так долго и так основательно, так часто применяли — тем удивительнее то, что самым эффективным для повседневных задач оказался новый алгоритм, изобретённый уже в нашем веке. The auxiliary storage, aux, is allocated once and used by each invocation of merge(). The actual implementation of Tim Sort has more complicated logic that looks for ascending or strictly descending sub-arrays; it also has a more sophisticated merge function that can merge groups of values “all at once,” where the merge() function I’ve shown operates one value at a time. The simplified implementation whose behav‐ ior is shown in Figure 5-15 contains the essential structure. Given the extensive study of sorting algorithms, it is rather amazing that a new sorting algorithm—discovered this century—has proven to be so effective when working with real-world data sets.

Иллюстрация 5-15. Как меняется массив во время сортировки Тима с начальным размером отрезка 4

size не переводится, это переменная -- FrBrGeorge 2022-10-19 17:34:29

Размер min_run на иллюстрации 5-15 равен всего четырём — так проще рассмотреть работу сортировки Тима. На первом этапе четыре отрезка длиной 4 сортируются вставками (последний отрезок меньше, он содержит только два элемента — 2 и 8). Отсортированные отрезки помечены на иллюстрации белым и серым фоном поочерёдно. Количество таких отрезков — N/size или на один больше, если N не делится на size нацело. Мы помним что сортировка size элементов вставками требует size · (size - 1) / 2 действий, а поскольку самих отрезков у нас N/size штук, время работы первого этапа будет прямо пропорционально N · (size - 1) / 2. Значение size в алгоритме — константа, так что сложность первого этапа можно оценить как O(N). Figure 5-15 demonstrates how Tim Sort works, using a min_run of 4 just to make it easier to visualize. In the first step, four sub-arrays of size 4 are sorted using Insertion Sort; the final two values containing 2 and 8 are contained in a partial sub-array of length 2. These sorted sub-arrays are visualized using alternating bands of shaded and non-shaded regions. There will be N/size sorted sub-arrays (possibly one more, if the length of the original array is not divisible by size). I showed earlier that the run‐ time performance of sorting size values is directly proportional to size × (size – 1)/2—since this occurs N/size times, the total runtime performance is directly pro‐ portional to N × (size – 1)/2. Because size can be considered a constant, this initial phase is classified as O(N).

На втором этапе мы попарно объединяем соседние отрезки. Разбирая работу сортировки слияниями, мы нашли, что общее время работы всех вызовов merge() на одном шаге пропорционально N. После первого прохода цикла while размер отсортированных отрезков удвоился до 8 — это показано на иллюстрации 5-15 соответствующим фоном. В нашем примере за три прохода size вырастает с 4 до 32, а это уже больше, чем N. В общем случае если исходный размер равен size, и вся сортировка выполняется за k проходов цикла while, это цикл заканчивается, когда size·2^k превысит N, то есть когда N/size<2^k. In the second phase, pairs of neighboring runs are merged together. The total accu‐ mulated time for the merge() invocations is proportional to N (as I explained earlier in Merge Sort). After the first pass through the while loop, the size of the sorted sub- arrays has doubled to 8, as you can see by the shaded regions in Figure 5-15. In this example, there are three iterations, as size repeatedly doubles from 4 to 32 (which is greater than N). In general, starting with sorted sub-arrays of size size, the while loop iterates k times until size × 2k > N; rewrite this computation as 2k > N/size.

Чтобы оценить k, возьмём логарифм обеих частей неравенства, и получим k > log₂(N/size). Логарифм частного — это разность логарифмов, так что k > log₂ N - log₂ size. Вспомним, что size — это константа, и получим, что k — это наименьшее целое число, которое не меньше log₂N за вычетом небольшой константы. To find k, take the logarithm of both sides, which reveals that k > log(N/size). Because log(a/b) = log(a) – log(b), I can say that k > log(N) – log(size); since size is a constant, I only need to focus on the fact that k is equal to the smallest integer greater than or equal to log(N) minus a small constant value.

Подытожим: первый этап — с сортировкой вставками — мы оценили как O(N); второй — со слияниями — как O(N · k), где k не превосходит log₂N. Вторая оценка доминирует над первой, так что общая оценка оказывается O(N log N). To summarize, the first phase of Tim Sort—which applies Insertion Sort—can be classified as O(N), and the second phase—which performs repeated merge() requests— is O(k × N), where k is no greater than log(N), resulting in a total overall performance of O(N log N).

Заключение

Summary

Сортировка — одна из основных задач в программировании, изучению которой посвящено немало времени и сил. Большинство встроенных типов данных в Python предусматривают сравнение элементов. Массив таких элементов можно отсортировать напрямую. Более сложные структуры данных могут не иметь функции сравнения, либо алгоритм сравнения по умолчанию может быть неподходящим — например, довольно бессмысленно сравнивать координаты точек лексикографически, то есть сначала сравнивать их абсциссы, а если те равны — то ординаты. В этом случае к каждому элементу можно применить функцию-ключ, которая вернёт значение простого типа, после чего сортировать исходный массив, сравнивая ключи элементов. Например, ключом для точки может быть расстояние от центра координат — тогда сортировка будет по степени удаления точки от центра. Sorting is a fundamental problem in computer science and has been extensively stud‐ ied. An array containing primitive values can be sorted because these values can be compared with each other by default. More complex data types (such as strings or two-dimensional points) can be sorted using custom ordering functions to allow the same sorting algorithms to work.

Здесь у автора две фактические ошибки и одно спорное утверждение в одном предложении, это неремонтопригодно. Мало того, автор в начале пообещал рассказать, как сортировать точки — и не рассказал! -- FrBrGeorge 2022-10-22 22:17:41

Вот что в этой главе мы узнали про сортировку: In this chapter, you learned:

• Простейшие алгоритмы сортировки имеют сложность O(N²), и это делает их совершенно непригодными для упорядочивания больших объемов данных. • How some basic sorting algorithms have O(N2) performance, making them com‐ pletely unsuitable for sorting large data sets.

• Если задачу можно разбить на несколько подзадач, это отличный повод применить рекурсию. • The concept of recursion as a key strategy to solve problems by dividing them into smaller sub-problems.

• Сортировка слиянием и пирамидальная сортировка имеют одинаковую сложность O(N log N), хотя достигается это различными путями. • That Merge Sort and Heap Sort, in different ways, achieve O(N log N) performance.

• В отличие от сортировки слиянием, быстрая сортировка не требует дополнительной памяти и тоже показывает быстродействие O(N log N). • That Quicksort achieves O(N log N) performance without requiring additional storage, as Merge Sort does.

• Во многих языках программирования алгоритм сортировки по умолчанию — это сортировка Тима, некогда изобретённая специально для Python. • Tim Sort, the default sorting algorithm used by Python and an increasing num‐ ber of other programming languages.

Тренировочные задания

Challenge Exercisesa

1. Напишите рекурсивную функцию count(A, t), которая возвращает количество вхождений элемента t в массив A. Рекурсивный вызов должен быть устроен так же, как в find_max(A). Write a recursive method count(A,t) that returns the number of times that the value t appears within A. Your implementation must have a recursive structure, similar to find_max(A).

2. Напишите функцию num_swaps(A), на вход которой подаётся массив размера N, содержащий набор различных целых чисел от 0 до N - 1 в произвольном порядке. Функция должна возвращать наименьшее количество обменов двух элементов массива, которое необходимо для его сортировки. Сам массив сортировать не надо, нужно лишь количество обменов.

   Дополните алгоритм так, чтобы можно было обрабатывать массив из N различных произвольных объектов, используя для этого хеш-таблицу из главы 3. Проверьте, что для сортировки массива с иллюстрации 5-1 требуется пять обменов. You are given an array containing a permutation of the N distinct integers from 0 to N – 1. Determine the fewest number of swaps needed to sort the values in ascending order. Write a function, num_swaps(A), that takes such an array as input and returns an integer value. Note that you do not actually have to sort the array; just determine the number of swaps. Extend the problem to work with an array of N distinct values, using the symbol table from Chapter 3, and confirm that five swaps are needed for Figure 5-1.

3. Сколько всего сравнений требуется для вычисления наибольшего значения в неупорядоченном массиве из N элементов с помощью рекурсивной функции find_max(A)? Функция largest(A) из главы 1 требует больше сравнений или меньше? What is the total number of comparisons needed for the recursive find_max(A) to determine the largest value in an unordered array of N values? Is this total less than (or greater than) the total number of comparisons used by largest(A) pre‐ sented in Chapter 1?

4. Функция merge() в сортировке слиянием в какой-то момент оказывается в ситуации, когда один из объединяемых отрезков закончился, а другой ещё нет. Наша функция продолжает обрабатывать оставшийся отрезок поэлементно. Исправьте это поведение: пускай в этот момент функция сразу заменяет один сегмент массива на другой — так, как мы это делали в aux[lo:hi+1] = A[lo:hi+1]. Проведите серию испытаний и определите, приводит ли это к повышению быстродействия, и если да, то насколько. In the merge() step in Merge Sort, it can happen that one side (left or right) is exhausted. Currently, the merge() function continues to iterate one step at a time. Replace this logic using Python’s ability to copy entire slices of an array, like was done in aux[lo:hi+1] = A[lo:hi+1]. Replace the logic in the first two cases of merge() using slice assignment. Conduct empirical trials to try to measure the performance improvement, if any.

5. Напишите рекурсивную функцию recursive_two(A), которая возвращает два значения — наибольший элемент массива A и второй наибольший его элемент. Сравните её быстродействие с другими вариантами поиска двух наибольших, которые мы видели в главе 1. Также сравните количество задействованных операций «меньше, чем». Complete a recursive implementation, recursive_two(A), that returns the two largest values in A. Compare its runtime performance against the other approaches from Chapter 1; also compare the number of times less-than is invoked.

6. Числа Фибоначчи — это последовательность, которая вычисляется по рекуррентному соотношению F_N=F_N-1+F_N-2, где F₀=0, а F₁=1. Числа Люка задаются примерно так же: L_N=L_N-1+L_N-2, где L₀=2, а L₁=1. Пользуясь стандартным рекурсивным подходом, напишите две функции — fibonacci(n) и lucas(n), которые будут вычислять n-е число Фибоначчи и Люка соответственно. Измерьте время, которое требуется для вычисления F_N и L_N вплоть до N=40. Если ваш компьютер достаточно быстрый, N стоит увеличить для повышения точности, а если слишком медленный — уменьшить, чтобы измерения заканчивались за приемлемое время. Затем напишите функцию fib_with_lucas(n) и вспомогательную к ней, lucas_with_fib(n), пользуясь следующими свойствами этих последовательностей: The Fibonacci series is defined using the recursive formula FN = FN – 1 + FN – 2, with base cases of F0 = 0 and F1 = 1. A related series, Lucas Numbers, is defined as LN = L N – 1 + L N – 2, with base cases of L0 = 2 and L1 = 1. Implement fibonacci(n) and lucas(n) using a standard recursive approach and measure the time it takes to compute both FN and LN up to N = 40; depending on the speed of your com‐ puter, you might have to increase or decrease N to allow the code to terminate. Now implement a new fib_with_lucas(n) method that takes advantage of the following two identities:

   • fib_with_lucas(n): Если поделить n нацело пополам и взять i = n//2, а j = n-i, то F_n = F_i+j = (F_i+L_j)·(F_j+L_i)//2 • fib_with_lucas(n): If you set i = n//2 and j = n-i, then Fi + j = (Fi + Lj) × (Fj + Li)/2

   • lucas_with_fib(n): В свою очередь, L_N = F_N-1 + F_N+1 • lucas_with_fib(n): LN = FN – 1 + FN + 1

   Сравните быстродействие fibonacci() и fib_with_lucas().

Compare timing results of fibonacci() with fib_with_lucas().