Re: Сортировка

From

Evgenij Masherov (2:5020/175.2)

To

Andrey Belyakov

Date

2002-04-30T14:19:08Z

Area

RU.ALGORITHMS

Tue Apr 30 2002 14:21, Andrey Belyakov wrote to Evgenij Masherov:

>>  >>  AB> Да элементарно. На каком-нибудь из шагов потребуется обменять
 >>  >>  AB> строки длиной 5 и 6 символов. Тому, кто сможет это сделать не
 >>  >>  AB> привлекая дополнительных ресурсов можно ставить памятник...
 >>  >>
 >>  >> Попрошу на родине Героя.
 >>  >> Дан массив строк. Т.е. массив указателей на начало строки. Обмен

 AB> местами

 >>  >> значений указателя не зависит от длины указуемых строк.
 >> 
 >>  AB> Подмена задачи не есть ее решение.
 >> 
 >> Пардон, где подмена?
 >> 
 >> MSTR:array[0..N] of string;
 >>  - массив строк?
 >> ИМХО он самый...

 AB> В Паскале? ;)  Нормально массив может лежать где-нибудь на внешнем
 AB> носителе, что, однако, на сам процесс сортировки не должно влиять...

 >> То, что у Вас приведено - никак не массив строк, а строка, в которую
 >> искусственным образом впихнуты несколько строк, разделенных нулевыми
 >> символами. Вот это - подмена задачи.
 >> Массив - совокупность величин одного типа, допускаящая обращение к
 >> каждой из них указанием индекса элемента массива.

 AB> О'key - уговорили. Цель постановки такой задачи не затруднит объяснить?

1. Ну так бюст возводится? :) Ждем-с...

2. Любая прикладная задача с сортировкой, скажем, фамилий или названий книг,
скорее будет предполагать выделение массива типа строка, а не создание длинной
строки с разделителями внутри...

3. Впрочем, возьмем Вашу постановку. Дана длинная строка на внешнем носителе.
С разделителями внутри. Необходимо ея отсортировать. Ну и почему здесь
неприменима разделяющая сортировка? Внешняя память нуждается в экономии?
Первый проход: из одного входного файла делаем два, поочередно выбрасывая в
1-й и 2-й последовательные строки.
Последующие проходы:
Сливаем эти файлы обычным образом (кстати, лексикографическое сравнение
получаеися само собой...), поочередно выбрасывая в два других. И так до
полного удовлетворения. O(NlnN)
Весьма практичная постановка.

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)