Рубрики

Граф Инверсии в массиве | Набор 1 (с использованием сортировки слиянием)

Число инверсий для массива указывает — насколько далеко (или близко) массив от сортировки. Если массив уже отсортирован, то счетчик инверсий равен 0. Если массив отсортирован в обратном порядке, то счетчик инверсий является максимальным.
Формально говоря, два элемента a [i] и a [j] образуют инверсию, если a [i]> a [j] и i <j

Пример:
Последовательность 2, 4, 1, 3, 5 имеет три инверсии (2, 1), (4, 1), (4, 3).

МЕТОД 1 (простой)
Для каждого элемента подсчитайте количество элементов, которые находятся справа от него и меньше его.

C ++

// C ++ программа для подсчета инверсий
// в массиве
#include <bits/stdc++.h>

using namespace std;

  

int getInvCount(int arr[], int n)

{

    int inv_count = 0;

    for (int i = 0; i < n - 1; i++)

        for (int j = i + 1; j < n; j++)

            if (arr[i] > arr[j])

                inv_count++;

  

    return inv_count;

}

  
// Код драйвера

int main()

{

    int arr[] = { 1, 20, 6, 4, 5 };

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << " Number of inversions are "

         << getInvCount(arr, n);

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

// C программа для подсчета
// Инверсии в массиве
#include <stdio.h>

int getInvCount(int arr[], int n)

{

    int inv_count = 0;

    for (int i = 0; i < n - 1; i++)

        for (int j = i + 1; j < n; j++)

            if (arr[i] > arr[j])

                inv_count++;

  

    return inv_count;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int arr[] = { 1, 20, 6, 4, 5 };

    int n = sizeof(arr) / sizeof(arr[0]);

    printf(" Number of inversions are %d \n", getInvCount(arr, n));

    return 0;

}

Джава

// Java-программа для подсчета
// инверсии в массиве

class Test {

    static int arr[] = new int[] { 1, 20, 6, 4, 5 };

  

    static int getInvCount(int n)

    {

        int inv_count = 0;

        for (int i = 0; i < n - 1; i++)

            for (int j = i + 1; j < n; j++)

                if (arr[i] > arr[j])

                    inv_count++;

  

        return inv_count;

    }

  

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

        System.out.println("Number of inversions are "

                           + getInvCount(arr.length));

    }

}

python3

# Python3 программа для подсчета
# инверсии в массиве

  

def getInvCount(arr, n):

  

    inv_count = 0

    for i in range(n):

        for j in range(i + 1, n):

            if (arr[i] > arr[j]):

                inv_count += 1

  

    return inv_count

  
Код водителя

arr = [1, 20, 6, 4, 5]

n = len(arr)

print("Number of inversions are",

              getInvCount(arr, n))

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # программа для подсчета инверсий
// в массиве

using System;

using System.Collections.Generic;

  

class GFG {

  

    static int[] arr = new int[] { 1, 20, 6, 4, 5 };

  

    static int getInvCount(int n)

    {

        int inv_count = 0;

  

        for (int i = 0; i < n - 1; i++)

            for (int j = i + 1; j < n; j++)

                if (arr[i] > arr[j])

                    inv_count++;

  

        return inv_count;

    }

  

    // Код драйвера

    public static void Main()

