Как отсортировать массив с минимальным обменом соседних элементов

Question

У меня был алгоритм для решения проблемы, при котором профессор должен сортировать студентов по баллам, таким как 1 для хорошего и 0 для плохого. в минимальном количестве обменов, где только смежные студенты могут поменяться местами. Например, если студенты указаны в последовательности [0,1,0,1], требуется только один обмен [0,0,1,1] или в случае [0,0,0,0,1,1, 1,1] обмен не требуется.

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

Наибольшее количество тестов было пройдено, когда я пытаюсь отсортировать массив в обратном порядке. Я также попытался отсортировать массив в порядке, основанном на том, является ли первый элемент массива 0 или 1. Например, если первый элемент равен 1, тогда я должен отсортировать массив в порядке убывания, иначе в порядке возрастания, поскольку студенты могут ни в одной группе все еще никто не работал. Некоторые тестовые случаи всегда терпели неудачу. Дело в том, что когда я сортировал его в порядке возрастания, один тестовый случай, который не был выполнен в случае обратной сортировки, прошел вместе с некоторыми другими, но не со всеми. Так что я не знаю, что я делал неправильно.

Answer 1

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

def count(lst):
    total = 0
    ones = 0
    for x in lst:
        if x:
            ones += 1
        else:
            total += ones
    return total

Поскольку сортировка нулей перед нулями также является опцией, нам просто нужно запустить этот алгоритм дважды, поменяв местами роли нулей и единиц, и возьми минимум.

Answer 2

Мне кажется, что термин "сортировка" - это преувеличение, когда речь идет о массиве из 0 и 1. Вы можете просто посчитать 0 и 1 в O (n) и произвести вывод.

Чтобы рассмотреть часть "минимальных свопов", я построил игрушечный пример; две идеи пришли мне в голову. Итак, пример. Мы сортируем студентов ... f:

a b c d e f
0 1 0 0 1 1

a c d b e f
0 0 0 1 1 1

Как видите, здесь не так много сортировки. Три 0, три 1.

Сначала я сформулировал это как проблему редактировать расстояние . И. е. вам нужно конвертировать abcdef в acdbef, используя только операцию "swap". Но как вы вообще пришли к acdbef? Моя гипотеза здесь заключается в том, что вам просто нужно перетащить 0 и 1 в противоположные стороны массива, не нарушая их порядок. Например,

        A     B     C     D
0 0 ... 0 ... 1 ... 0 ... 1 ... 1 1

0 0 0 0         ...         1 1 1 1
    A C                     B D

Я не уверен на 100%, работает ли он и дает ли вы минимальные свопы. Но это кажется разумным - зачем вам тратить дополнительный своп на e. г. А и С?

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

Относительно того, как найти количество свопов или даже последовательность свопов, - размышление с точки зрения расстояний редактирования может помочь вам с последним. Поиск только количества свопов также может быть упрощенной формой редактирования расстояния. Или, может быть, что-то еще более простое - е. г. найдите что-то (a 0 или 1), ближайшее к его «кластеру», и переместите его. Затем повторяйте, пока массив не будет отсортирован.