1. Алгоритмы сортировки для начинающих
Алгоритмы сортировки для начинающих
Русский
Elementary
Данный тест не только может помочь новичкам понять 4 базовые сортировки данных в программировании, но и позволит профессионалам своего дела проверить свои знания.
Description
Программирование, Алгоритмы
Tags
30
Questions
5 min
Per question
3:04
Average time
3.0
Contest Score
6
Participants
Start Quiz
7 comments
Small Lizard
Вопрос №3: сортировка выбором может быть как устойчивой, так и неустойчивой
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Выбором#Python
Small Lizard
Вопрос №5. Обмен элементов - a[i],a[min_ind]=a[min_ind],a[i]. Правильный ответ (то, о чём говорится в объяснении) - просто присвоение переменным min_el и min_ind новых значений
Small Lizard
Вопрос №11. В границах цикла тоже ошибка. Рассмотрим первую итерацию внешнего цикла: i=0. Тогда N-i=N, и j будет идти по диапазону [0..N). Последняя его итерация - j=N-1. Условие if'а: a[j]>a[j+1]. a[j+1]=a[N-1+1]=a[N] - выход за границу массива.
Small Lizard
Реализация сортировки слиянием на видео работает за O(n^2) из-за того, что list.pop(0) работает за длину списка: https://wiki.python.org/moin/TimeComplexity
Small Lizard
Вопрос №22. Ответ "неправильное условие деления на 2" неправильно сформулирован. Правильнее будет просто "неправильное деление на 2"
Small Lizard
Мне непонятен смысл теста - посмотреть на видео и тут же ответить, что было написано на видео
Small Lizard
Вопрос №20 о сложности сортировки слиянием.
Ответ: O(nlogn) + доп.память O(n).
Объяснение: Доп. память из-за рекурсии.
Это неправильное объяснение. Например, быстрая сортировка (quicksort) тоже рекурсивная, но не требует дополнительной памяти (разве что O(logn) из-за стека вызовов, но не O(n)). Сортировка слиянием требует дополнительно O(n) памяти для слияния двух половин массива
Take the quiz to leave a comment