Сортировка массива с использованием множественного сравнения

sokrat

Есть массив a1, ..., aN
Есть оператор сравнения принимающий на вход фиксированное количество элементов (напр. 10) и выдающий сортированную подпоследовательность.
Кто нить знает видел алгоритм с сортировками такого типа сравнения? Или хотя бы как они называются правильно?
Уточнения:
1. Одинаковых элементов в входном массивет нет
2. Оператор сравнения возвращает тот же входной набор, но упорядоченный. Напр cmp(1, 6, 5, 2) вернет (1, 2, 5, 6). Длина оператора фиксированна (некоторое K << N). Сравнения просто двух элементов нет. Использование k-множественного чревато большими расходами на вызов функций сравнения.
3. В реальной задаче k ~ 25, N = 30 000.
4. Оператор сравнения оооочень дорогой. Остальные параметры не важны.

soldatiki

Ну можно merge sort применить. Строится N-арное дерево вместо бинарного.

Vlad128

Ну это ты, конечно, не подумал. Дерево тож бинарное, просто при размере массива меньше 10 вызываем указанную функцию.
В нерекурсивной реализации изначально разбиваем массив на куски длиной 10, потом сливаем, сливаем, сливаем...

vsjshnikova

qsort тоже можно модифицировать.
Выбираем средний элемент, каждый раз сортируем его и 9 еще не обработанных элементов массива, потом идем по отсортированному массивчику и запихиваем его элементы в начало большого массива, пока не встретим выделенный, потом запихиваем элементы в конец.

natunchik

Наверное, зависит от того, можешь ли ты свой оракул использовать именно как оператор сравнения.
На IOI2001 (или 2000) была похожая задачка: массив из разных элементов и функция, принимающая на вход три значения и выдающая их порядок как один инт (типа, от 0 до 5). Правда, там медиану нужно было искать, но не суть. Ну и решения - квиксорт (не инплейс) с двумя пивотами, и каждый элемент определяется в один из трёх интервалов, или, ещё лучше, mergesort, где ты вместо слияния двух списков сливаешь три на каждом уровне. То есть получаешь логарифм не по основанию два, а по основанию три.
Ну вот. Если ты можешь своему "оператору сравнения" скормить не тупо элементы, а массив кортежей "элемент-индекс", после чего найти минимальный элемент (и его индекс) как бы нахаляву (типа сравнение элементов намного дороже сравнения индексов то можно такое делать.
Правда, из формулировки сразу видно, что мы нифига не всю информацию используем, мы по сути работаем с нашим оператором как с оператором "минимум n элементов", который намного меньше информации нам даёт (n альтернатив вместо n!, каждый раз, когда мы очередной элемент вытаскиваем, после первого).
Ну и если нельзя свой индекс подцеплять, тоже непонятно.

Vlad128

короче много текста и решения или толкового совета, как решить нет? Я правильно подытожил?

sokrat

Честно мало что понял (давно сортировками не занимался). При чем тут Оракл?
Задача чисто академическая так сказать: отсортировать массив имея необычный оператор сравнения.
> Если ты можешь своему "оператору сравнения" скормить не тупо элементы, а массив кортежей "элемент-индекс"...
Теоретически скормить можно все что угодно, как это поможет то? Можно считать, что возвращаются отсортированные индексы элементов, а не сами элементы. Не суть важно.
Уточнение: необходимо использовать минимум сравнений, т.к. они достаточно дороги. На все остальное - пофиг.
В связи с тем, что в разделе Development обсуждение более активное, желающих поделиться своими соображениями прошу писать там :)

blackout

При чем тут Оракл?

natunchik

