Переупорядочить массив в отрицательных числах, ноль, а затем порядок положительных чисел

Дан arr[ ] размера N , содержащий положительные, отрицательные целые числа и один ноль. Задача состоит в том, чтобы переставить массив таким образом, чтобы все отрицательные числа находились слева от 0, а все положительные числа — справа.

Примечание. Не обязательно соблюдать порядок чисел. Если возможных ответов несколько, выведите любой из них.

Примеры:

Input: arr[] = {1, 0, -2, 3, 4, -5, -7, 9, -3}
Output: -2 -3 -5 -7 0 1 9 3 4 
Explanation: The negative numbers are -2, -5, -7 and -3.

Input: arr[] = {-10, 5, -2, 0, -4, 5, 17, -9, -13, 11}
Output: -10 -2 -4 -13 -9 0 17 5 5 11  

Наивный подход: создайте массив размера N и поместите отрицательные числа в начало и положительные числа в конец. Кроме того, заполните единственное оставшееся место 0.

Временная сложность: O(N)
Вспомогательное пространство: O(N)

Эффективный подход: идея состоит в том, чтобы найти индекс, в котором 0 хранится в массиве. Как только 0 будет найден, считайте этот индекс опорным. Переместите все отрицательные значения в левую часть оси, и, таким образом, значения правой стороны автоматически станут положительными.

Ниже приведена реализация вышеуказанного подхода:

Сложность времени: НА)
Вспомогательное пространство: O(1)