Sorting an array with two values

Question

I have array of colors:

String  s[]=new String[]{"red","black..............};

The only possible colors are red and black. I need an algorithm which partitions the array such that all red come before all black. How can I compare/exchange them to accomplish that? i have tried this

public class Partition{



public static void main(String[]args){
String temp="";
String s[]=new String[]{"red","black","red","black","black","red","red","black","red"};
int i=0;
int j=s.length;
while (i<j){
do{
i++;
} while (s[i]!="black");

do{
j--;
} while (s[i]!="red");


 if (i>j)  break;
 if (i<j){
 exch( s,i,j);
}
}

 for (int k=0;k<s.length;k++){
 System.out.println(s[k]);
}




}

public static  void  exch  (  String s[],int i,int j){

 String m=s[i];
 s[i]=s[j];
 s[j]=s;


}
}

but it does not show me result

Answer 1

Just sort and reverse.

Without sort: iterate from front to end and end to front using two iterators, look for the first instance of red from the right and first instance of black from the left. Swap them. Perform this until both iterators cross.

Answer 2

Assuming you are using Java... you can use java.util.Arrays.sort

Answer 3

Not very efficient but a really easy way of doing it would be:

Array.Sort(s);
Array.Reverse(s);

Edit: Wrote my answer assuming C# which might not be the case...

Answer 4

You can do this in O(N) with counting sort.

Count how many "red" and "black" are there. Let's say there are x "red" and y "black". Then, instead of swapping things around etc, just put x "red" followed by y "black" and you're done.

Note that this not a comparison based sort: you never compare one element of the array to another element of the array. You're just checking if an element is "red" or "black". Thus, it's not bound by the O(N log N) theoretical lower bound for comparison-based sorting.

---

If you just want to fix the code that you have right now, then something like this works:

public static void main(String[] args) {
    String[] s = {
        "red","black","red","black","black","red","red","black","red"
    };
    for (int i = 0, j = s.length - 1; i < j; ) {
        while (i < j && s[i].equals("red")) i++;
        while (i < j && s[j].equals("black")) j--;
        swap(s, i, j);
    }
    System.out.println(java.util.Arrays.toString(s));
    // prints "[red, red, red, red, red, black, black, black, black]"
}
public static void swap(String[] s, int i, int j){
    String temp;
    temp = s[i];
    s[i] = s[j];
    s[j] = temp;
}

Note the difference in logic between the while from the original do while. Note also the extra condition to guard against ArrayIndexOutOfBoundsException when the element sought does not exist (e.g. when the array is all of one color).

Note also the declaration of arrays as type[] identifier as opposed to type identifier[]. The former is the official recommended style for Java.

Answer 5

If you really just want to get an array with the reds before the blacks, sort/reverse will work as others have mentioned.

1. Why are you using strings? It's probably much more logical to use an enum (enum Color {RED, BLACK};) or (I'm guessing this is Java) the java.awt.Color class

2. Why are you making a new array instead of just having a count? You could do:

   Color[] colorArray = {RED, BLACK, BLACK, RED, RED};
   int red = 0, black = 0;
   for(Color c : colorArray) {
       switch(c) {
           case RED: red++; break;
           case BLACK: black++; break;
       }
   }
   

Even if you do need an array, it's probably fastest to just do the count and then refill the array afterwards:

Arrays.fill(colorArray, 0, red, RED);
Arrays.fill(colorArray, red, red+black, BLACK);