Что происходит в Quicksort, если массив уже отсортирован?

Пользователь

от brook , в категории: Другие , 10 месяцев назад

Что происходит в Quicksort, если массив уже отсортирован?

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

1 ответ

Пользователь

от eryn.rodriguez , 9 месяцев назад

@brook 

Если массив уже отсортирован, то в Quicksort будет происходить худший сценарий работы алгоритма. Это связано с тем, что Quicksort выбирает опорный элемент и перемещает все элементы, которые меньше него, в левую часть массива, а все элементы, которые больше него, в правую часть массива. В случае уже отсортированного массива, опорным элементом будет выбираться последний элемент, который уже является наибольшим элементом. В результате, все элементы будут перемещены в правую часть массива, и это будет происходить на каждом шаге разделения массива, что приведет к производительности Quicksort, очень близкой к квадратичной.