Как сортировать целочисленный массив в отрицательную, нулевую, положительную часть без изменения относительной позиции?

Дайте алгоритм O (n), который принимает на вход массив S, затем делит S на три набора: отрицательные, нулевые и положительные. Покажите, как реализовать это на месте, то есть без выделения новой памяти. И вы должны сохранить относительную последовательность чисел. например: {-1, 4, 0, -2, 1, 2} == > {-1, -2, 0, 4, 1, 2}

Я не уверен, выходит ли такое решение. Лучшие решения, которые я могу придумать, следующие:

Решение 1. Используя дополнительный целочисленный массив, перейдите по всему массиву, чтобы получить отрицательные значения, затем 0s, затем положительные.

Решение 2: Не сохраняйте относительную последовательность чисел. Затем зациклируйте массив два раза:

    template <typename Type>  
void Partion(Type *array, int begin, int end, Type v, int &l, int &r) 
{  
    l = begin;  
    for (int i=begin; i!=end; ++i)  
    {  
        if (array[i] < v)  
            swap(array[i], array[l++]);  
    }  
    r = l;  
    for (int j=l; j!=end; ++j)  
    {  
        if (array[j] == v)  
            swap(array[j], array[r++]);  
    }  
}

Ответ 1

Это пример проблемы голландского национального флага изучаемой Эдсгером Дейкстра. Интересно, что решение этой проблемы не существует стабильно, которое работает в O (n) времени и O (1) пространстве (или, по крайней мере, в последний раз, когда я проверял литературу, не было известное решение проблема существует).

Ответ 2

Я не уверен, что это помогает, но требование стабильно разбить на три класса можно свести к проблеме стабильного разбиения на два класса: отделить отрицательный от неотрицательного, а затем положительный от неположительного. Если проблему двух классов можно решить в пространстве O (1) и времени O (n), решение можно применить дважды, чтобы решить исходную задачу.

Ответ 3

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

Если вы смотрите на ситуацию, когда целые числа являются просто ключами для чего-то большего, это, возможно, не так, вы можете захотеть, чтобы нули сохранялись и стабильно разделялись. Но если нет, то здесь две идеи:

Во-первых, ваша проблема идентична проблеме стабильного двоичного раздела.

Алгоритм вашей проблемы, конечно, содержит стабильные двоичные разделы (просто массив без нулей). Напротив, если массив имеет нули, вы все равно можете использовать двоичный раздел для выполнения грязной работы: сканировать прямо через массив, обменивая каждый нуль, с которым вы сталкиваетесь со следующим отрицательным значением (отслеживая, где это было, чтобы вы не делали этого n ^ 2 общее сканирование), в результате чего

[mixed -, +] [возможно дополнительные нули] [mixed 0, +].

Затем вы делаете два двоичных раздела, чтобы получить

[-] [+] [0] [+]

и сдвиньте значения + для получения желаемого результата.

AFAIK с двоичными разделами вы можете выбрать любые два стабильных, на месте и O (n). Таким образом, похоже, что вам удача удалась, но, по-видимому, алгоритм O (n * log n) на месте известен как алгоритм O (n) с использованием области царапин (log).

Во-вторых, если вы можете гарантировать, что количество нулей будет не менее f (n), нули могут компенсировать отсутствие царапины; просто получить стабильное место-место во времени O (n ^ 2/f (n)). В частности, если нули будут по крайней мере некоторой постоянной частью массива, вы получите O (n) время выполнения, просто выполнив эти два шага, пока вы не закончите:

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

Если нули столь же многочисленны, как и другие типы, это делается после выполнения 1 затем 2, затем 1 снова.

Ответ 4

Нельзя ли это сделать, просто используя любую "стабильную сортировку", выполненную с помощью пользовательского сравнения, который проверяет только знак?

Edit:
Нет, что O (n log n).

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

j=0;
for (i=0;i<N;i++) {
  if (A[i]) {
     A[j++]=A[i];
  }
}
while (j<N) {
   A[j++]=0;
}

Теперь вы можете игнорировать последний раздел, и проблема становится поиском алгоритма O (n) для устойчивого раздела вокруг 0. К сожалению, функция stable_partition из С++ stl имеет только O (n) сравнения, но O (n log n) свопирует, если дополнительное пространство не доступно.

Однако эта статья: "Стабильное минимальное разбиение пространства в линейном времени" , кажется, указывает, что это возможно в O (n). Я не думаю, что понимаю это достаточно хорошо, чтобы четко изложить это здесь.

Если это работает, последним шагом является вставка нулей обратно между разделами, что также является O (n), так как нули не имеют порядка обслуживания.

Ответ 5

Библиотека С++ имеет stable_partition алгоритм, который требует n сравнений и O (n log n) свопов, когда он запускается на месте.

Как указывает @Ted , проблема требует двух применений этого алгоритма.