Мне нужно выполнить задание, в котором я должен реализовать сортировку по пузырькам и сортировку слиянием в Python.Я не могу опубликовать код, потому что это назначение.Но оба они тривиальны, и я знаю, как это сделать, и я сделал их очень быстро.
В последней части мы просим нас рассчитать оба, якобы, чтобы показать, что на больших наборах данных сортировка по пузырькам медленнее, чем сортировка слиянием.Но вот в чем дело: пузырьковая сортировка всегда быстрее, независимо от того, что я делаю.Это не имеет никакого смысла.Теоретически, пузырьковая сортировка должна быть O(n^2), а сортировка слиянием - O(n log n).Теперь это Python, поэтому рекурсия очень ограничена, и наборы данных не могут быть очень большими.После всего лишь нескольких тысяч элементов Python просто сдается из-за ограничений рекурсии.Повышение максимальной глубины рекурсии приводит к краху Python.
Я на Python 3.7.Я попытался с версией пузырьковой сортировки, где элементы переключаются полностью вниз по списку и установлен флаг, если какой-либо элемент переключен, и я также пробовал версию пузырчатой сортировки, где функция вызывается снова, как только любойпроисходит переключение.Вторая версия просто не работает: Python не может справиться с такой рекурсией.Это не схема.
Тем не менее, как это возможно, что сортировка пузырьков происходит быстрее?Для сортировки слиянием я создаю список нужного размера для слияния и заполняю их индексами.Я не увеличиваю их с помощью append, что может быть медленнее.
Мое главное предположение, что Python, ограничивая размер набора данных, не может позволить мне достичь размера данных, где сложность становится значительной,Но все же ...
Это вывод, который я получил после помещения инструкции sleep при каждом вызове функции bubble и при каждом вызове функции merge, но не функции split.Так что это дает метод слияния несправедливое преимущество.Сортировка 2000 случайных чисел:
Time for bubble sort: 0.012022733688354492.
Time for merge sort: 23.143869876861572.
On a log scale: -1.919996772700693 and 1.3644359788874267.
Я сбит с толку.
Тем не менее, когда я перезапускаю интерпретатор, с первой попытки они, кажется, занимают примерно одно и то же время.Только во второй раз пузырьковая сортировка становится намного быстрее.(И нет, я не использую памятку.) Но, может, Python как-то кэширует результаты?В конце концов, сортировка - это чистая функция ...