|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 30 Apr 2002 14:19:08
To : Andrey Belyakov
Subject : Re: Сортировка
--------------------------------------------------------------------------------
>> >> AB> Да элементарно. Hа каком-нибудь из шагов потребуется обменять
>> >> AB> строки длиной 5 и 6 символов. Тому, кто сможет это сделать не
>> >> AB> привлекая дополнительных ресурсов можно ставить памятник...
>> >>
>> >> Попрошу на родине Героя.
>> >> Дан массив строк. Т.е. массив указателей на начало строки. Обмен
AB> местами
>> >> значений указателя не зависит от длины указуемых строк.
>>
>> AB> Подмена задачи не есть ее решение.
>>
>> Пардон, где подмена?
>>
>> MSTR:array[0..N] of string;
>> - массив строк?
>> ИМХО он самый...
AB> В Паскале? ;) Hормально массив может лежать где-нибудь на внешнем
AB> носителе, что, однако, на сам процесс сортировки не должно влиять...
>> То, что у Вас приведено - никак не массив строк, а строка, в которую
>> искусственным образом впихнуты несколько строк, разделенных нулевыми
>> символами. Вот это - подмена задачи.
>> Массив - совокупность величин одного типа, допускаящая обращение к
>> каждой из них указанием индекса элемента массива.
AB> О'key - уговорили. Цель постановки такой задачи не затруднит объяснить?
1. Hу так бюст возводится? :) Ждем-с...
2. Любая прикладная задача с сортировкой, скажем, фамилий или названий книг,
скорее будет предполагать выделение массива типа строка, а не создание длинной
строки с разделителями внутри...
3. Впрочем, возьмем Вашу постановку. Дана длинная строка на внешнем носителе.
С разделителями внутри. Hеобходимо ея отсортировать. Hу и почему здесь
неприменима разделяющая сортировка? Внешняя память нуждается в экономии?
Первый проход: из одного входного файла делаем два, поочередно выбрасывая в
1-й и 2-й последовательные строки.
Последующие проходы:
Сливаем эти файлы обычным образом (кстати, лексикографическое сравнение
получаеися само собой...), поочередно выбрасывая в два других. И так до
полного удовлетворения. O(NlnN)
Весьма практичная постановка.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
