|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Cvetkov 2:5030/1334 02 May 2002 10:53:21
To : Andrey Belyakov
Subject : Соpтиpовка
--------------------------------------------------------------------------------
02 Май 02 02:24, Andrey Belyakov писал(ла) Alexey V. Goloborchy:
>> 5. Произвольные строки можно отсортировать только пузырьком?
>> Ответ: Hет, не только.
AB> Hапишите это. Без построения дополнительных массивов указателей на
AB> строки. Пусть даже не будет ограничения на буфер для одной строки.
Радость моя, только чтобы ты успокоился. Привожу псевдокод (перевести в
программу на си не составит труда даже для тебя) алгоритма меняюжего местами две
строки в упакованном виде. Как понимаю, именно эта задача вызвала у тебя
непреодалимые трудности.
Hаити A1 - адрес начала первой строки, B1 - адрес конеца первой строки,
A2, B2 - аналогичные параметры второй строки.
L1 = B1-A1 - длинна первой строки. Аналогично L2 = B2 - B1
Условимся, не ограничивая общности, что первая строка находиться по меньшим
адресам в памяти.
Также следует отметить что из условия задачи строки не пересекаються.
Hаидем разность dL = L2 - L1
Рассмотрим случай когда она положительна (случай когда она отрицательна в
некотором смысле аналогичен, если разность нулевая задача сводиться к
тривиальной).
Исходная упакованная строка примет вид PQRUST
где P - начало упакованной строки,
Q - первая строка
R - часть исходной упакованной строки между первой и втрой строками
U - начало второй строки длинны dL
S - конец второй строки длинны L1
T - остаток исходной упакованной строки
Итак произведем dL шагов следующего алгоритма.
Циклически сдвигаем подстроку с началом в A1 и концом в A2 + dL, таким образом
что первый символ подстроки становиться последним, остальные символы подстроки
уменьшают свой адрес на единицу.
В результате исходная упакованная строка примет вид PUQRST
где PQRUST - теже самые подстроки.
Теперь нам осталось заменить подстроки U и S местами.
Сделать это нетрудно, так как они имеют одинаковую длинну.
Итак задача обмена местами двух подстрок строки завершена.
Этот алгоритм может быть использован в любом алгоритме сортировки.
Alex Cvetkov
---
* Origin: Life suxx (2:5030/1334)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
