3. Suppose you have an array of N objects (as a reminder, in Java, the array wou

Question

3. Suppose you have an array of N objects (as a reminder, in Java, the array would actually contain references to the objects). Each object has a key field and some other data fields. The key field s a string that can have only two distinct values, red and blue. Give an O(N) algorithm to rearrange the array so that all red objects precede the blue objects. (Or rather that the references to red objects precede the references to ?blue objects.) You may uses only constant extra space. (3 points) Note: a non-solution would be to just count the number of reds and then rewrite the key field of the first k elements with the string red and the rest with blue. This would change the nature of the objects. Imagine your objects are flowers, and one attribute is color and another is species. Now if you just over-write the color attribute you will end up with corrupted data.

Explanation / Answer

import java.io.*;

import java.util.*;

class Flowers

{

String colour;

String Name;

Flowers(String cl,String nm)

{

colour = cl;

Name=nm;

}

}

public class RedBlue

{

public static void main(String[] args)

{

Flowers[] fl = new Flowers[12];

int cnt=1;

fl[0] = new Flowers("red","Rose");

fl[1] = new Flowers("blue","Lily");

fl[2] = new Flowers("red","Camellia");

fl[3] = new Flowers("red","Carnations");

fl[4] = new Flowers("red","Yarrow");

fl[5] = new Flowers("blue","Lily-of-the-Nile");

fl[6] = new Flowers("blue","Anemone");

fl[7] = new Flowers("blue","Aster");

fl[8] = new Flowers("red","Marygold");

fl[9] = new Flowers("blue","Skyflower");

fl[10] = new Flowers("blue","Iris");

fl[11] = new Flowers("blue","Lavender");

for(int i=0;i<fl.length;i++)

{

if (fl[i].colour == "red")

cnt++;

}

int j=0;

for(int i=cnt;i<fl.length;i++)

{

if (fl[i].colour == "red")

{

j=swap(fl,j,i);

}

}

for(int i=0;i<fl.length;i++)

{

System.out.println(fl[i].Name + " - " + fl[i].colour);

}

}

static int swap(Flowers flw[],int x,int z)

{

Flowers temp;

if (flw[x].colour == "blue")

{

temp = flw[z];

flw[z]=flw[x];

flw[x] = temp;

}

else

x=swap(flw,x+1,z);

return x+1;

}

}

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.