1632
правки
Изменения
м
<font color=green>MAX - число больше a.size() и из которого можно извлечь целый квадратный корень.</font>
<font color=green>BUCKET - размер кармана BUCKET=sqrt(MAX)</font>
'''int''' bucket_sort( '''vector<int>''' a )
'''int''' ans = 0;<font color=green>//изначально кол-во инверсий</font>
'''vector<int>''' tab_invers(a'''.size()'''+1);<font color=green>//таблица перестановок</font>
'''vector< list<int> >''' mem(BUCKET);
'''for'''('''int''' i = 0;i < a'''.size()''' ; i++)
'''int''' invers = 0; <font color=green>//кол-во инверсий которые создает элемент a[i]</font>
'''int''' pos = (a[i] - 1)/(MAX / BUCKET);<font color=green>//Определяем в каком кармане должен лежать элемент</font>
'''list<int>::iterator''' it = mem[pos]'''.begin()''';
'''int''' newpos = 0;
'''while'''(it != mem[pos]'''.end()''' && (*it) < a[i] ) <font color=green>//идем до позиции где должен стоять элемент</font>
it++;
newpos++;
invers += mem[pos]'''.size()''' - newpos;<font color=green>//ищем сколько инверсий эленент создает в своем кармане</font>
mem[pos]'''.insert'''( it , a[i] );<font color=green>//вставляем элемент в список</font>
'''for'''('''int''' i = pos + 1 ; i < BUCKET ; i++) <font color=green>//ищем сколько инверсий он создает с элементами в других карманах</font>
invers += mem[i]'''.size()''';
tab_invers[a[i]] = invers;
ans += invers;
'''return''' tab_invers;
'''return''' ans;
Утверждается '''int''' bucket_sort('''vector<int>''' permutation): '''int''' max = число больше permutation.size и из которого можно извлечь целый квадратный корень '''int''' bucket = sqrt(max) '''int''' answer = 0<font color=green> // изначально кол-во инверсий</font> '''list<list<int>>''' bank(bucket) '''for''' i = 0 to permutation.size '''int''' pos = (permutation[i] - 1) / (max / bucket) <font color=green>// Определяем в каком кармане должен лежать элемент</font> '''int''' newPosition = 0 '''while''' newPosition < bank[pos].size '''and''' bank[pos][newPosition] < permutation[i] <font color=green>// идем до позиции где должен стоять элемент permutation[i] </font> newPosition++ answer += bank[pos].size - newPosition <font color=green>// ищем сколько инверсий эленент создает в своем кармане</font> bank[pos].insert(newPosition, permutation[i]) <font color=green>// вставляем элемент в Карман на свою позицию </font> '''for''' i = position + 1 to bucket - 1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font> answer += bank[i].size '''return''' answer В разделе [[Карманная сортировка | карманная сортировка]] доказывается, что она работает за линейное время. Что касается подсчета инверсий, то в приведенной реализации происходит [[Карманная сортировка | карманная сортировка]] в online режиме и вся математическая часть подходит и под этот случай. Следует отметить, что cложность представленного алгоритма есть хотя подсчет с помощью [[Карманная сортировка | карманной сортировки]] выполняется за линейное время, но имеет очень большую константу поэтому подсчет инверсий рассматриваемый выше за <tex>O(n\log n)</tex> работает быстрее .
rollbackEdits.php mass rollback
== Алгоритм построения за O(N) ==
Для построения таблицы инверсий за линейное время воспользуемся [[Карманная сортировка | карманной сортировкой]]. Известно что карманная При [[Карманная сортировка имеет линейную сложность, но только в том случае если элементы равномерно распределены. Т.к. мы ищем кол-во инверсий в перестановке то мы знаем что наши элементы встречаются единожды , а следовательно равномерно распределены. При | карманной сортировке ]] нужно определить карман '''<tex>B'''</tex>, в который попадет текущий элемент. Затем найти количество число элементов в старших карманах относительно '''<tex>B'''</tex>. Потом аккуратно подсчитать количество элементов, больших текущего в кармане '''<tex>B'''</tex>. Карман '''<tex>A''' </tex> считается старшим для кармана '''<tex>B'''</tex>, если любой элемент из '''<tex>A''' </tex> больше любого элемента из '''<tex>B'''</tex>.
== Алгоритм восстановления ==
