2001-gre-vs-practice.pdf/Q52

Ссылки сюда (1) →

Какой из следующих алгоритмов сортировки имеет время выполнения, НАИМЕНЕЕ зависящее от первоначального порядка ввода?

Ответы

• Сортировка вставками
• Быстрая сортировка
• Правильный ответ: Сортировка слиянием
• Сортировка выбором
• Сортировка Шелла

Объяснение

Исходники — вопрос 52 на 39 странице книги «2001-gre-vs-practice.pdf»

Сортировка вставками

В лучшем случае, когда данные уже отсортированы, имеет время выполнения . В худшем случае (когда данные отсортированы в обратном порядке) — .

Быстрая сортировка

В среднем случае имеет время выполнения , но в худшем случае (если выбор опорного элемента неудачен) — . Однако, в лучшем случае также может быть .

Сортировка слиянием

Всегда имеет время выполнения , независимо от первоначального порядка данных.

Сортировка выбором

Всегда имеет время выполнения , независимо от порядка данных.

Сортировка Шелла

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

Таким образом, алгоритм с наименьшим временем выполнения, зависимым от первоначального порядка ввода, — это сортировка слиянием, так как его время выполнения всегда составляет .

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.