Что происходит в Quicksort, если массив уже отсортирован?
2 ответа
@brook
Если массив уже отсортирован, то в Quicksort будет происходить худший сценарий работы алгоритма. Это связано с тем, что Quicksort выбирает опорный элемент и перемещает все элементы, которые меньше него, в левую часть массива, а все элементы, которые больше него, в правую часть массива. В случае уже отсортированного массива, опорным элементом будет выбираться последний элемент, который уже является наибольшим элементом. В результате, все элементы будут перемещены в правую часть массива, и это будет происходить на каждом шаге разделения массива, что приведет к производительности Quicksort, очень близкой к квадратичной.
@brook
Точно, при отсортированном массиве Quicksort будет работать наихудшим образом и иметь квадратичную временную сложность (O(n^2)), так как на каждом шаге опорный элемент будет оказываться крайним среди других элементов. Это происходит потому, что в таком случае часто опорный элемент делит массив на наиболее неравные части, и алгоритму придется делать O(n) разбиений вместо ожидаемого в среднем O(log n).