i.e.
Input : [-1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2]
Output : [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]
We will consider the following:
1. Time complexity
2. Space requirement
3. Stability
If we treat negative numbers as 0 and positive numbers as 1, this is a 0-1 sorting problem.
Algorithm 1: Loop through the array from both ends, swap negatives with positives if they are misplaced.
Time Complexity: O(N)
Space Requirement: O(1)
But not stable.
static public class NegativePositiveSwapSorter extends NegativePositiveBaseSorter implements Sorter {
public void sort(int[] a) {
if (a==null || a.length<=1)
return;
int i = 0, j = a.length-1;
while (i<=j) {
while (a[i]<0 && i<=j) i++;
while (a[j]>0 && i<=j) j--;
if (i<j ) swap(a, i, j);
i++;
j--;
}
}
}
Algorithm 2: Loop through the array, count the number of negatives (z). Scan the array the second time, and maintain two counters c0 and c1. c0 counting the number of negatives and c1 sums up the number positives to the left of the current position.
If a[i]<0, final position is (a[i]<0 ? 0 : 1 ) * z + c0
If a[i]<0, final position is (a[i]<0 ? 0 : 1 ) * z + c1
Time Complexity: O(N)
Space Requirement: O(N)
Stable static public class NegativePositiveCountSorter extends NegativePositiveBaseSorter implements Sorter {
public void sort(int[] a) {
if (a==null || a.length<=1) return;
// z is count of negatives
int z=0;
for (int i=0; i<a.length; i++) {
if (a[i]<0) z++;
}
int c0=0, c1=0;
int [] c = new int[a.length];
for (int i=0; i<a.length; i++) {
int idx=0;
if (a[i]<0) {
idx= (a[i]<0 ? 0 : 1 ) * z + c0;
c0++;
} else {
idx= (a[i]<0 ? 0 : 1 ) * z + c1;
c1++;
}
c[idx] = a[i];
}
System.arraycopy(c, 0, a, 0, a.length);
}
}
Algorithm 3: Loop through the array, and swap negative number block and positive number block with rotating (Juggling)
Time Complexity: O( N0 x N1 )
Space Requirement: O(1)
Stable
static public class NegativePositiveSorterViaRotationWithJuggling extends NegativePositiveBaseSorter implements Sorter {
public void sort(int[] a) {
if (a==null || a.length<=1)
return;
int start = 0, mid=0, end=0, num = 1;
do {
start = skipNegBlock(a, start);
mid = skipPosBlock(a, end==0? start : end);
end = skipNegBlock(a, mid);
num = rotateleftByJuggling(a, start, mid-start, end-start);
} while (num>0);
}
}
Here is the transformation:
Step: 1 Array: [-1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2]
Step: 2 Array: [-1, -9, 2, 1, 12, 3, -4, 4, -3, 21, 52, 4, -2]
Step: 3 Array: [-1, -9, -4, 2, 1, 12, 3, 4, -3, 21, 52, 4, -2]
Step: 4 Array: [-1, -9, -4, -3, 2, 1, 12, 3, 4, 21, 52, 4, -2]
Step: 5 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]
Step: 6 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]
Algorithm 4: Loop through the array, and swap negative number block and positive number block with double reverse
Time Complexity: O( N0 * N1 )
Space Requirement: O(1)
Stable
static public class NegativePositiveSorterViaBlockSwapWithReverse extends NegativePositiveBaseSorter implements Sorter {
public void sort(int[] a) {
if (a==null || a.length<=1)
return;
int start = 0, mid=0, end=0, num = 1;
do {
start = skipNegBlock(a, start);
mid = skipPosBlock(a, end==0? start : end);
end = skipNegBlock(a, mid);
num = swapBlockWithReverse(a, start, mid, end);
} while (num>0);
}
}
Here is the transformation:
Step: 1 Array: [-1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2]
Step: 2 Array: [-1, -9, 2, 1, 12, 3, -4, 4, -3, 21, 52, 4, -2]
Step: 3 Array: [-1, -9, -4, 2, 1, 12, 3, 4, -3, 21, 52, 4, -2]
Step: 4 Array: [-1, -9, -4, -3, 2, 1, 12, 3, 4, 21, 52, 4, -2]
Step: 5 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]
Step: 6 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]Algorithm 5: Loop through the array, Loop through the array, and swap negative number block and positive number block with rotating.
Time Complexity: O( n log(n) )
Space Requirement: O(1)
Stable
public void sort(int[] a) {
if (a==null || a.length<=1)
return;
int start = 0, mid=0, end=0, num = 1;
do {
start = skipNegBlock(a, start);
mid = skipPosBlock(a, end==0? start : end);
end = skipNegBlock(a, mid);
num = rotateleft(a, start, mid-start, end-start);
} while (num>0);
}
Here is the transformation:
Step: 1 Array: [-1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2]
Step: 2 Array: [-1, -9, 2, 1, 12, 3, -4, 4, -3, 21, 52, 4, -2]
Step: 3 Array: [-1, -9, -4, 2, 1, 12, 3, 4, -3, 21, 52, 4, -2]
Step: 4 Array: [-1, -9, -4, -3, 2, 1, 12, 3, 4, 21, 52, 4, -2]
Step: 5 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]
Step: 6 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]Here is the entire source code:
package com.lei.algorithm;
import java.util.Arrays;
/**
*
* Algorithms to sort negatives in front of positives for an integer array
*
* @author stones333
*
*/
public class NegativePositiveIntergerSorter {
/**
* Sorter interface
*
*/
static public interface Sorter {
void sort(int[] a);
void print(int[] a);
}
/**
* Base class for Sorter with utility methods
*
* @author stones333
*
*/
static public abstract class NegativePositiveBaseSorter implements Sorter {
/**
* swap array item position i and j
*
* @param a
* @param i
* @param j
*/
public void swap(int[] a, int i, int j) {
a[i] = a[i] + a[j];
a[j] = a[i] - a[j];
a[i] = a[i] - a[j];
}
/**
* reverse the array a[] between position i and j.
* @param a
* @param i, inclusive
* @param j, exclusive
*/
public void reverse(int[] a, int i, int j) {
while (i<j) {
swap(a, i, j);
i++;
j--;
}
}
/**
* advance array index by n position.
*
* @param a
* @param start
* @param n
* @return
*/
public int advance(int[] a, int start, int n) {
return ( (start+n)>a.length) ? a.length : (start+n);
}
/**
*
* swap array block of n item starting from position i and j
*
* @param a
* @param i
* @param j
* @param n
*/
public void swap(int[] a, int i, int j, int n) {
if (i==j|| n==0) return;
for (;n>0; n--)
swap(a, i++, j++);
}
/**
* skip the negative block until positive number
*
* @param a
* @param begin
* @return
*/
public int skipNegBlock(int[] a, int begin) {
int start=begin;
while (start<a.length && a[start]<0 ) start++;
return start;
}
/**
* skip the positive block until negative number
*
* @param a
* @param begin
* @return
*/
public int skipPosBlock(int[] a, int begin) {
int start=begin;
while (start<a.length && a[start]>0 ) start++;
return start;
}
/**
* swap the blocks, the first from start to mid-1, with the second from mid to end-1
*
* @param a
* @param start
* @param mid
* @param end
* @return
*/
public int swapBlockWithReverse(int[] a, int start, int mid, int end) {
reverse(a, start, mid-1);
reverse(a, mid, end-1);
reverse(a, start, end-1);
return end-mid;
}
public void pickAndSwapBlock(int[] a, int start, int mid, int end) {
while (start<mid && a[start]<0 ) start++;
int start2=mid;
while (start2<end && a[start2]<0 ) start2++;
if (start<=mid && start2>=mid && start2<=end) {
swapBlockWithReverse(a, start, mid, start2);
}
}
/**
* print the array content
*
* @param a
*/
public void print(int[] a) {
System.out.println( "Array: " + Arrays.toString(a) );
}
/**
* print the array content with step number
*
* @param step
* @param a
*/
public void print(int step, int[] a) {
System.out.println( "Step: " + step + " Array: " + Arrays.toString(a) );
}
}
/**
*
* Algorithm 1: Loop through the array from both ends, swap negatives with positives if they are misplaced.
*
* Time Complexity: O(N)
* Space Requirement: O(1)
* Not stable
*
* @author stones333
*
*/
static public class NegativePositiveSwapSorter extends NegativePositiveBaseSorter implements Sorter {
public void sort(int[] a) {
if (a==null || a.length<=1)
return;
int i = 0, j = a.length-1;
while (i<=j) {
while (a[i]<0 && i<=j) i++;
while (a[j]>0 && i<=j) j--;
if (i<j ) swap(a, i, j);
i++;
j--;
}
}
}
/**
*
* Algorithm 2: Loop through the array, count the number of negatives (z). Scan the array the second time, and maintain two counters c0 and c1.
* c0 counting the number of negatives and c1 sums up the number positives to the left of the current position.
*
* If a[i]<0, final position is (a[i]<0 ? 0 : 1 ) * z + c0
* If a[i]<0, final position is (a[i]<0 ? 0 : 1 ) * z + c1
*
*
* Time Complexity: O(N)
* Space Requirement: O(N)
* Stable
*
* @author stones333
*
*/
static public class NegativePositiveCountSorter extends NegativePositiveBaseSorter implements Sorter {
public void sort(int[] a) {
if (a==null || a.length<=1) return;
// z is count of negatives
int z=0;
for (int i=0; i<a.length; i++) {
if (a[i]<0) z++;
}
int c0=0, c1=0;
int [] c = new int[a.length];
for (int i=0; i<a.length; i++) {
int idx=0;
if (a[i]<0) {
idx= (a[i]<0 ? 0 : 1 ) * z + c0;
c0++;
} else {
idx= (a[i]<0 ? 0 : 1 ) * z + c1;
c1++;
}
c[idx] = a[i];
}
System.arraycopy(c, 0, a, 0, a.length);
}
}
/**
*
* Algorithm 3: Loop through the array, and swap negative number block and positive number block with rotating (Juggling)
*
* Time Complexity: O( N0 x N1 )
* Space Requirement: O(1)
* Stable
*
* @author stones333
*
*/
static public class NegativePositiveSorterViaRotationWithJuggling extends NegativePositiveBaseSorter implements Sorter {
/**
* return gcd of i and j
*
* @param i
* @param j
* @return
*/
public int gcd( int i, int j ) {
if ( i == 0 ) return j;
if ( j == 0 ) return i;
while ( i != j ) {
if ( i > j )
i -= j;
else
j -= i;
}
return i;
}
/**
*
* rotates array a[] of size n by d elements, start from position st
*
* Steps:
* 1. A is the left subarray, B is the right subarray — that is, the starting point is AB
* 2. If A is shorter, divide B into Bl and Br, such that length of Br equals the length of A
* 3. Swap A and Br to change ABlBr into BrBlA
* 4. Recur on the two pieces of B
* 5. Once A and B are of equal lengths, swap A and B
*
* @param a
* @param st
* @param d
* @param n
* @return number of items rotated
*/
public int rotateleftByJuggling(int a[], int st, int d, int n) {
if (d == 0 || d == n)
return 0;
int i, j, k, temp;
for (i =0; i < gcd(d-st, n-st); i++)
{
/* move i-th values of blocks */
temp = a[i+st];
j = i;
while(true)
{
k = j + d;
if (k >= n)
k = k - n;
if (k == i) break;
a[j+st] = a[k+st];
j = k;
}
a[j+st] = temp;
}
return d;
}
public void sort(int[] a) {
if (a==null || a.length<=1)
return;
int step=1;
this.print(step++, a);
int start = 0, mid=0, end=0, num = 1;
do {
start = skipNegBlock(a, start);
mid = skipPosBlock(a, end==0? start : end);
end = skipNegBlock(a, mid);
num = rotateleftByJuggling(a, start, mid-start, end-start);
this.print(step++, a);
} while (num>0);
}
}
/**
*
* Algorithm 4: Loop through the array, and swap negative number block and positive number block with double reverse
*
* Time Complexity: O( N0 x N1 )
* Space Requirement: O(1)
* Stable
*
* @author stones333
*
*/
static public class NegativePositiveSorterViaBlockSwapWithReverse extends NegativePositiveBaseSorter implements Sorter {
public void sort(int[] a) {
if (a==null || a.length<=1)
return;
int start = 0, mid=0, end=0, num = 1;
do {
start = skipNegBlock(a, start);
mid = skipPosBlock(a, end==0? start : end);
end = skipNegBlock(a, mid);
num = swapBlockWithReverse(a, start, mid, end);
} while (num>0);
}
}
/**
*
* Algorithm 5: Loop through the array, and swap negative number block and positive number block with rotating
*
* Time Complexity: O( N0 x N1 )
* Space Requirement: O(1)
* Stable
*
* @author stones333
*
*/
static public class NegativePositiveSorterViaRotationWithBlockSwap extends NegativePositiveBaseSorter implements Sorter {
/**
*
* rotates array a[] of size n by d elements, start from st
*
* Steps:
* 1. A is the left subarray, B is the right subarray — that is, the starting point is AB
* 2. If A is shorter, divide B into Bl and Br, such that length of Br equals the length of A
* 3. Swap A and Br to change ABlBr into BrBlA
* 4. Recur on the two pieces of B
* 5. Once A and B are of equal lengths, swap A and B
*
* @param a
* @param st
* @param d
* @param n
* @return number of items rotated
*/
public int rotateleftByBlockSwap(int a[], int st, int d, int n) {
if(d == 0 || d == n)
return 0;
int i, j;
i = d;
j = n - d;
while (i != j)
{
if (i < j) { // A is shorter
swap(a, st+d-i, st+d+j-i, i);
j -= i;
}
else { // B is shorter
swap(a, st+d-i, st+d, j);
i -= j;
}
}
// swap block swap A and B
swap(a, st+d-i, st+d, i);
return d;
}
public void sort(int[] a) {
if (a==null || a.length<=1)
return;
int start = 0, mid=0, end=0, num = 1;
do {
start = skipNegBlock(a, start);
mid = skipPosBlock(a, end==0? start : end);
end = skipNegBlock(a, mid);
num = rotateleftByBlockSwap(a, start, mid-start, end-start);
} while (num>0);
}
}
/**
* Algorithm 6 is based on lg(N) blocking.
*
*
* @author stones333
*
*/
static public class NegativePositiveSorterViaBlockSwap extends NegativePositiveBaseSorter implements Sorter {
public void sort(int[] a) {
if (a==null || a.length<=1)
return;
int num=2;
int start, mid, end;
while (num<a.length) {
start = 0;
mid= advance(a, start, num/2);
end = advance(a, start, num);
while (start<end) {
pickAndSwapBlock(a, start, mid, end);
start=end;
mid= advance(a, start, num/2);
end = advance(a, start, num);
}
num = num * 2;
}
mid= advance(a, 0, num/2);
end = advance(a, 0, num);
pickAndSwapBlock(a, 0, mid, end);
}
}
// test code for NegativePositiveSorterViaRotationWithJuggling
public static void testNegativePositiveSorterViaRotationWithJuggling() {
Sorter sorter = new NegativePositiveSorterViaRotationWithJuggling();
int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
sorter.sort(a);
sorter.print(a);
}
// test code for NegativePositiveSorterViaRotationWithBlockSwap
public static void testNegativePositiveSorterViaRotationWithBlockSwap() {
Sorter sorter = new NegativePositiveSorterViaRotationWithBlockSwap();
int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
sorter.sort(a);
sorter.print(a);
}
// test code for NegativePositiveSorterViaBlockSwapWithReverse
public static void testNegativePositiveSorterWithBlockSwapViaReverse() {
Sorter sorter = new NegativePositiveSorterViaBlockSwapWithReverse();
int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
sorter.sort(a);
sorter.print(a);
}
// test code for NegativePositiveCountSorter
public static void testNegativePositiveCountSorter() {
Sorter sorter = new NegativePositiveCountSorter();
int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
sorter.sort(a);
sorter.print(a);
}
// test code NegativePositiveSwapSorter
public static void testNegativePositiveSwapSorter() {
Sorter sorter = new NegativePositiveSwapSorter();
int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
sorter.sort(a);
sorter.print(a);
}
// test code NegativePositiveSorterViaBlockSwap
public static void testNegativePositiveSorterViaBlockSwap () {
Sorter sorter = new NegativePositiveSorterViaBlockSwap();
int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
sorter.sort(a);
sorter.print(a);
}
public static void main(String[] args) {
testNegativePositiveSwapSorter();
testNegativePositiveCountSorter();
testNegativePositiveSorterWithBlockSwapViaReverse();
testNegativePositiveSorterViaRotationWithBlockSwap();
testNegativePositiveSorterViaRotationWithJuggling();
testNegativePositiveSorterViaBlockSwap();
}
}
Enjoy.
