Рубрики

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 23

Наихудшее время выполнения сортировки вставкой, сортировки слиянием и быстрой сортировки, соответственно:

(A) Θ (n log n), Θ (n log n) и Θ (n 2 )

(B) Θ (n 2 ), Θ (n 2 ) и Θ (n Log n)

(C) Θ (n 2 ), Θ (n log n) и Θ (n log n)

(D) Θ (n 2 ), Θ (n log n) и Θ (n 2 )

Ответ: (D)
Объяснение:

  • Сортировка вставки принимает Θ (n 2 ) в худшем случае, так как нам нужно запустить два цикла. Внешний цикл необходим, чтобы один за другим выбрать элемент для вставки в правильное положение. Внутренний цикл используется для двух вещей: для поиска позиции вставляемого элемента и перемещения всех отсортированных больших элементов на одну позицию вперед. Поэтому рекурсивная формула наихудшего случая — это T (n) = T (n-1) + Θ (n).
  • Сортировка слиянием занимает Θ (n Log n) времени во всех случаях. Мы всегда делим массив на две половины, сортируем две половины и объединяем их. Рекурсивная формула T (n) = 2T (n / 2) + Θ (n).
  • QuickSort принимает Θ (n 2 ) в худшем случае. В QuickSort мы берем элемент как pivot и разбиваем массив вокруг него. В худшем случае выбранный элемент всегда является угловым элементом, и рекурсивная формула становится T (n) = T (n-1) + Θ (n). Пример сценария, когда происходит худший случай, массивы сортируются, и наш код всегда выбирает угловой элемент как сводный.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 23

0.00 (0%) 0 votes