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

From

Andrey Tarasevich ()

To

Andrey Belyakov

Date

2002-05-02T03:10:18Z

Area

RU.ALGORITHMS

From: Andrey Tarasevich <atarasevich@telocity.com>

Andrey Belyakov wrote:
> ...
> Массив можно также рассматривать, как набор элементов, доступ к
> которым обеспечивается нумерацией элементов.

Доступ на основе нумерации элементов можно организовать для любой
последовательно доступаемой структуры данных. Тем не менне это не делает
такую структуру данных массивом.

> В случае строк произвольной длины это определение более рационально.
> Однотипность элементов и доступ за O(1) операций не являются обязательными.

Неправильно. Требование произвольного доступа (random access) является
фундаментальным свойством структуры данных "массив" и заключается в
обеспечении индексного доступа за время O(1). Это _обязательное_
требование.

> > Ответ:
> > Да, такое определение соответствует условиям задачи. Причем, подобный
> > выбор параметра строки в качестве элемента рабочего массива, позволяет
> > осуществлять операцию перестановки любых двух элементов массива без
> > дополнительных затрат времени и ресурсов; следовательно, является
> > оптимальным.
> Уже нет. Заменена задача сортировки массива _произвольных_ строк т.е.
> сущностей по определению различных, 
> на сортировку массива указателей
> на строки(символы) т.е. сущностей одинаковых.

Нонсенс. Изменение содержимого строки никак не меняет строку, как
сущность. Задача сортировки массива произвольных строк является задачей
сорировки массива одинаковых сущностей. Задачи сортировки произвольно
различающихся сущностей не существует и существовать не может.

И еще раз: строка в С существует только на уровне интерпретации.
Указатель на символ в С, при соблюдении некоторых требований, является
строкой.

> > 5. Произвольные строки можно отсортировать только пузырьком?
> > Ответ: Нет, не только.
> Напишите это. Без построения дополнительных массивов указателей на
> строки. Пусть даже не будет ограничения на буфер для одной строки.

Я уже привел пример сортировки массива std::string-ов.

Best regards,
Андрей.
--- ifmail v.2.15dev5
 * Origin: good enough (2:5020/400)