Изменения

Для построения таблицы инверсий за линейное время воспользуемся [[Карманная сортировка | карманной сортировкой]]. При [[Карманная сортировка | карманной сортировке ]] нужно определить карман <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

В Кормене описываются мат. выкладкиразделе [[Карманная сортировка | карманная сортировка]] доказывается, доказывающие линейность карманной сортировкичто она работает за линейное время.Что касается подсчета инверсий, то по сути дела в приведенной реализации происходит [[Карманная сортировка | карманная сортировка ]] в online режиме и вся мат.математическая часть из Кормена подходит и под этот случай.

Хотя Следует отметить, что хотя подсчет с помощью [[Карманная сортировка | карманной сортировки ]] выполняется за линейное время, но имеет очень большую константу т.ч. поэтому подсчет с помощью дерева Фенвика(которая выполняется инверсий рассматриваемый выше за <tex>O(n*\log(n))</tex>) часто работает быстрее рассматриваемого в данном случае. Также следует учитывать с помощью какой сортировки вставлять элемент каждый раз. Если размер кармана не велик, то возможно лучше подойдет эффективная реализация квадратичной сортировки, иначе лучше использовать одну из быстрых сортировок. Известно, что маленькие массивы лучше сортировать квадратичной сортировкой. Но как узнать границу, после которой массив перестает быть маленьким? В общем случае эта верхняя граница находится между 32 и 40. У Тима Петерсона в Tim Sort'e это 64.