минимальный переключатель для отсортированного перестановки

Question

Предположим, у меня есть массив как это: [5 4 1 2 3]

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

Теперь ответ 7 в этом случае. Просто двигайте 4 и 5 вправо или перемещайте 1, 2, 3 влево.

Ирония заключается в том, что я использовал [4 5 1 2 3] в своих заметках, что дает 6, и вводит в заблуждение себя и делает себя дураком.

Шаги:

[5 1 2 3 4] // Шаг 1

[1 5 4 3 2] // Шаг 2

[1 5 4 3 2] // шаг 3

[1 2 3 4 5] // шаг 4

[1 2 3 4 5] // шаг 5

[1 2 3 4 5] // шаг 6

[1 2 3 4 5] // Шаг 7

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

Но это кажется слишком медленным, любые идеи?

EDIT: из комментария: являются ли элементы массива гарантированно полностью принадлежащими {1..N} для массива размера N, без повторяющихся чисел?

Nope. Это не гарантирует, не повторять или быть в [1 ... N] для массива размером с N.

UPDATE:

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

С помощью bubblesort вы в основном рассчитываете количество переключателей при запуске алгоритма.

С mergesort это немного сложнее, но подсчет происходит при слиянии. Когда массив уже объединен, счетчик должен дать 0, поскольку для сортировки этого массива не потребуется никаких коммутаторов. С помощью bubblesort вы считаете переключатели, когда вы нажимаете самое большое или наименьшее число влево или вправо. С mergesort вы рассчитываете переключатели при слиянии. Я немного ручаю, нажимая грубую силу, вы попадете туда.

Answer 1

Это выглядит подозрительно похоже на bubble sort, в котором вам нужно до n^2 движений.

И интересный факт заключается в том, что простая сортировка пузырьков фактически достигает вашей цели, чтобы найти минимальное количество переключателей!(Доказательство ниже)

В этом случае нам не нужно для дальнейшего совершенствования алгоритмов с использованием двойных петель, и на самом деле это возможно с помощью двойных петель (в C++):

int switch = 0; 
for(int repeat=0; repeat<n; repeat++){ 
    for(int j=0; j<n-repeat; j++){ 
     if(arr[j]>arr[j+1]){ 
      int tmp = arr[j]; 
      arr[j] = arr[j+1]; 
      arr[j+1] = tmp; 
      switch = switch + 1 
     } 
    } 
} 

switch результат.
arr - массив, содержащий числа.
n - длина массива.

Докажите, что это производит минимальное количество переключателя:

Во-первых, отметим, что пузырьковая сортировка по существу перемещает самый высокий элемент в крайнем правом положении в массиве на каждой итерации (внешняя петля)

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

Answer 2

Что вы на самом деле ищете, вычисляет количество инверсий в последовательности.

Это может быть сделано в O(n*logn) с использованием mergesort, например.

Here У вас есть статья об этой теме, выглядит вполне понятной.

еще несколько ссылок:

• https://stackoverflow.com/a/338252/2180475
• https://codereview.stackexchange.com/questions/12922/inversion-count-using-merge-sort