question

Devise an algorithm which takes an input array and divides it into three sets: negatives, zeros, and positives. Implement the sort in place and keep the numbers' relative sequence.

Recall the Dutch National Flag problem.

A solution can be derived by slightly modifying a solution to the Dutch National Flag problem. The algorithm works by iterating through the array and essentially sorting from each end. Starting with two pointers, one pointing to the fist integer in the array and the other pointing to the last, we sequentially swap the current digit with one on either end, moving the point one unit to the center.

Thoughts or alternate solution? Let us know in the comments below!

**dutchFlagSort**(int[] inputArray) {
int n_index = 0;
int p_index = inputArray.length - 1;
**for**(int i = 0; i <= p_index;) {
**if**(arr[i] < 0){
**swap**(arr, i, n_index);
n_index++;
i++;
}
**else if**(arr[i] > 0) {
**swap**(arr, i, p_index);
p_index--;
// Note that we don't increment i here because the element
// that was swapped is unknown
}
**else** {
i++;
}
}
}
**swap**(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

Thoughts or alternate solution? Let us know in the comments below!

*Thanks anon.coder & Aaron for pointing out a correction in the code**Also note that this code does not actually keep the relative sequence of number as originally asked. Thanks Benjamin.*