> При чем тут Оракл?
Не оракл, а оракул, лол. Когда у тебя есть какой-то чорный ящик, который умеет быстро выполнять некое сложное действие, в виде реальной внешней железки или, допустим, используя какие-то специфические свойства обрабатываемых объектов, то его принято называть оракулом. Типа, "сортировка с оракулом".
Ну вот, я говорю, один вариант есть - использовать оракул как обобщённый минимум (который для k = 2 эквивалентен сравнению) и сортировку слиянием в k потоков, тогда количество проходов оказывается не log_2(n а log_k(n) и получаешь ускорение в log(k) раз. Но это не очень интересно, хотя и интересней чем та херня, которую предлагает куклюкулюкухуй.
Зато в этом, кстати, есть прямой смысл: обобщённый минимум можно дико быстро считать кучей (heap если она маленькая и вся влезает в кэш первого уровня, а то и в регистры. Возможно, через это можно получить неиллюзорное ускорение.
В программинге действительно интересней, потому что там есть Блайнд, который, судя по всему, Знает Правильный Ответ, даже два!

Vlad128

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

kiritsev

Знает Правильный Ответ, даже два!
=)
это очевидно! если при мердже засовывать с сортировщик по несколько элементов из каждой кучи, то и забирать можно больше чем по одному.

blackout

Можно сделать так. Пусть есть k отсортированных последовательностей произвольной длины. Теперь:
1) Отсортируем первые (наибольшие) элементы этих последовательностей.
2) Выберем b наибольших чисел из первой (с наибольшим первым элементом b - 1 из второй и т.д., всего примерно b*b/2 < k и сравним их. Любое из оставшихся чисел меньше, чем некоторые b чисел из выбранных. Значит первые b чисел из выбранных являются также и первыми b числами из всех. Можно принять, что b = sqrt(2k).
Таким образом N чисел разделенных на k отсортированных последовательностей можно отсортировать за
2*N/(sqrt(2k = sqrt(2)*N/(sqrt(k
Значит S(N) = k*S(N/k) + sqrt(2)*N/(sqrt(k и немного посчитав получим, что:
S(N) = O(log(N)*N/sqrt(k. По N это тот же квиксорт, но есть еще один множитель, зависящий от k.

kiritsev

фигня. делить надо всё равно на два кучи. логарифм это конечно хорошо, но деление круче.
k-арный сортировщик сольёт две упорядоченные поседовательности по n в каждой худшем за 2*n/k применений.

blackout

Можно делать сортировку слиянием но сливать сразу k кусков по N/k штук. Сливаем первые два куска, вторые 2 куска и т.д., но на каждый шаг делаем только 1 сравнение. То есть за N/k шагов имеем k/2 куч по 2N/k, еще за N/k - k/4 куч по 4N/k. То есть на все слияние надо log(k)*N/k и весь алгоритм log_k(N)*(N/k)*log_2(k) = log(N)*(N/k).
Ты это имеешь ввиду? (up нет не это)

blackout

Посчитал, получается что не важно сколько последовательностей сливать 2 или k, в любом случае будет log(N)*(N/k).

kiritsev

сливай строки:
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
ну и столбцы попробуй (взависимости от того что ты там придумал)

blackout

сливай строки:
Сливаем 1 1 1 1 с 2 2 2 2 и 3 3 3 3 с 4 4 4 4, сравниваем (1 2 3 4) но используем только результаты (1 2) и (3 4). То есть для каждой пары строк получается обычный мердж. Через семь шагов будет 2 строки 2 2 2 2 1 1 1 1 и 4 4 4 4 3 3 3 3. Их сливаем беря уже по 2 элемента из каждой строки, потом бы брали по 4 из каждой строки и т.д.

antcatt77

в любом случае будет log(N)*(N/k).
для k=2, в два раза лучше, чем штатные сортировки(например, qsort)?

Vlad128

у qsort асимптотика не NlogN

blackout

для k=2, в два раза лучше, чем штатные сортировки(например, qsort)?
Это без констант.

Vlad128

на число сравнений у «штатных» сортировок константа 1. Например, у пузырька, heap, merge.

blackout

на число сравнений у «штатных» сортировок константа 1
Что ты имеешь в виду?

Vlad128

То, что те сортировки, которые я перечислил выполняют не более, NlogN сравнений. Без всяких O. константа там только в числе присваиваний.

vsjshnikova

del

blackout

И что? В общем случае 100*N/k лучше чем N, поэтому константы я не подсчитывал.

vsjshnikova

Вероятно, он имеет в виду, что обычные merge, heap требуют асимптотически [math]$$1\cdot n\log n$$[/math], и qsort в среднем столько же.

vsjshnikova

В нашем случае k - заранее заданная константа, и поэтому 100*N/k может быть хуже N

blackout

заранее заданная константа, и поэтому 100*N/k может быть хуже N
Может она и задана, но ты ее не знаешь. А так как в условии задачи про k вообще ничего не сказано, то скорее всего 100*N/k все-таки лучше.

vsjshnikova

Может она и задана, но ты ее не знаешь. А так как в условии задачи про k вообще ничего не сказано, то скорее всего 100*N/k все-таки лучше.
Есть массив a1, ..., aN
Есть оператор сравнения принимающий на вход фиксированное количество элементов (напр. 10) и выдающий сортированную подпоследовательность.

soldatiki

Дерево тож бинарное, просто при размере массива меньше 10 вызываем указанную функцию.
Ну здрасьте! Имеено и прикол в том, что сливаем не два, а N сортированных массивов меньшей длины. При этом сортировка "лидеров" происходит за O(1 а не O(N) как при использовании operator <. Правда, выигрыш тут не сильный все равно: сортировка используется как взятие минимума.

Vlad128

Да, уже разобрались. Все-таки лучшим признано разделение на две части и более эффективное сливание.
Все равно не была доказана оптимальность ни одного из предложенных решений, так как в одном случае используют соритровку как минимум, в другом - сортируют уже частично отсортированные участки.
Оставить комментарий
Имя или ник:
Комментарий: