Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 10

Какое количество перестановок требуется для сортировки n элементов с использованием сортировки выбора, в худшем случае?
(А) (П)
(В) (n log n)
(С) (п ^ 2)
(D) (n ^ 2 log n)
(A) Тета (n)
(B) Тета (nLogn)
(С) тета (n * n)
(D) Тета (n * nLogn)

Ответ: (А)
Объяснение: Здесь представлен алгоритм сортировки по выбору для сортировки по возрастанию.

   1. Find the minimum value in the list
   2. Swap it with the value in the first position
   3. Repeat the steps above for the remainder of the list (starting at
      the second position and advancing each time)

Как видно из алгоритма, сортировка выбора выполняет своп только после нахождения соответствующей позиции текущего выбранного элемента. Таким образом, в сортировке выбора выполняется O (n) перестановок.
Поскольку подкачки требуют записи в массив, сортировка выбора предпочтительнее, если запись в память значительно дороже, чем чтение. Это обычно тот случай, если предметы огромные, а ключи маленькие. Другим примером, где время записи имеет решающее значение, является массив, хранящийся в EEPROM или Flash. Нет другого алгоритма с меньшим перемещением данных.

Ссылки:
http://en.wikipedia.org/wiki/Selection_sort
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2009 | Вопрос 10

0.00 (0%) 0 votes