Сортирующий итератор

Перечитайте обьяснение еще раз, там все правильно. Обычный Mergesort сливает части, который делит пополам на каждом этапе рекурсии. Таким образом упрощается поиск минимума между половинами, всего два числа. Тут одноуровневое деление sqrt n по sqrt n частей. Потом минимум среди частей ищется, то ли с поддержанием сортировки, то ли через heap

Можно на ты :)
Надеюсь придет автор и скажет почему его вариант не правильный

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

Тогда нужно чтобы все части были уже отсортированны

Ищем минимум за линейное время от размера части.

А если след. минимум в другой части?

Текущие минимальные значения надо хранить в сбалансированном дереве поиска. Тогда поиск текущего минимально значения моментальный. Асимптотику не улучшит, но скорость чуток улучшит.

Тогда он уже был найден ранее и лежит в указателе на минимум этой части. Алгоритм корректный.

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

Если размер части — корень из n, то они равны, и получится O(n^(3/2)).

проходим по массиву указателей на текущие минимумы и ищем минимум за время O(исходный_размер / размер_части)

И да, выше Legioner написал про дерево.

след. минимум

он уже был найден ранее

Неплохо

Сортирующий итератор (комментарий)
Сортирующий итератор (комментарий)

Это все-таки разные алгоритмы

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

Обсуждаем вроде второй вариант: Сортирующий итератор (комментарий)

{1,2,3, 11,22,33, 111,222,333}

массив минимальных:

{1, 11, 111}

В каждой строчке результат запроса и массив минимальных после после запроса:

1 {2, 11, 111}

2 {3, 11, 111}

3 {inf, 11, 111}

11 {inf, 22, 111}

22 {inf, 33, 111}

33 {inf, inf, 111}

...

Надеюсь, стало чуть понятнее.

Да, корректный. N^(3/2).
Почти всем лором помогли разобраться :3

Кто-то красно-черное делал поверх массива? Там ротации нормально пройдут, не будет сильных сдвигов?

естественный алгоритм «в лоб»:

пара оптимизаций

нихреновый кстати алгоритм сортировки получается :-)

если учесть фокус тер.вера и свойств чисел, при сортировке в неубывающем порядке:

• входящий поток жадно разбивается на M чередующихся неубывающих/убывающих групп
• всего таких групп 2/3 от общего объёма, а на разметку O(1/3 N) памяти (группы-же строго чередуются 1 метка на 2 группы).
• причём группы в неубывающем порядке длиннее где-то на треть
• для случайных данных IRL размер групп не превышает 10 (обозначим как K)

если эти группы (аka сортированные списки) объеденять известными mergesort получаем O(K log M) да ещё N чтобы разметить группы, итого O(N+10 log 2/3N). Плюс если вспомнить, что оценки mergesort даны для список/массивов одинаковой длинны, в данном случае можно принять среднее 5.

Так как группы чередующиеся то при исчерпании группы есть шанс что две смежные с ней можно (за счёт одного сравнения) объеденить то есть уменьшить N не на 1 а на 2, так что множитель под log будет меньше 2/3.

всё выливается в реализацию эффективного слияния сортированных массивов разной длины, а факт их смежности и строгого чередования даёт шанс это оптимизировать.

и ещё он (алгоритм) потенциально хорошо паралеллится.

PS. 4 часа за рулём по спокойной дороге дают возможность подумать об отвлечённых вещах :)

получаешь свой n log n ;-)

Очень хочу поспорить, что там у тебя не будет n log n, но для начала мне не понятен алгоритм. Конкретно, не понятна вот эта часть:

на первом шаге делаешь частичный битовый индекс: B=1 еcли X>X[i+1], и на каждом следующем его поддерживаешь.- каждый проход становится ещё короче

если эти группы (аka сортированные списки) объеденять известными mergesort получаем O(K log M)

Не очень понятно, что значит объединить группы. Если построить отсортированный массив элементов из групп, то на это надо O(KM log M)

Не очень понятно, что значит объединить группы.

сливать. Из набора M сортированных списков размером K получить 1. Оценка по скорости O(K log M).

Если построить отсортированный массив элементов из групп, то на это надо O(KM log M)

множителя K там нет - группы де-факто отсортированы

кстати оценка кол-ва групп как 2/3 N - это худший, то есть максимальный случай. Больше чем 2/3 их быть неможет.

Конкретно, не понятна вот эта часть:

на первом шаге делаешь частичный битовый индекс: B=1 еcли X>X[i+1], и на каждом следующем его поддерживаешь.- каждый проход становится ещё короче

сравниваем смежные элементы исх.массива и запоминаем результат в битовом поле. Теперь цепочка из 1 в нём соотв. группе в «правильном» порядке, цепочка из 0 - группе в обратном. Если после 0 следует 1 - то это локальный минимум, если после 1 следует 0 1 то это локальный максимум.

доп.свойство - если всего один 0 - мы имеем на входе уже отсортированный массив. если всего одна 1 - входящий массив сортирован в обратном порядке.

Остается поддерживать эту структуру при очередном «удалении минимального».

множителя K там нет - группы де-факто отсортированы

Ну так покажи, как это сделать. Алгоритм сортировки слиянием сливает M отсортированных массивов по K элементов за время O(KM log M)

на первый взгляд алгоритм имеет ту-же асимтотику что и mergesort потому как построен вокруг него. Но поддержка информации о группах потенциально даёт BEST O(N), WORST O(N log N) < WORST O`mergesort. Вопрос насколько эффективно поддерживать эти группы, не сжирается ли там весть профит.

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

да плюс, оригинальный посыл ТС «сортирующий итератор» - первое значение получаем через O(N), каждое следующее через T(i)=O(log N - f(i)) и как только получаем признак что остаток сортирован T(i)=O(1); где f(i) - эффект от оптимизаций, заведомо больший 1 (оставшийся объём сокращается на каждой итерации) и неубывающий (число групп стремится от 2/3(N-i) -> 2)

да плюс, оригинальный посыл ТС «сортирующий итератор» - первое значение получаем через O(N), каждое следующее через T(i)=O(log N - f(i)) и как только получаем признак что остаток сортирован T(i)=O(1); где f(i) - эффект от оптимизаций, заведомо больший 1 (оставшийся объём сокращается на каждой итерации) и неубывающий (число групп стремится от 2/3(N-i) -> 2)

сдаётся мне, что если f(i) возрастает то использование даже тупового поиска минимума на каждом шаге даёт T(i)=O(N - f(i)) и в пределе O(n log n)

http://www.naftaliharris.com/blog/2x-speedup-with-one-line-of-code/