Изменения

Для построения таблицы инверсий за линейное время воспользуемся [[Карманная сортировка | карманной сортировкой]]. При [[Карманная сортировка | карманной сортировке ]] нужно определить карман <tex>B</tex>, в который попадет текущий элемент. Затем найти количество число элементов в старших карманах относительно <tex>B</tex>. Потом аккуратно подсчитать количество элементов, больших текущего в кармане <tex>B</tex>. Карман <tex>A</tex> считается старшим для кармана <tex>B</tex>, если любой элемент из <tex>A</tex> больше любого элемента из <tex>B</tex>.

'''int''' bucket_sort('''vector<int>''' Permutationpermutation): MAX '''int''' max = число больше Permutationpermutation.size и из которого можно извлечь целый квадратный корень BUCKET'''int''' bucket =sqrt(MAXmax) '''int''' Answer answer = 0<font color=green> // изначально кол-во инверсий</font> '''list<list<int>>''' Bankbank(BUCKETbucket) '''for''' i = 0 to Permutationpermutation.size '''int''' Position pos = (Permutationpermutation[i] - 1)/(MAX max / BUCKETbucket) <font color=green>// Определяем в каком кармане должен лежать элемент</font> '''int''' NewPosition newPosition = 0 '''while'''(NewPosition newPosition < Bankbank[pos].size && Bank'''and''' bank[pos][NewPositionnewPosition] < Permutationpermutation[i] ) <font color=green>// идем до позиции где должен стоять элемент Permutationpermutation[i] </font> NewPositionnewPosition++ Answer answer += Bankbank[pos].size - NewPosition newPosition <font color=green>// ищем сколько инверсий эленент создает в своем кармане</font> Bankbank[pos].insert( NewPosition newPosition, Permutationpermutation[i] ) <font color=green>// вставляем элемент в Карман на свою позицию </font> '''for''' i = Position position + 1 to BUCKETbucket -1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font> Answer answer += Bankbank[i].size '''return''' Answeranswer

Известно что В разделе [[Карманная сортировка | карманная сортировка имеет линейную сложность]] доказывается, но только в том случае если элементы равномерно распределенычто она работает за линейное время. Т.к. мы ищем кол-во Что касается подсчета инверсий , то в перестановке то мы знаем что наши элементы встречаются на отрезке от <tex>приведенной реализации происходит [[1;nКарманная сортировка | карманная сортировка]</tex> единожды , а следовательно равномерно распределены] в online режиме и вся математическая часть подходит и под этот случай.

Сложность представленного алгоритма есть Следует отметить, что хотя подсчет с помощью [[Карманная сортировка | карманной сортировки]] выполняется за линейное время, но имеет очень большую константу поэтому подсчет инверсий рассматриваемый выше за <tex>O(n\log n)</tex> работает быстрее .