Разделяй и властвуй: подсчет количества инверсий в массиве

Question

Разделяй и властвуй: подсчет количества инверсий в массиве

Рейтинг: 6Ответов: 2Опубликовано: 16.11.2014

Есть функция для подсчета инверсий в массиве, требующая О(n2) времени:

    static void Inverses(int[] A, ref int count)
    { 
        count = 0;
        for(int i = 0; i < A.Length - 1; i++)
        {
            for (int j = i + 1; j < A.Length; j++)
            {
                if( A[i] > A[j] )
                    count++;
            }
        }
    }

Также есть функция сортировки массива подходом разделяй и властвуй, требующая O(n*log(n)) времени:

    static Int32[] Merge_Sort(Int32[] massive)
    {
        if (massive.Length == 1)
            return massive;
        Int32 mid_point = massive.Length / 2;
        return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));
    }

    static Int32[] Merge(Int32[] mass1, Int32[] mass2)
    {
        Int32 a = 0, b = 0;
        Int32[] merged = new int[mass1.Length + mass2.Length];
        for (Int32 i = 0; i < mass1.Length + mass2.Length; i++)
        {
            if (b < mass2.Length && a < mass1.Length)
                if (mass1[a] > mass2[b])
                    merged[i] = mass2[b++];
                else //if int go for
                    merged[i] = mass1[a++];
            else
                if (b < mass2.Length)
                    merged[i] = mass2[b++];
                else
                    merged[i] = mass1[a++];
        }
        return merged;
    }

Нужно реализовать алгоритм подсчета инверсий в массиве с подходом разделяй и властвуй, которому требовалось бы O(n*log(n)) времени.

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

c# массивы алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 22Принят

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

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

Текстом трудно понять, поэтому рекомендую посмотреть графическую демонстрацию (на той же википедии есть гифка). Когда поймете идею, уже можно вникать и в реализацию.

Насчет инверсий

Когда мы сливаем обе части, как я уже говорил, мы сравниваем элементы одной (первой, левой) части с элементами другой (правой, второй) части соответственно. И если элемент левой части больше элемента правой части соответственно, то значит это и есть инверсия.
И так же все оставшиеся элементы левой части тоже будут больше, т.к. левая и правая часть отсортированы. Поэтому количество инверсий нужно увеличить на количество оставшихся элементов + 1 (текущий элемент).

UPD:

Вот и пример.

Индексация идет с 0. Не описывал, что добавляем элементы в результирующую часть, думаю, это и так понятно. Описал только те части, в которых есть инверсии. Возможны ошибки, т.к. быстро делал. Да и пришлось так сжато уместить элементы, чтобы картинка полностью отобразилась на хэшкоде.

alt text

Answer 2

▲ 2

public static int[] Merge_Sort(int[] arr, ref int counter)
{
    if (arr.Length == 1)
        return arr;
    int mid_point = arr.Length / 2;
    int[] a;


    Merge(Merge_Sort(arr.Take(mid_point).ToArray(), ref counter), Merge_Sort(arr.Skip(mid_point).ToArray(), ref counter), out a, ref counter);
    return a;
}

public static void Merge(int[] mass1, int[] mass2, out int[] merged, ref int counter)
{
    int a = 0, b = 0;            
    merged = new int[mass1.Length + mass2.Length];
    for (int i = 0; i < mass1.Length + mass2.Length; i++)
    {
        if (b < mass2.Length && a < mass1.Length)
            if (mass1[a] > mass2[b])
            {
                merged[i] = mass2[b++];
                counter = counter + (mass1.Length - a);
            }
            else //if int go for 
            {
                merged[i] = mass1[a++];
            }
        else
            if (b < mass2.Length)
        {
            merged[i] = mass2[b++];
        }
        else
        {
            merged[i] = mass1[a++];
        }                
    }            
}

Разделяй и властвуй: подсчет количества инверсий в массиве

Ответы