Алгоритмы сортировки для начинающих
Русский
Початковий
Данный тест не только может помочь новичкам понять 4 базовые сортировки данных в программировании, но и позволит профессионалам своего дела проверить свои знания.
Опис
Теги
30
Запитань
5 хв
На запитання
3:04
Середній час
3,0
Результат у конкурсі
6
Учасників
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Выбором#Python
Ответ: O(nlogn) + доп.память O(n).
Объяснение: Доп. память из-за рекурсии.
Это неправильное объяснение. Например, быстрая сортировка (quicksort) тоже рекурсивная, но не требует дополнительной памяти (разве что O(logn) из-за стека вызовов, но не O(n)). Сортировка слиянием требует дополнительно O(n) памяти для слияния двух половин массива