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

Question

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

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

id  time   sequence
 2  11:35  46
 4  NULL   48
<b> 5  11:40  99</b>
 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
<b> 5  11:40  99</b>
 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
<b> 5  11:40  99</b>
 1  11:55  55

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

Answer 1

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

Вы, похоже, очень уверены в результирующем порядке.

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

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 выглядит так, что сортировка пузырей ограничена индексами с ненулевым временем ... Вы можете назвать это разреженным пузыремsort.

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