Лучший случай изменения быстрой сортировки

Question

Допустим, у вас такой реализации быстрой сортировки, который, вероятно, немного отличается от стандартного:

qsort(list): 
if list is of length 1 or lower - 
    return list 
else - 
    choose a random pivot 
    smaller - get all elements that are smaller than the pivot 
    equal - get all elements that are equal to the pivot, including the pivot itself 
    greater - get all elements that are greater than the pivot 
    return qsort(smaller) + equal + qsort(greater) 

не самый лучший вариант развития событий для этой функции быть бы когда функция получает список, в котором все элементы одинаковы, и в этом случае наилучшая временная сложность будет равна O(n), что лучше, чем наилучшая временная сложность стандартной версии быстрого сортировки, которая равна O(n log n)?

Аргументации для этого является то, что функция создает только те разделы, один раз, поскольку меньшие и большие списки будут пустыми (как все элементы одинаковы), и это положит конец рекурсии, так как qsort(smaller) и qsort(greater) бы просто верните пустые списки.

Верно ли это?

Answer 1

Да, в случае, если вы описываете сложность времени, будет O(n).

Однако пространство также будет O(n) в виде нового списка equal. Это хуже того, что qsort, который сортируется на месте, имеет значение O(1) (постоянное) пространство.

Временная сложность qsort O(n lg(n)) - это средний случай, который рассчитывается с учетом статистически случайных данных. Ваша адаптация поможет производительности в краевом случае, что все значения равны, что очень маловероятно (хотя вы могли бы иметь предварительное знание о данных, что делает его более вероятным).

Если вы рассматривали возможность использования этого алгоритма в отличие от стандартного qsort, я бы порекомендовал его. Поскольку использование дополнительных списков добавляет накладные расходы при добавлении элементов и конкатенации (где эти накладные расходы зависят от реализации списка). Эти накладные расходы отсутствуют в qsort, поскольку они сортируются на месте.