    {

        Console.WriteLine("Number of "

                          + "inversions are "

                          + getInvCount(arr.Length));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php 
// PHP программа для подсчета инверсий
// в массиве

  

function getInvCount(&$arr, $n)

{

    $inv_count = 0;

    for ($i = 0; $i < $n - 1; $i++)

        for ($j = $i + 1; $j < $n; $j++)

            if ($arr[$i] > $arr[$j])

                $inv_count++;

  

    return $inv_count;

}

  
// Код драйвера

$arr = array(1, 20, 6, 4, 5 );

$n = sizeof($arr);

echo "Number of inversions are "

           getInvCount($arr, $n);

  
// Этот код предоставлен ita_c
?>


Выход:

Number of inversions are 5

Сложность времени: O (n ^ 2)
МЕТОД 2 (Улучшение сортировки слиянием)
Предположим, мы знаем количество инверсий в левой и правой половине массива (пусть это будут inv1 и inv2), какие виды инверсий не учитываются в Inv1 + Inv2? Ответ — инверсии, которые мы должны посчитать на этапе объединения. Поэтому, чтобы получить количество инверсий, нам нужно добавить количество инверсий в левом подмассиве, правом подмассиве и слиянии ().

Как получить количество инверсий в слиянии ()?
В процессе объединения пусть i используется для индексации левого подмассива, а j — для правого подмассива. На любом этапе слияния (), если a [i] больше, чем a [j], то существуют (mid — i) инверсии. потому что левый и правый подмассивы отсортированы, поэтому все остальные элементы в левом подмассиве (a [i + 1], a [i + 2]… a [mid]) будут больше, чем a [j]

Полная картина:

Реализация:

C ++

// C ++ программа для подсчета
// Инверсии в массиве
// используя сортировку слиянием
#include <bits/stdc++.h>

using namespace std;

  

int _mergeSort(int arr[], int temp[], int left, int right);

int merge(int arr[], int temp[], int left, int mid, int right);

  
/ * Эта функция сортирует входной массив и возвращает
количество инверсий в массиве * /

int mergeSort(int arr[], int array_size)

{

    int temp[array_size];

    return _mergeSort(arr, temp, 0, array_size - 1);

}

  
/ * Вспомогательная рекурсивная функция, которая сортирует входной массив и
возвращает количество инверсий в массиве. * /

int _mergeSort(int arr[], int temp[], int left, int right)

{

    int mid, inv_count = 0;

    if (right > left) {

        / * Разделить массив на две части и

        вызов _mergeSortAndCountInv ()

        для каждой из частей * /

        mid = (right + left) / 2;

  

        / * Счетчик инверсий будет суммой

        инверсии в левой части, правой части

        и количество инверсий в слиянии * /

        inv_count += _mergeSort(arr, temp, left, mid);

        inv_count += _mergeSort(arr, temp, mid + 1, right);

  

        / * Объединить две части * /

        inv_count += merge(arr, temp, left, mid + 1, right);

    }

    return inv_count;

}

  
/ * Этот пух объединяет два отсортированных массива
и возвращает счетчик инверсий в массивах. * /

int merge(int arr[], int temp[], int left,

          int mid, int right)

{

    int i, j, k;

    int inv_count = 0;

  

    i = left; / * я индекс для левого подмассива * /

    j = mid; / * j - индекс для правого подмассива * /

    k = left; / * k - индекс для результирующего объединенного подмассива * /

    while ((i <= mid - 1) && (j <= right)) {

        if (arr[i] <= arr[j]) {

            temp[k++] = arr[i++];

        }

        else {

            temp[k++] = arr[j++];

  

            / * это сложно - см. выше

            объяснение / схема для слияния () * /

            inv_count = inv_count + (mid - i);

        }

    }

  

    / * Копировать оставшиеся элементы левого подмассива

(если таковые имеются), чтобы временно * /

    while (i <= mid - 1)

        temp[k++] = arr[i++];

  

    / * Копировать остальные элементы правого подмассива

(если таковые имеются), чтобы временно * /

    while (j <= right)

        temp[k++] = arr[j++];

  

    / * Скопировать обратно объединенные элементы в исходный массив * /

    for (i = left; i <= right; i++)

        arr[i] = temp[i];

  

    return inv_count;

}

  
// Код драйвера

int main()

{

    int arr[] = { 1, 20, 6, 4, 5 };

    int n = sizeof(arr) / sizeof(arr[0]);

    int ans = mergeSort(arr, n);

    cout << " Number of inversions are " << ans;

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

// C программа для подсчета
// Инверсии в массиве
// используя сортировку слиянием
#include <stdio.h>

  

int _mergeSort(int arr[], int temp[], int left, int right);

int merge(int arr[], int temp[], int left, int mid, int right);

  
/ * Эта функция сортирует входной массив и возвращает

   количество инверсий в массиве * /

int mergeSort(int arr[], int array_size)

{

    int* temp = (int*)malloc(sizeof(int) * array_size);

    return _mergeSort(arr, temp, 0, array_size - 1);

}

  
/ * Вспомогательная рекурсивная функция, которая сортирует входной массив и

  возвращает количество инверсий в массиве. * /

int _mergeSort(int arr[], int temp[], int left, int right)

{

    int mid, inv_count = 0;

    if (right > left) {

        / * Разделите массив на две части и вызовите _mergeSortAndCountInv ()

       для каждой из частей * /

        mid = (right + left) / 2;

  

        / * Количество инверсий будет суммой инверсий в левой части, правой части

      и количество инверсий в слиянии * /

        inv_count += _mergeSort(arr, temp, left, mid);

        inv_count += _mergeSort(arr, temp, mid + 1, right);

  

        / * Объединить две части * /

        inv_count += merge(arr, temp, left, mid + 1, right);

    }

    return inv_count;

}

  
/ * Этот funt объединяет два отсортированных массива и возвращает количество инверсий в

   массивы. * /

int merge(int arr[], int temp[], int left, int mid, int right)

{

    int i, j, k;

    int inv_count = 0;

  

    i = left; / * я индекс для левого подмассива * /

    j = mid; / * j - индекс для правого подмассива * /

    k = left; / * k - индекс для результирующего объединенного подмассива * /

    while ((i <= mid - 1) && (j <= right)) {

        if (arr[i] <= arr[j]) {

            temp[k++] = arr[i++];

        }

        else {

            temp[k++] = arr[j++];

  

            / * это сложно - см. выше объяснение / диаграмма для слияния () * /

            inv_count = inv_count + (mid - i);

        }

    }

  

    / * Копировать оставшиеся элементы левого подмассива

   (если таковые имеются), чтобы временно * /

    while (i <= mid - 1)

        temp[k++] = arr[i++];

  

    / * Копировать остальные элементы правого подмассива

   (если таковые имеются), чтобы временно * /

    while (j <= right)

        temp[k++] = arr[j++];

  

    / * Скопировать обратно объединенные элементы в исходный массив * /

    for (i = left; i <= right; i++)

        arr[i] = temp[i];

  

    return inv_count;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main(int argv, char** args)

{

    int arr[] = { 1, 20, 6, 4, 5 };

    printf(" Number of inversions are %d \n", mergeSort(arr, 5));

    getchar();

    return 0;

}

Джава

// Java реализация подхода

import java.util.Arrays;

  

public class GFG {

  

    // Функция для подсчета количества инверсий

    // во время процесса слияния

    private static int mergeAndCount(int[] arr, int l, int m, int r)

    {

  

        // Левый подмассив

        int[] left = Arrays.copyOfRange(arr, l, m + 1);

  

        // Правый подмассив

        int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

  

        int i = 0, j = 0, k = l, swaps = 0;

  

        while (i < left.length && j < right.length) {

            if (left[i] <= right[j])

                arr[k++] = left[i++];

            else {

                arr[k++] = right[j++];

                swaps += (m + 1) - (l + i);

            }

        }

  

        // Заполняем из остальной части левого подмассива

        while (i < left.length)

            arr[k++] = left[i++];

  

        // Заполняем из остального правого подмассива

        while (j < right.length)

            arr[k++] = right[j++];

  

        return swaps;

    }

  

    // Объединить функцию сортировки

    private static int mergeSortAndCount(int[] arr, int l, int r)

    {

  

        // Отслеживает количество инверсий на

        // конкретный узел дерева рекурсии

        int count = 0;

  

        if (l < r) {

            int m = (l + r) / 2;

  

            // Общее количество инверсий = количество левых подрешеток

            // + количество правых подмассивов + количество слияний

  

            // Количество левых подмассивов

            count += mergeSortAndCount(arr, l, m);

  

            // Правильный подсчет

            count += mergeSortAndCount(arr, m + 1, r);

  

            // Счет слияния

            count += mergeAndCount(arr, l, m, r);

        }

  

        return count;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int[] arr = { 1, 20, 6, 4, 5 };

  

        System.out.println(mergeSortAndCount(arr, 0, arr.length - 1));

    }

}

  
// Этот код предоставлен Pradip Basak

python3

# Python 3 программа для подсчета инверсий в массиве

  
# Функция для использования счетчика инверсий

def mergeSort(arr, n):

    # Temp_arr создан для хранения

    # отсортированный массив в функции слияния

    temp_arr = [0]*n

    return _mergeSort(arr, temp_arr, 0, n-1)

  
# Эта функция будет использовать MergeSort для подсчета инверсий

  

def _mergeSort(arr, temp_arr, left, right):

  

    # Переменная inv_count используется для хранения

    Количество инверсий в каждом рекурсивном вызове

  

    inv_count = 0

  

    # Мы сделаем рекурсивный вызов, если и только если

    # у нас более одного элемента

  

    if left < right:

  

        # mid рассчитывается для разделения массива на два подмассива

        # Пол деления обязательно в случае с питоном

  

        mid = (left + right)//2

  

        # Он рассчитает количество инверсий в левом подмассиве

  

        inv_count += _mergeSort(arr, temp_arr, left, mid)

  

        # Он вычислит количество инверсий в правом подмассиве

  

        inv_count += _mergeSort(arr, temp_arr, mid + 1, right)

  

        # Он объединит два подмассива в отсортированный подмассив

  

        inv_count += merge(arr, temp_arr, left, mid, right)

    return inv_count

  
# Эта функция объединит два подмассива в один отсортированный подмассив

def merge(arr, temp_arr, left, mid, right):

    i = left     # Начальный индекс левого подмассива

    j = mid + 1 # Начальный индекс правого подмассива

    k = left     # Начальный индекс сортируемого подмассива

    inv_count = 0

  

    # Условия проверяются, чтобы убедиться, что i и j не превышают их

    # пределы подмассива.

  

    while i <= mid and j <= right:

  

        # Инверсии не будет, если arr [i] <= arr [j]

  

        if arr[i] <= arr[j]:

            temp_arr[k] = arr[i]

            k += 1

            i += 1

        else:

            # Инверсия произойдет.

            temp_arr[k] = arr[j]

            inv_count += (mid-i + 1)

            k += 1

            j += 1

  

    # Скопировать оставшиеся элементы левого подмассива во временный массив

    while i <= mid:

        temp_arr[k] = arr[i]

        k += 1

        i += 1

  

    # Скопировать оставшиеся элементы правого подмассива во временный массив

    while j <= right:

        temp_arr[k] = arr[j]

        k += 1

        j += 1

  

    # Скопировать отсортированный подмассив в исходный массив

    for loop_var in range(left, right + 1):

        arr[loop_var] = temp_arr[loop_var]

          

    return inv_count

  
Код водителя
# Данный массив

arr = [1, 20, 6, 4, 5]

n = len(arr)

result = mergeSort(arr, n)

print("Number of inversions are", result)

  
# Этот код предоставлен ankush_953

C #

// C # реализация подсчета
// инверсия с использованием сортировки слиянием

  

using System;

public class Test {

  

    / * Этот метод сортирует входной массив и возвращает

       количество инверсий в массиве * /

    static int mergeSort(int[] arr, int array_size)

    {

        int[] temp = new int[array_size];

        return _mergeSort(arr, temp, 0, array_size - 1);

    }

  

    / * Вспомогательный рекурсивный метод, который сортирует входной массив и

      возвращает количество инверсий в массиве. * /

    static int _mergeSort(int[] arr, int[] temp, int left, int right)

    {

        int mid, inv_count = 0;

        if (right > left) {

            / * Разделите массив на две части и вызовите _mergeSortAndCountInv ()

           для каждой из частей * /

            mid = (right + left) / 2;

  

            / * Количество инверсий будет суммой инверсий в левой части, правой части

          и количество инверсий в слиянии * /

            inv_count += _mergeSort(arr, temp, left, mid);

            inv_count += _mergeSort(arr, temp, mid + 1, right);

  

            / * Объединить две части * /

            inv_count += merge(arr, temp, left, mid + 1, right);

        }

        return inv_count;

    }

  

    / * Этот метод объединяет два отсортированных массива и возвращает количество инверсий в

       массивы. * /

    static int merge(int[] arr, int[] temp, int left, int mid, int right)

    {

        int i, j, k;

        int inv_count = 0;

  

        i = left; / * я индекс для левого подмассива * /

        j = mid; / * j - индекс для правого подмассива * /

        k = left; / * k - индекс для результирующего объединенного подмассива * /

        while ((i <= mid - 1) && (j <= right)) {

            if (arr[i] <= arr[j]) {

                temp[k++] = arr[i++];

            }

            else {

                temp[k++] = arr[j++];

  

                / * это сложно - см. выше объяснение / диаграмма для слияния () * /

                inv_count = inv_count + (mid - i);

            }

        }

  

        / * Копировать оставшиеся элементы левого подмассива

       (если таковые имеются), чтобы временно * /

        while (i <= mid - 1)

            temp[k++] = arr[i++];

  

        / * Копировать остальные элементы правого подмассива

       (если таковые имеются), чтобы временно * /

        while (j <= right)

            temp[k++] = arr[j++];

  

        / * Скопировать обратно объединенные элементы в исходный массив * /

        for (i = left; i <= right; i++)

            arr[i] = temp[i];

  

        return inv_count;

    }

  

    // Метод драйвера для проверки вышеуказанной функции

    public static void Main()

    {

        int[] arr = new int[] { 1, 20, 6, 4, 5 };

        Console.Write("Number of inversions are " + mergeSort(arr, 5));

    }

}
// Этот код предоставлен Rajput-Ji


Выход:

Number of inversions are 5

Сложность времени: O (N log N)
Алгоритмическая парадигма: разделяй и властвуй

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

Вы можете видеть.
Граф инверсий в массиве | Набор 2 (с использованием самобалансирующегося BST)
Подсчет инверсий с использованием Set в C ++ STL
Граф инверсий в массиве | Набор 3 (с использованием BIT)


Ссылки:

http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf
http://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в вышеуказанной программе / алгоритме или другие способы решения той же проблемы.

Рекомендуемые посты:

Граф Инверсии в массиве | Набор 1 (с использованием сортировки слиянием)

0.00 (0%) 0 votes