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

Question

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

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

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

Решение 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++]);  
    }  
} 

Answer 1

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

Answer 2

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

Answer 3

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

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

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

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

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

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

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

Редактировать:
Нет, это 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 function из c ++ stl имеет только O (n) сравнений, но O (n log n) поменяется местами, если нет свободного места.

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

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