Нетривиальная сортировка

381

05 января 2017, 06:09

Есть таблица, пусть для "синтетического" примера - просто таблица целых чисел. Числа могут повторяться и не могут принимать значение NULL. Нужно вывести сортированный список по возрастанию "дистанции".

Определение "дистанции"

Dij = ABS(ABS(Ti)-ABS(Tj))

Где:

Dij - дистанция между i-м и j-м элементом
Ti,Tj - i-й и j-й элементы таблицы

Правила сортировки

Dij<Djk
Если на очередной итерации сортировки на место очередной пары претендуют несколько пар (Dij==Djk), выбирается та пара, у которой есть число - наименьшее из всех чисел из данных пар
по возможности Ti < Tj

Поправка

"Возрастание дистанции" - скорее всего не совсем верная формулировка. Потому как выбор очередной пары зависит от предыдущей. Иными словами - второй элемент предыдущей пары на очередной итерации становится первым в текущей. Поэтому "дистанции" могут "плясать". Типа 2-3-10-1-2-2-7-3...

Для теста

CREATE TABLE Test (
  Digit INT NOT NULL
);
INSERT INTO Test (Digit)
VALUES (17),(16),(9),(8),(7),(3),(0),(-5),(-10),(-17);

Нужный порядок сортировки:

Answer 1

SQLite, postgesql:

WITH RECURSIVE Q(Digit,ids,Level) as(
  select * from (
    select a.Digit,','||a.rowid ids,0 as Level
      from Test a, Test b
     where a.rowid!=b.rowid
     order by abs(abs(a.Digit)-abs(b.Digit)),a.Digit
     limit 1
  ) A
  union all
  select a.Digit,ids||','||a.rowid,Level+1
    from Q, Test a
   where a.rowid in(
          select b.rowid from Test b,(select Q.digit as d) C
           where Q.ids||',' not like '%,'||b.rowid||',%'
           order by abs(abs(b.Digit)-abs(C.d)),b.Digit
           limit 1
         )
)
select Digit from Q order by Level

"странный" подзапрос (select Q.digit as d) пришлось ввести специально для SQLite, потому как он в фразе order by подзапроса в упор не хочет видеть поля таблицы Q. Для posgresql это не требуется и Q.Digit можно указать прямо в order by.

На MySQL решать это ни имею ни малейшего желания, ибо рекурсивных запросов там нет. Хотя в принципе рекурсия может быть эмулирована размножением записей и накапливанием "вышедших" номеров в переменных, примерно как в этом ответе.