Главная страница


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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Сортировка   Georgy Saygin   28 Apr 2001 18:56:31 
 Re: Сортировка   Andrey Belyakov   29 Apr 2002 18:33:46 
 Сортировка   Stanislav Shwartsman   29 Apr 2002 18:15:22 
 Re: Сортировка   Andrey Belyakov   29 Apr 2002 20:55:39 
 Сортировка   Stanislav Shwartsman   29 Apr 2002 20:59:56 
 Re: Сортировка   Andrey Belyakov   29 Apr 2002 22:54:54 
 Re: Сортировка   Sergiy Kanilo   30 Apr 2002 00:19:14 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 00:56:05 
 Re: Сортировка   Sergiy Kanilo   30 Apr 2002 01:49:26 
 Re: Сортировка   Andrey Tarasevich   30 Apr 2002 02:42:26 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 13:30:13 
 Re: Сортировка   Evgenij Masherov   30 Apr 2002 08:50:15 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 13:36:23 
 Re: Сортировка   Evgenij Masherov   30 Apr 2002 12:55:47 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 14:25:35 
 Re: Сортировка   Evgenij Masherov   30 Apr 2002 14:19:47 
 Сортировка   Alexander Orlov   30 Apr 2002 16:30:43 
 Re: Сортировка   Alexander Krotoff   30 Apr 2002 18:23:26 
 Сортировка   Stanislav Shwartsman   30 Apr 2002 18:25:40 
 Сортировка   Alex Kardaniuk   30 Apr 2002 17:14:25 
 Сортировка   Alexander Orlov   30 Apr 2002 20:04:14 
 Сортировка   Evgenij Masherov   30 Apr 2002 21:21:48 
 Соpтиpовка   Stanislav Aranovsky   01 May 2002 00:19:12 
 Re: Соpтиpовка   Sergiy Kanilo   01 May 2002 02:46:33 
 Соpтиpовка   Evgenij Masherov   01 May 2002 11:26:34 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 16:24:32 
 Re: Сортировка   Evgenij Masherov   30 Apr 2002 21:19:15 
 Re: Сортировка   Andrey Belyakov   01 May 2002 01:14:33 
 Re: Сортировка   Andrey Tarasevich   01 May 2002 02:01:42 
 Сортировка   Alex Kardaniuk   30 Apr 2002 17:16:20 
 Сортировка   Evgenij Masherov   30 Apr 2002 20:35:31 
 Re: Сортировка   Sergiy Kanilo   30 Apr 2002 19:26:57 
 Re: Сортировка   Andrew Ezhguroff   01 May 2002 03:08:56 
 Re: Сортировка   Andrey Belyakov   01 May 2002 12:46:40 
 Re: Сортировка   Andrey Tarasevich   01 May 2002 21:18:18 
 Re: Сортировка   Andrey Belyakov   02 May 2002 02:28:08 
 Сортировка   Andrey Dashkovsky   01 May 2002 13:19:47 
 Re: Сортировка   Andrey Tarasevich   30 Apr 2002 02:18:04 
 Re: Сортировка   Evgenij Masherov   29 Apr 2002 19:17:50 
 Re: Сортировка   Andrey Belyakov   29 Apr 2002 20:55:40 
 Re: Сортировка   Evgenij Masherov   29 Apr 2002 20:29:58 
 Re: Сортировка   Andrey Belyakov   29 Apr 2002 22:03:31 
 Re: Сортировка   Evgenij Masherov   29 Apr 2002 22:12:23 
 Re: Сортировка   Andrey Tarasevich   30 Apr 2002 02:28:13 
 Сортировка   Comoderator Of Ru Algorithms   01 May 2002 12:57:43 
 Re: Сортировка   Alexander Krotoff   30 Apr 2002 00:23:24 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 01:00:10 
 Re: Сортировка   Andrey Tarasevich   30 Apr 2002 02:22:08 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 13:17:51 
 Сортировка   Evgeniy Jirnov   05 May 2002 11:35:40 
 Re: Сортировка   Andrey Belyakov   06 May 2002 15:53:34 
 Сортировка   Comoderator Of Ru Algorithms   07 May 2002 16:36:01 
 Смежные строки (Re: Сортировка)   Valentin Davydov   06 May 2002 17:19:48 
 Смежные строки (Re: Сортировка)   Comoderator Of Ru Algorithms   07 May 2002 16:38:04 
 Сортировка   Comoderator Of Ru Algorithms   06 May 2002 18:32:06 
 Re: Сортировка   Andrew Ezhguroff   30 Apr 2002 03:04:49 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 13:19:54 
 Сортировка   Stanislav Shwartsman   30 Apr 2002 18:18:11 
 Re: Сортировка   Andrew Ezhguroff   01 May 2002 03:08:55 
 Re: Сортировка   Evgenij Masherov   30 Apr 2002 08:51:43 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 13:21:58 
 Re: Сортировка   Evgenij Masherov   30 Apr 2002 12:50:56 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 14:21:30 
 Re: Сортировка   Evgenij Masherov   30 Apr 2002 14:19:08 
 Re: Сортировка   Andrey Belyakov   30 Apr 2002 16:20:26 
 Re: Сортировка   Andrew Ezhguroff   01 May 2002 03:08:56 
 Re^2: Соpтиpовка   Vlad Bespalov   01 May 2002 13:49:10 
 Re: Соpтиpовка   Andrey Belyakov   01 May 2002 16:18:00 
 Re: Соpтиpовка   Evgenij Masherov   01 May 2002 16:55:32 
 Соpтиpовка   Comoderator Of Ru Algorithms   02 May 2002 00:42:04 
 Re: Соpтиpовка   Evgenij Masherov   01 May 2002 16:56:57 
 Re: Соpтиpовка   Andrey Tarasevich   01 May 2002 21:24:27 
 Re: Соpтиpовка   Andrey Belyakov   02 May 2002 02:30:11 
 Re: Соpтиpовка   Alexey V. Goloborchy   02 May 2002 01:23:33 
 Re: Соpтиpовка   Andrey Belyakov   02 May 2002 02:24:04 
 Re: Соpтиpовка   Andrey Tarasevich   02 May 2002 03:10:18 
 Re: Соpтиpовка   Andrey Belyakov   02 May 2002 15:29:29 
 Re: Соpтиpовка   Andrew Ezhguroff   02 May 2002 18:08:13 
 Re: Соpтиpовка   Andrey Belyakov   02 May 2002 19:31:52 
 Re: Соpтиpовка   Andrew Ezhguroff   02 May 2002 22:49:55 
 Соpтиpовка   Comoderator Of Ru Algorithms   03 May 2002 12:36:26 
 Re: Соpтиpовка   Evgenij Masherov   02 May 2002 08:09:51 
 Соpтиpовка   Alex Cvetkov   02 May 2002 10:53:21 
 Re: Сортировка   Andrew Ezhguroff   01 May 2002 03:08:55 
 Re: Сортировка   Andrey Belyakov   01 May 2002 12:44:37 
 Re: Сортировка   Andrew Ezhguroff   02 May 2002 04:30:05 
 Re: Сортировка   Andrey Belyakov   02 May 2002 15:09:08 
 Re: Сортировка   Andrew Ezhguroff   02 May 2002 17:11:10 
 Re: Сортировка   Andrey Belyakov   02 May 2002 18:44:56 
 Re: Сортировка   Andrew Ezhguroff   02 May 2002 22:49:56 
 Сортировка   Comoderator Of Ru Algorithms   03 May 2002 12:37:01 
 Сортировка   Stanislav Shwartsman   30 Apr 2002 08:25:00 
 Сортировка   Nickita A Startcev   01 May 2002 22:32:20 
 Сортировка   Nickita A Startcev   30 Apr 2002 18:39:42 
 Соpтиpовка   Sergey Naidenov   02 Apr 2002 22:09:53 
 Соpтиpовка   Maxim Lanovoy   06 May 2002 16:34:26 
Архивное /ru.algorithms/330033fcf537.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional