Дерево решений быстрого сортировки

Question

Я только что потратил пару часов, пытаясь представить дерево решений для алгоритма быстрой сортировки по набору элементов (и я также искал в Интернете). Я хотел бы знать, что представляет собой каждый узел. Это сравнение между двумя наборами (в результате вызова Раздел)? или просто сравнение между двумя элементами набора? Надеюсь, что мой вопрос достаточно ясен.

Answer 1

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