Добрый день всем!
Подумалось тут, что можно на Рефале-5 легко написать короткую, но очень
неэффективную функцию сортировки:
/*
<Sort e.Items> == e.Items
e.Items ::= (s.Key e.Value)*
s.Key ::= s.NUMBER
*/
Sort {
e.L (s.KeyBig e.ValBig) (s.KeySmall e.ValSmall) e.R
, <Compare s.KeyBig s.KeySmall> : '+'
= <Sort e.L (s.KeySmall e.ValSmall) (s.KeyBig e.ValBig) e.R>;
e.Sorted = e.Sorted;
}
Пояснение по Рефалу-5. Функция Compare принимает два числа и возвращает знак их
разности. Таким образом, условие <Compare s.KeyBig s.KeySmall> : '+'
утверждает, что разность s.KeyBig и s.KeySmall положительна, т.е. первое больше
второго.
Сортировка стабильная — она не меняет порядок пар с равными ключами. Сложность
алгоритма O(n³), где n — длина аргумента.
Рассмотрим следующий алгоритм сортировки вставками:
InsertSort {
e.Items = <DoInsertSort () e.Items>;
}
DoInsertSort {
(e.Sorted) t.Next e.Rest
= <DoInsertSort (<Insert e.Sorted t.Next>) e.Rest>;
(e.Sorted) /* пусто */ = e.Sorted;
}
Insert {
e.Sorted (s.KeyLast e.ValLast) (s.KeyNew e.ValNew)
, <Compare s.KeyLast s.KeyNew> : '+'
= <Insert e.Sorted (s.KeyNew e.ValNew)> (s.KeyLast e.ValLast);
e.Sorted = e.Sorted;
}
Его сложность O(n²), он тоже стабильный.
Интересно вот что. Запустим первый алгоритм на некоторых входных данных и
построим трассировку поля зрения на каждом шаге (за исключением шагов на
проверку условий). Сотрём в трассировке все скобки конкретизации. Запустим
второй алгоритм на тех же данных. Также сотрём в трассировке все скобки
конкретизации и форматные структурные скобки. Получится та же самая
последовательность (без учёта повторяющихся строк). Так что в некотором смысле
оба алгоритма эквивалентны.
Интересно, можно ли вывести второй алгоритм из первого какой-нибудь цепочкой
элементарных преобразований?
С уважением,
Александр Коновалов
