Как найти количество инверсий в массиве?

Question

В основном я пытаюсь написать алгоритм в Java, чтобы определить количество пар в массиве, который вышел из строя. Поэтому, если мы берем i, а j и j находятся в более высоком положении в массиве, чем i, но A [i]> A [j], то он учитывает эти два числа как инверсию. В настоящее время это то, что у меня есть:

for(int i = 0; i<n-1; i++){ 
    if (A[i] > A[i+1]){ 
     k++; 

Что это делает только по сравнению с парами, которые находятся в непосредственной близости друг друга, так что теперь я пытаюсь изменить это, чтобы найти любые два числа в массиве, где нижняя позиция более высокое значение, чем число в более высоком положении. Я знаю, как это сделать, но я хочу, чтобы время выполнения было (n + k), где n - длина массива, а k - количество инверсий в массиве.

EDIT: Вот моя попытка осуществить вставки рода:

int k = 0; 
int [] A = {5, 4, 3, 2, 1}; 
int n = A.length; 
for(int i = 1; i < n; i++){ 
    int temp = A[i]; 
    int j; 
    for (j = i - 1; j >=0 && temp < A[j]; j--){ 
     A[j + 1] = A[j]; 
    A[j + 1] = A[j]; 
     k++; 

к, как предполагается, будет отслеживать, как много инверсий. Для массива 5, 4, 3, 2, 1 число, которое я получил, - 6. Правильно ли это?

Answer 1

Инверсия Count для массива указывает, насколько далеко (или близко) массив сортируется. Если массив уже отсортирован, то число инверсии равно 0. Если массив отсортирован в обратном порядке, то количество инверсий является максимальным. Формально говоря, два элемента a [i] и a [j] образуют инверсию, если a [i]> a [j] и i < j Пример: Последовательность 2, 4, 1, 3, 5 имеет три инверсии (2, 1), (4, 1), (4, 3).

Для каждого элемента подсчитайте количество элементов, которые находятся с правой стороны от него и меньше его.

int getInvCount(int arr[], int n) 
{ 
    int inv_count = 0; 
    int i, j; 

    for(i = 0; i < n - 1; i++) 
    for(j = i+1; j < n; j++) 
     if(arr[i] > arr[j]) 
     inv_count++; 

    return inv_count; 
} 

/* Driver progra to test above functions */ 
int main(int argv, char** args) 
{ 
    int arr[] = {1, 20, 6, 4, 5}; 
    printf(" Number of inversions are %d \n", getInvCount(arr, 5)); 
    getchar(); 
    return 0; 
} 

Answer 2

Решение состоит в том, чтобы внедрить сортировку вставки и подсчитать количество раз, когда была смещена пара смежных элементов. Это работает, потому что сортировка вставки выполняет обмен и только для каждой инверсии. Фактически, его время работы составляет O (n + k), как и вы просили.

---

Что касается вопроса второй части - вот исправленный алгоритм вставки сортировать:

for (int i = 1; i < n; i++) { 
    int temp = A[i]; 
    int j; 
    for (j = i - 1; j >= 0 && temp < A[j]; j--) { 
     A[j + 1] = A[j]; 
     k++; // Number of inversions 
    } 
    A[j + 1] = temp; 
} 

---

Дополнительное примечание: эффективный способ подсчета инверсий массива является изменение алгоритма сортировки слиянием, которая работает в O (n log n) время. Однако, когда к мал, О (п + к) составляет приблизительно O (п), что меньше, чем О (п лог п). Действительно, сортировка слиянием ПОРА лучшем случае еще O (п лог п), в то время как лучший случай сортировки вставками является O (п).Поэтому, сортировка слиянием делает вопрос не ответить на OP для алгоритма O (п + к).