Соpтиpовка

From

Alex Cvetkov (2:5030/1334)

To

Andrey Belyakov

Date

2002-05-02T10:53:21Z

Area

RU.ALGORITHMS

Hello Andrey!

02 Май 02 02:24, Andrey Belyakov писал(ла) Alexey V. Goloborchy:

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

Радость моя, только чтобы ты успокоился. Привожу псевдокод (перевести в программу на си не составит труда даже для тебя) алгоритма меняюжего местами две строки в упакованном виде. Как понимаю, именно эта задача вызвала у тебя непреодалимые трудности.

Наити A1 - адрес начала первой строки, B1 - адрес конеца первой строки,
A2, B2 - аналогичные параметры второй строки.
L1 = B1-A1 - длинна первой строки. Аналогично L2 = B2 - B1

Условимся, не ограничивая общности, что первая строка находиться по меньшим адресам в памяти.
Также следует отметить что из условия задачи строки не пересекаються.

Наидем разность 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)