$(10\%)$ Consider an array of length $n$ containing positive and negative integers in random order. Write a $O(n)$ program that rearranges the integers so that the negative integers appear before the positive integers.