Сортировка на основе оценки

Question

У меня есть 1D массив, содержащий набор рейтингов.например,

0 | 0
1 | 2
2 | 2
3 | 1
4 | 0
5 | 1

(первый столбецздесь показан индекс массива)

, который я хотел бы оценить следующим образом:

1 | 2
2 | 2
3 | 1
5 | 1
0 | 0
4 | 0

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

Answer 1

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

• Вставка сортировки
• Слияние сортировки
• Пузырьковая сортировка

Если бы я выбрал, я бы, вероятно, пошел с сортировкой слиянием, потому что это имеет лучшую сложность.Сортировка вставок может превзойти его в небольших списках.Я помню, что читал, что есть один случай, когда Bubble Sort не страшен, но я забываю, что это такое.

Однако стоит отметить, что беспокойство по поводу стабильности исключит алгоритм, подобный быстрой сортировке, который может быть алгоритмом,неопределенный язык использует в своих функциях сортировки.

Какой бы язык вы ни использовали, его реализация сортировки должна иметь возможность взять функцию, которая будет сравнивать два элемента и определять, какой из них «больше».Так что все, что вам действительно нужно сделать, это написать функцию, которая

• Если ранги равны, утверждает, что элементы с большим числовым индексом "больше"
• Если рангине равно, утверждает, что элемент с более высоким рангом «больше».
• Если и ранг, и числовой индекс равны, утверждает, что они равны.

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

Точный протокол, которому следует эта функциябудет варьироваться от языка к языку.

Answer 2

То, что вы ищете, это «стабильный» алгоритм сортировки, который не переупорядочивает элементы, которые сравниваются как равные.Вы не сказали, какой язык или набор инструментов вы используете, поэтому я не могу сказать вам, что конкретно использовать.Нестабильность является неотъемлемой чертой некоторых алгоритмов, другие могут быть реализованы в стабильных или нестабильных формах.Обычно алгоритмы сортировки библиотеки выбирают стабильную реализацию, если это возможно.

Answer 3

Не знаю, насколько это эффективно или хорошо, но:

// suppose you have scores[n]

for c1 = 1 to n
    for c2 = c1 + 1 to n
        if scores[c2]>scores[c1] then swap them

Answer 4

Хм .. это стабильность важна?

Разве это не сортировка по рейтингу?

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

Стабильная сортировка может повлечь за собой ненужные потери производительности с добавленной сложностью.