Сортировка, когда функция сравнения может вернуть значение «не знаю» для определенных пар

Я хотел бы сортировать объекты (или, возможно, строки базы данных) определенным образом. В основном основано на time, но это значение может быть NULL. У меня есть второе значение sequence, которое представляет собой число, указывающее порядок, но оно может иметь число, которое больше не соответствует порядку столбца time. Так что он должен хотя бы отсортировать время по порядку.

Допустим, у меня есть массив/БД со следующим содержимым:

id  time   sequence
 2  11:35  46
 4  NULL   48
 5  11:40  99
 6  NULL   49
 8  11:45  51
 9  11:50  52
 7  NULL   53
 3  NULL   54
 1  11:55  55

Я бы хотел, чтобы конечный результат был таким

id  time   sequence
 2  11:35  46
 4  NULL   48
 6  NULL   49
 5  11:40  99
 8  11:45  51
 9  11:50  52
 7  NULL   53
 3  NULL   54
 1  11:55  55

Простая функция сравнения будет выглядеть примерно так (псевдокод)

int compare(a, b)
{
    if(a->time !== null && b->time !== null)
        return (int)a->time - (int)b->time;

    return a->sequence - b->sequence;
}

Но общий вызов сортировки, конечно, ограничит количество вызовов функции сравнения. Поэтому, если он сравнит идентификаторы 5/1, 5/3 и 1/3, он определит порядок и выдаст этот результат.

id  time   sequence
 2  11:35  46
 4  NULL   48
 6  NULL   49
 8  11:45  51
 9  11:50  52
 7  NULL   53
 3  NULL   54
 5  11:40  99
 1  11:55  55

Я хотел бы, чтобы моя функция сравнения говорила что-то вроде «не знаю» для определенных сравнений. Namelijk, когда строка с заполненным time сравнивается со строкой без. Так что sort-функция вынуждена смотреть дальше. Например, я пытался вернуть 0 в этом случае, но это не решает проблему. Есть ли название для такого механизма? Есть ли другой способ решить эту проблему?


sorting language-agnostic topological-sort
person ontrack    schedule 13.10.2019    source источник
comment
Возможный дубликат Как сортировать с неполным порядком?   -  person dmckee --- ex-moderator kitten    schedule 16.11.2019
comment
Relasted: stackoverflow.com/questions/480640/ stackoverflow.com/q/51429309/2509   -  person dmckee --- ex-moderator kitten    schedule 16.11.2019

Ответы (1)


arrow_upward
1
arrow_downward

Ясно, что вы не можете сортировать, просто сравнивая любые два элемента, потому что у вас нет полного порядка.

Вы, кажется, очень уверены в полученном порядке.

Возьмем другой пример, потому что ожидания мне неясны:

id  time   sequence
 2  11:35  103
 5  11:40  51
 8  11:45  28
 9  11:50  50
 1  11:55  99

куда должно идти все время NULL и почему?

 4  NULL   48
 6  NULL   49
 7  NULL   53
 3  NULL   54

Кажется, трудно найти правило для размещения NULL после того, как мы отсортировали не NULL!
Что, вероятно, лучше всего соответствует вашим ожиданиям, так это результат процедурного алгоритма, например, такой:

  1. сначала отсортировать по порядку
  2. затем позвольте четко определенным временам двигаться вверх, пока есть большее время выше

Написанный таким образом этап 2 выглядит как пузырьковая сортировка, ограниченная индексами с ненулевым временем... Вы можете назвать это разреженной пузырьковой сортировкой.

Результирующий порядок всегда один и тот же, каким бы ни был первоначальный порядок, поэтому он не является двусмысленным.
Я думаю, что это потому, что этап 1) является общим порядком.
Если вы введете NULL в столбце последовательности, я не буду даже уверен, что вы получите недвусмысленную сортировку...
Может быть, вы можете назвать это многоэтапной частичной сортировкой.

person aka.nice    schedule 15.11.2019