У меня есть набор данных, который представляет собой ряд объектов, расположенных в двумерной сетке. Я знаю, что у меня строгий порядок, увеличивающийся по мере того, как вы идете слева направо в каждом ряду, и увеличивающийся сверху вниз в каждом столбце. Например,
- 1 2 3
- 4 6 7
- 5 8 9
Можно ли улучшить наивную сортировку для линейной сортировки всего набора данных (как измерено в сравнениях)?
Что насчет nd наборов данных? Произвольные конечные наборы данных с подмножеством сравнений известны?
ds.algorithms
total-ordering
sorting
Захари Вэнс
источник
источник
Ответы:
Легко доказать нижнюю границу Ω (n 2 log n) для этой задачи (в модели сортировки сравнения): если элемент в позиции (i, j) всегда находится на расстоянии 1/2 от i + j, то сетка диагонали не зависят друг от друга, и отсортированный порядок в пределах каждой диагонали сетки является произвольным. Таким образом, при этом ограничении общее число возможных упорядочений представляет собой произведение (по всем диагоналям сетки) факториалов на длину диагоналей, которое экспоненциально по n 2 log n.
То есть стандартные алгоритмы сортировки сравнения асимптотически оптимальны для сеток, упорядоченных, как вы описываете.
источник
Если я правильно понимаю проблему (а может и нет, не стесняйтесь сказать мне, если я не знаю), вы хотите преобразовать 2D-сетку в отсортированный 1D-массив, тогда как каждая строка и столбец уже отсортированы в 2D-сетке?
Первым элементом в списке в этом случае должен быть верхний левый угол ((0,0) по определению проблемы). После этого он должен быть элементом (1,0) или (0,1), так как все остальные по определению будут больше, чем эти.
Вы можете обобщить, сказав, что следующий наименьший элемент в сетке всегда находится непосредственно под уже использованным элементом (или краем сетки), а также справа от уже использованного элемента (или края сетки), так как оба определено, чтобы быть меньше, чем это. Поэтому на каждой итерации вы должны учитывать только наименьшее значение, которое удовлетворяет этому требованию.
Вы можете хранить возможные кандидаты в отсортированном порядке по мере их нахождения (не более двух будут доступны за одну итерацию), и на каждой итерации проверять новые доступные значения (если они есть). Если они ниже, чем самый низкий из предыдущих кандидатов, сразу же добавьте их в список и повторите, в противном случае добавьте самого низкого предыдущего кандидата и сравните со следующим самым низким и т. Д.
К сожалению, я не претендую на то, чтобы быть в состоянии предоставить точную сложность этого, и при этом я не утверждаю, что это наиболее эффективный возможный, это, конечно, кажется лучше, чем наивный подход, и я надеюсь, что я объяснил это достаточно хорошо, чтобы вы поняли.
РЕДАКТИРОВАТЬ: Я думаю, что для nd-сеток, подобных этой, применяется один и тот же базовый принцип, но на каждой итерации доступно до n новых кандидатов, и эти кандидаты должны быть наименьшими неиспользованными элементами в каждом из n измерений на данный момент.
источник