|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 01 May 2002 16:55:32
To : Andrey Belyakov
Subject : Re: Соpтиpовка
--------------------------------------------------------------------------------
>> Как я понимаю, задача "должна" звyчать как:
>> "отсоpтиpовать непpеpывнyю область памяти, являющyюся
>> последовательностью NTS, завеpшающyюся символом \0, без
>> динамического выделения памяти".
AB> Hаконец-то хоть один удосужился сформулировать задачу.
AB> Думаю, что пониматься она должна именно так. В противном
AB> случае давать ее просто бессмысленно.
AB> Андрей.
AB> P.S. Совсем без дополнительной памяти не обойдется, но можно
AB> наложить достаточно жесткие ограничения. Hапример, ограничив
AB> фиксированный буфер размером < max(длинны строк).
Позвольте заметить, что разрешение спора возможно либо "юридически", либо
практически.
В первом случае следует определить, что есть "массив" и "строка", либо объявив
массивом и строкой то, что понимается под этим в каком-то языке
программирования (недостаток этого в том, что мы привязываемся к языковой
конкретике, достоинство же - что исключены почти всякие споры), либо дав
определения и признав их сообществом.
Для случая 1а я прав - если в качестве языка программирования принимать С или
же Паскаль (если любой иной, по выбору - то также легко построить пример
сортировки не пузырьком).
Для случая 1б предлагаю в качестве определния массива "совокупность элементов
одного типа, позволяющую осуществить доступ к произвольному элементу за О(1)
операций", а в качестве определения строки "совокупность символьных (байтовых
или иных) элементов, возможно переменной длины, позволяющую осуществлять
операции сравнения в лексикографическом порядке, конкатенации и выделения
подстроки". В этом случае также, очевидно, пузырек не только не единственынй,
но и не оптимальный вариант.
Во втором же, практически ориентированном случае, "массивом строк" будет то,
что в конкретной практической задаче позволяет хранить и использовать некую
совокупность текстовых данных, которую и требуется отсортировать. Очевидно, в
случае, когда в нашем распоряжении имеется дополнительная память (на операции
обмена ли или же для хранения указателей), пузырек непрактичен. Поэтому
рассмотрим случай крайнего дефицита памяти. Понятно, что сие возможно лишь при
том, что исходные данные столь велики, что невместимы в оперативную память, и
хранятся во внешней. Hо тогда оптимальной сортировкой никак не может быть
пузырек, квадратичный по природе, а лишь требующие O(NlnN) методы, если только
они реализуемы. И они реализуемы. Скажем, для исходных данных, представленных
в виде последовательности символов с разделительными символами меж ними, можно
построить распределяющую сортировку или сортировку слиянием, более
эффективную, нежели пузырек, по времени, и не требующую дополнительной памяти.
Следовательно, прихожу к выводу, что пузырек не удовлетворяет условиям
первоначально поставленной задачи и может быть применим в редких, практически
незначимых случаях.
Примите уверения в совершеннейшем почтении
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
