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