Поиск в массиве

[lily]

Здравствуйте!
Я пытаюсь придумать алгоритм для такой задачи. В неупорядоченном массиве размера n надо найти номера m-1 элементов таких, что в упорядоченном массиве данные элементы делят его на n/m упорядоченных массивов размером m.
Пробовала решать сортировкой, а затем выдавать номера in/m, i=1..m-1, но хочется, чтобы алгоритм работал, не выполняя самой сортировки, то есть за меньшее число шагов.
Посоветуйте, пожалуйста,что-нибудь.

[Werwolf]

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

[незваный гость]

Если по каким то причинам эффективность очень важна (а иначе, и впрямь, лучше сортировать), воспользуйтесь известной задачей о «голандском флаге». Она является поворяющимся шагом быстрой сортировки (qsort, quicksort). Для любого значения $x$ за один проход сегмента массива его можно реорганизовать на зоны $ < x$, $=x$ и $>x$.

Идея проста: выбираем произвольное значение. Делим массив на три зоны. Каждый из наших индексов $ \frac{i\,n}{m}$ попадает в одну из зон. Те, что попали в среднюю — найдены. Если в зоне нет ни одного индекса — забываем про нее. Иначе применяем к ней (и к попадающем в нее индексам) этот же процесс.

В среднем этот алгоритм дает линейное время, но при неудаче — квадратичное. На практике неудачи можно регулировать управляя выбором $x$. Кроме того, маленькие сегменты (меньше 10-15) может быть выгоднее отсортировать полностью каким нибудь пузырьком. Это уж надо на конкретной реализации выяснять.

[lily]

Спасибо, что рассмотрели мою проблему. Мне вообще кажется, что если руководствоваться чем-то типа qsort, то можно даже в худшем случае получить сложность меньше квадратичной.

[незваный гость]

Вы не можете гарантировать, что не будете откусывать по два элемента на каждом проходе (то есть, получать две зоны по одному элементу). Отсюда и проблемы.

[Werwolf]

Еще придумал такое решение: разбиваем весь массив на эти отрезки, а потом в каждом отрезке если есть элемент меньший за левый и/или больший за правый, то меняем его местами с соответствующим. И так до тех пор, пока ничего менять не приходится. Только кажется сложность будет не меньше квадратической (правда и не больше, потому что за квадратическое время массив сортируется). Вообще кажется, что получить сложность лучше n log n (не знаю точно, но в худшем случае не придется ли массив в любом случае сортировать?) не выйдет.

[PAV]

Если данные берутся не из головы, а поступают из какой-либо реальной системы, то, возможно, они могут быть более-менее хорошо описаны некоторым распределением (надо проанализировать данные). Тогда можно взять в качестве границ областей соответствующие квантили, что может дать распределение по группам, близкое к равномерному.