Смежные строки (Re: Сортировка)

From

Valentin Davydov ()

To

Evgeniy Jirnov

Date

2002-05-06T17:19:48Z

Area

RU.ALGORITHMS

From: Valentin Davydov <val@sqdp.trc-net.co.jp>

>   From: Evgeniy Jirnov <Evgeniy.Jirnov@p13.f1230.n5030.z2.fidonet.org>
>   Date: Sun, 05 May 2002 10:35:40 +0400
> AB> В Пузырьке они смежные.  Смежные можно объменять местами без
> AB> дополнительных затрат.
>
>Да? Ну тогда "обменяй" пожалуйста эти две строчки,
>без дополнительных затрат ресурсов:
>evgeniy\0jirnov\0

Пусть элементарная операция - это копирование одного байта. Тогда получается:

evgeniy0jirnov0
evgeniyejirnov0
jvgeniyejirnov0
jvgeniyevirnov0
jigeniyevirnov0
jigeniyevgrnov0
jireniyevgrnov0
jireniyevgenov0
jirnniyevgenov0
jirnoiyevgenov0
jirnoiyevgeniv0
jirnovyevgeniv0
jirnovyevgeniy0
jirnov0evgeniy0,

то есть всего 13 шагов. Правда, я чуток съоптимизировал, воспользовавшись
тем, что строчка "jirnniyevgenov0" переходит сама в себя при переносе буквы
'n' с пятого места на двенадцатое. В общем же случае количество потребных
шагов равно суммарной длине обеих строк за вычетом единицы (последний ноль
в перестановках не участвует).

Вал. Дав.
--- ifmail v.2.15dev5
 * Origin: St. Petersburg State University (2:5020/400)