В чем разница между алгоритмом онлайн-сортировки и алгоритмом внешней сортировки?
В чем разница между алгоритмом онлайн-сортировки и алгоритмом внешней сортировки? Они одинаковые или разные?
1 ответ
Алгоритм онлайн-сортировки будет работать, если элементы для сортировки предоставляются по одному с пониманием того, что алгоритм должен сохранять последовательность отсортированной, так как в нее добавляется все больше и больше элементов. Алгоритмы, которые предполагают, что весь вход будет заданные заранее, такие как heapsort, не будут работать в качестве онлайн-алгоритмов, поскольку они предполагают, что они знают все элементы заранее. С другой стороны, такой алгоритм, как сортировка вставками, работает в режиме онлайн, поскольку он работает только слева направо и не нуждается в просмотре всего массива, пока работает, пока не попытается обработать самый последний элемент.
Внешний алгоритм сортировки - это алгоритм, в котором целью является сортировка данных, обычно предоставляемых заранее, которые настолько велики, что не могут поместиться в основную память. Хотя внешние алгоритмы сортировки обычно не сохраняют все данные, подлежащие сортировке, в памяти сразу, они обычно предполагают, что могут загружать любые данные, которые им нужны, в память в любое время.
Хороший способ подумать о разнице заключается в том, что в алгоритме онлайн-сортировки следует исходить из того, что вы пытаетесь отсортировать последовательность, которая генерируется динамически, - не все данные существуют до начала сортировки. В алгоритме внешней сортировки все данные уже существуют, но их так много, что вы не можете сразу загрузить все в память.
Надеюсь это поможет!