Как я могу пересортировать массив на месте, чтобы поместить четные индексированные элементы перед нечетными?
У меня есть отсортированный массив, который я хочу отсортировать так, чтобы ранее четные индексированные элементы были в начале, за которыми следуют нечетные индексированные элементы.
Пример: [a, b, c, d, e, f] => [a, c, e, b, d, f],
Я также (отдельно) хочу сделать наоборот, сначала с нечетными индексами:
Пример: [a, b, c, d, e, f] => [b, d, f, a, c, e],
Я знаю, что могу создать отдельные нечетные / четные массивы, а затем объединить их, но производительность является ключевым фактором, и я пытаюсь найти одноконтурное решение на месте, которое позволяет избежать выделения и использования временных массивов.
Контекст:
Я рекурсивно ищу игровое дерево ходов (минимакс с альфа-бета) и пытаюсь реализовать Lazy SMP, где я ищу те же позиции в других потоках, но пробую ходы в несколько разных порядках, сохраняя результаты в общем доступе (транспонирование), чтобы повысить эффективность основной поисковой цепочки.
Разъяснения:
Начальный массив уже отсортирован, и я хочу, чтобы порядок в четных / нечетных индексах сохранялся. То есть, я не хочу просто сгруппировать четности и шансы вместе и в итоге сказать [f, b, d, e, c, a],
Кроме того, я сортирую строго по значению индекса, а не по элементу, хранящемуся там. Таким образом, любые методы, использующие предикаты поиска по значению элемента, не будут работать.
И хотя я пишу на C#, я не хочу использовать LINQ, так как мне нужно, чтобы код был переносимым на системы без LINQ.
Я надеюсь, что есть способ зациклить массив один раз и выполнить серию перестановок элементов так, чтобы я закончил с порядком, который я описал. Я пробовал это на бумаге, но пока ничего не получил.
Пояснения 2:
Я обновил примеры буквами вместо цифр и поменял местами нечетные / четные примеры, когда получил их задом наперед. Я хочу оба.
В конечном итоге я пытаюсь смоделировать циклический просмотр исходного массива, но пропускаю все остальные элементы и все еще просматриваю каждый элемент. С двумя циклами я бы сделал следующее:
// Case 1: Regular order
for (int i = 0; i < items.Length; i ++)
{
// Process
}
// Case 2: Even indexes first
for (int i = 0; i < items.Length; i += 2)
{
// Process
}
for (int i = 1; i < items.Length; i += 2)
{
// Process
}
// Case 3: Odd indexes first
for (int i = 1; i < items.Length; i += 2)
{
// Process
}
for (int i = 0; i < items.Length; i += 2)
{
// Process
}
Обработка в цикле достаточно сложна, так как она вызывает эту функцию рекурсивно, имеет отдельные условия для преждевременного завершения цикла и т. Д., Поэтому я не хочу дублировать ее и / или помещать в другую функцию.
Поэтому вместо того, чтобы иметь два цикла или один сложный цикл, который обрабатывает все три случая, я бы предпочел просто предварительно отсортировать элементы.
Пояснения 3:
Мне нужно что-то, что обрабатывает все три случая, поддерживает массив любого размера (не только число элементов) и не загромождает содержимое цикла поиска игры. Я думал, что предварительная сортировка на месте до того цикла была лучшим вариантом.
В конце концов я решил отказаться от предварительной сортировки на месте и расширить List с помощью специального итератора, который пропускает элементы. Я добавил свой код ниже, хотя я не буду отмечать его как ответ, поскольку технически это не то, что я просил.
Спасибо всем за помощь. (И если кто-то опубликует единый цикл, решение на основе подкачки на месте, которое работает для любого количества элементов, я буду рад принять его в качестве ответа.)
7 ответов
Вот алгоритм, который делает это по одному пути в массиве. Предполагается, что массив имеет четное количество элементов Nи что мы можем выделить bool[N/2] массив:
static void OddEvenSwap(int[] data) {
int n = data.Length / 2;
int p = 0;
var seen = new bool[n];
while (true) {
int last = data[p];
do {
var tmp = data[p];
data[p] = last;
last = tmp;
if (p < n) {
seen[p] = true;
}
p = (p/2) + (p%2 == 0 ? n : 0);
} while (p >= n || !seen[p]);
data[p] = last;
while (p != n && seen[p]) {
p++;
}
if (p == n) {
break;
}
}
}
Вот краткое объяснение того, как это работает:
- Учитывая исходный индекс
pэлемента, мы всегда можем вычислить его целевой индекс напрямую - Начните с нулевого индекса, вычислите его индекс назначения, переместите элемент туда и продолжите от индекса назначения до следующего пункта назначения
- Отметьте все индексы в нижней половине, которые мы посетили
- В конце концов мы вернемся к индексу, который мы видели; поместите туда последний элемент, потому что мы закончили цикл
- Найдите следующий индекс из нижней половины, который мы еще не посетили
- Как только мы исчерпали все индексы, мы сделали
Demo.
Примечание. Если вы запустите этот алгоритм несколько раз, вы сможете избежать перераспределения seen[] массив, выделив его один раз в максимальном размере, а затем просто заполнив его falses.
В конечном итоге я пытаюсь смоделировать циклический просмотр исходного массива, но пропускаю все остальные элементы и все еще просматриваю каждый элемент.
В этом случае вам вообще не нужна сортировка: используйте специализированную пошаговую функцию, которая обходит нечетные индексы, опережая четные, или наоборот.
Этот подход работает для любой четной стоимости N (длина массива).
int N = 28;
Console.WriteLine("Odd before even");
for (var i = 1 ; i != N ; i = (i + 2) % (N+1)) {
Console.Write("{0} ", i);
}
Console.WriteLine("Even before odd");
for (var i = 1 ; i != N ; i = (i + 2) % (N+1)) {
// The formula is a bit complicated to avoid ternary:
Console.Write("{0} ", -2*(i%2)+i+1);
}
Demo.
Это оказалось довольно интересной проблемой. Сначала отметим, что тривиальное решение O(N^2) уже опубликовано, поэтому теперь вопрос в том, можем ли мы добиться большего успеха.
Моя лучшая попытка на данный момент: просто бросать шансы и четности там, где вы хотите, а затем сортировать каждую половину массива.
static void swap<t>(ref T a, ref T b) {
var temp = a;
a = b;
b = a;
}
static void ThrowInHalf<T>(T[] arr) {
for (var i = 0 ; i < arr.Length/2; i+=2) {
swap(arr[i],arr[L/2+i+1];
}
}
После сортировки все четы должны быть во втором тайме, а шансы в первом. Проблема разбивается так, что вы получаете точно такую же проблему - четные индексы подмассива должны предшествовать нечетным, поэтому вы можете снова запустить алгоритм и т. Д., Каждый раз работая с половиной массива, классическим O(nlog n). Конечно, вы можете просто пересортировать каждую половину массива за те же затраты времени выполнения (не так просто в c# как и другие языки, но есть варианты).
Другие попытки линейного времени
Я попробовал еще две вещи, но застрял. Первый:
static void sortAttempt1<T>(T[] array) {
for(var i=0,inc=1; i+inc<array.Length; ++i) {
swap(array[i],array[i+inc]);
++inc;
}
}
Это будет первая половина, как вы хотите. Мне еще предстоит найти алгоритмический способ увидеть, как переупорядочить вторую половину, но похоже, что есть структура, которую можно вычислить, и она зависит от того, какая степень 2 равна длине массива.
Вторая попытка (версия, которую я вижу, была впервые опубликована dasblinkenlight):
static int next(int i) {
if(i&1)
return i/2;
return (L+i)/2;
}
static int cycle<T>(T[] array,int start) {
var perms = 0;
var keep = array[start];
var n = next(start);
while(n != start) {
swap(array[n],keep);
n = next(n);
++perms;
}
return perms;
}
void sortAttempt2<T>(T[] array) {
int perms = 0;
for(int start = 0; perms<array.Length-1; start+=2) {
perms += cycle(array,start);
}
}
Это решение запускает циклы в массиве. Например:
0,1,2,3,4,5,6,7,8
Начиная с индекса 0, разместите данные именно там, где вы хотите, затем возьмите то, что вы только что стерли, и поместите его в нужное место и т. Д., Пока не закроете круг (next функция сообщает нам, куда именно должен идти индекс):
0->4->6->7->3->1->0
Таких, что вы получите:
1,3,2,7,0,5,4,6,8
Теперь запустите цикл, начиная с индекса 2 (который все еще на месте)
2->5->2
сортировка как мы хотим в O(n). Проблема в том, чтобы найти, где начать следующий цикл. start+2 работает до массива длиной 21, но после начинает сбой на растущем количестве входов. Я не смог найти решение O(1) в пространстве и времени, чтобы получить следующую итерацию для общего случая.
Краткое изложение того, что у меня есть
- Решение этого может быть сделано как минимум за O(nlog n) раз.
- Я предоставил еще две попытки первоначального решения.
Любой, у кого есть идея, буду очень признателен им. Включая, конечно, доказательство нижней границы во времени. Обратите внимание на предложения по выделению массива размера, который зависит от N, строго запрещено.
С помощью LINQ легко отсортировать массив. Чтобы отсортировать по нечетному / четному, просто вернуть значение на основе i % 2 из предиката, который вы поставляете OrderBy(),
var list = new int[] { 1, 2, 3, 4, 5, 6 };
var sorted = list.OrderBy( i => i % 2 );
Console.WriteLine(string.Join(",",sorted));
Выход:
2,4,6,1,3,5
Если тебе надо sorted чтобы быть массивом, просто добавьте ToArray():
var list = new int[] { 1, 2, 3, 4, 5, 6 };
var sorted = list.OrderBy( i => i % 2 ).ToArray();
Console.WriteLine(string.Join(",",sorted));
И если вам нужно обновить исходный массив ("на месте"), вы можете скопировать его обратно в массив следующим образом:
var list = new int[] { 1, 2, 3, 4, 5, 6 };
var sorted = list.OrderBy( i => i % 2 );
sorted.Select( (n, i) => list[i] = n ).Last();
Console.WriteLine(string.Join(",",list));
Обратите внимание, что это решение требует сортировки исходного массива. Если это не так, вы можете добавить шаг сортировки с помощью дополнительного вызова LINQ:
var list = new int[] { 6, 5, 4, 3, 2, 1 };
var sorted = list.OrderBy( i => i).OrderBy( i => i % 2 );
sorted.Select( (n, i) => list[i] = n ).Last();
Console.WriteLine(string.Join(",",list));
Это будет делать сортировку по месту:
static void SortOddEven<T>(T[] source)
{
for (var start = 0; start < source.Length; start++)
{
for (var swap = start; swap < source.Length - start - 1; swap += 2)
{
var temp = source[swap];
source[swap] = source[swap + 1];
source[swap + 1] = temp;
}
}
}
И соответствующая четно-нечетная сортировка в основном такая же:
static void SortEvenOdd<T>(T[] source)
{
for (var start = 1; start < source.Length; start++)
{
for (var swap = start; swap < source.Length - start; swap += 2)
{
var temp = source[swap];
source[swap] = source[swap + 1];
source[swap + 1] = temp;
}
}
}
В разъяснении я сказал, что конечный результат, который я искал, - это способ итерации, пропуская каждый второй элемент.
Я предполагал, что сортировка на месте будет более быстрым / чистым подходом, но в итоге я просто закончил расширением List следующим образом:
static class ListExtensions
{
public static IEnumerable<T> GetEnumerableByOrderType<T>(this List<T> items, OrderType orderType)
{
int i = orderType == OrderType.SkipOffset && items.Count > 1 ? 1 : 0;
int count = 0;
while (i < items.Count)
{
yield return items[i];
count++;
i += orderType == OrderType.Default ? 1 : 2;
if (count < items.Count && i >= items.Count)
{
i = orderType == OrderType.SkipOffset ? 0 : 1;
}
}
}
}
public enum OrderType
{
Default = 0,
Skip, // Starts at 0
SkipOffset // Starts at 1
}
Тогда я смог просто изменить:
List<Move> moves = GetSortedMoves();
foreach (Move in moves)
{
// Processing
}
чтобы:
List<Move> moves = GetSortedMoves();
foreach (Move in moves.GetEnumerableByOrderType(OrderType.Skip))
{
// Processing
}
Он работает со всеми тремя типами заказа и с любым размером списка.
Вы можете попробовать это, это почти в 3 раза быстрее, чем OrderBy/ToArray для массива с миллионом элементов.
for (int i = 0; i < masiv.Length; i++)
{
if (i % 2 != 0) //or if (i % 2 == 0)
{
int j = i / 2;
int tmp = masiv[i];
masiv[i] = masiv[j];
masiv[j] = tmp;
}
}
QuickSort(masiv, masiv.Length / 2, masiv.Length - 1);
//Quicksort method
public static void QuickSort(int[] a, int start, int end)
{
if (start >= end)
{
return;
}
int num = a[start];
int i = start, j = end;
while (i < j)
{
while (i < j && a[j] > num)
{
j--;
}
a[i] = a[j];
while (i < j && a[i] < num)
{
i++;
}
a[j] = a[i];
}
a[i] = num;
QuickSort(a, start, i - 1);
QuickSort(a, i + 1, end);
}