Алгоритмы сортировки для начинающих
Русский
Elementary
Данный тест не только может помочь новичкам понять 4 базовые сортировки данных в программировании, но и позволит профессионалам своего дела проверить свои знания.
Description
Tags
30
Questions
5 min
Per question
3:04
Average time
3.0
Contest Score
6
Participants
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Выбором#Python
Ответ: O(nlogn) + доп.память O(n).
Объяснение: Доп. память из-за рекурсии.
Это неправильное объяснение. Например, быстрая сортировка (quicksort) тоже рекурсивная, но не требует дополнительной памяти (разве что O(logn) из-за стека вызовов, но не O(n)). Сортировка слиянием требует дополнительно O(n) памяти для слияния двух половин массива