Может ли сортировка алгоритмов уничтожить ранее существовавший порядок элементов?

Question

Мне было интересно, у меня проблема.

Мои Ситуации выглядит следующим образом:

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

Поэтому, учитывая следующие данные:

1: b/lvl 1 
2: c/lvl 1 
3: a/lvl 1 
4: d/lvl 2 

после первого рода он должен выглядеть следующим образом:

a, b, c, d 

и после второго:

d, a, b, c 

До сих пор так хорошо. Я знаю, что можно уничтожить первую сортировку (например, с помощью Bogosort). Так что может быть выход второго рода:

d, b, c, a 

Но есть ли «правильные» алгоритмы сортировки, которые могли бы сделать это тоже?

Answer 1

То, что вы говорите о том, stability:

При сортировке некоторых видов данных, только часть данных проверяется при определении порядка сортировки. Например, в примере сортировки карт справа, карты сортируются по их рангу, и их костюм игнорируется. В результате можно иметь несколько разных правильно отсортированных версий исходного списка. Стабильные алгоритмы сортировки выбирают один из них, в соответствии со следующим правилом: если два элемента сравниваются как равные, как и две 5 карт, тогда их относительный порядок будет сохранен, так что, если кто-то окажется перед другим на входе, он также будет перед другим на выходе.

Многие алгоритмы устойчивы, а многие другие нет.

Два довольно известных примера - (типичный) quick-sort нестабилен и merge-sort стабилен.

См. Wikipedia для длинного списка алгоритмов сортировки, в том числе, являются ли они стабильными.