How to merge two sorted arrays into one sorted vector???

[MtX]

Hello,

I have two text files. Both files have a list of sorted names. The two files have to be merged into one sorted vector. I have heard of two methods to accomplish this task but I am not sure how to do it. First method is to compare the elements of each array and then put it into the new vector and the other method is merge sort. Can anyone offer some assistance and suggestions?

Thanks

[MtX]

there was a method my teacher was talking about... he said it's the easiest to accomplish this task.. for example, there are two sorted arrays:

Array 1
Auckland
Boston
Munich
Ohio

Array 2
London
NYC
Rome
Sydney

the program compares the first element of each array to each other... Auckland vs London, Auckland is smaller so it goes first in the new vector... Since Auckland is eliminated, its Boston vs London, Boston is smaller so it goes in the new vector as second element.. Then London vs Munich, London smaller so it goes in as third element.. Then Munich vs NYC and so on... I get the concept - but when it comes to writing it out in Java, Im puzzled..

[Barancle]

Well, I played around and came up with this. It should work in most cases. Don't just copy and paste, study it to learn how the logic works.

import java.io.*;
import java.util.Vector;

class sample{
public static void main(String[] args){
// Create two arrays of Strings
String[] one = new String[4];
one[0] = "Auckland";
one[1] = "Boston";
one[2] = "Munich";
one[3] = "Ohio";
String[] two = new String[4];
two[0] = "London";
two[1] = "NYC";
two[2] = "Rome";
two[3] = "Sydney";

//Create an ArrayMerger and merge the two arrays
ArrayMerger am = new ArrayMerger();
Vector myVector = am.mergeArrays(one, two);
// Print the Vector to check if it's in order
System.out.println(myVector.toString());
}
}

class ArrayMerger{
Vector mergeArrays(String[] first, String[] second){
Vector merged = new Vector();
int countFirst = 0, countSecond = 0;

for(int i = 0; i < (first.length + second.length); i++){
// check if the first array is empty or has been used up
if (first.length == 0 || countFirst == first.length){
merged.addElement(second[countSecond]);//add from second array
countSecond++;//go to next element in second array
}
// check if the second array is empty or has been used up
else if(second.length == 0 || countSecond == second.length){
merged.addElement(first[countFirst]);//add from first array
countFirst++;//go to next element in first array
}
// compare the two strings add the lesser of the two, go to next
else if (first[countFirst].charAt(0) < second[countSecond].charAt(0)){
merged.addElement(first[countFirst]);
countFirst++;
}
else{
merged.addElement(second[countSecond]);
countSecond++;
}
}

return merged;
}
}

[jompe71]

I suggest you use whats in the core API. Check the Collections class and try the example below. If the lists includes other custom objects rather than plain Strings your object should implement the Comparable interface overriding the compareTo method and you can sort the array just as usual.


public class JustAClass
{
public static void main( String[] args )
{
String arrOne[] = { "Auckland", "Boston", "Munich", "Ohio" };
String arrTwo[] = { "London", "NYC", "Rome", "Sydney" };

ArrayList alOne = new ArrayList(),
alTwo = new ArrayList();

for( int i = 0; i < arrOne.length; i++ )
alOne.add( arrOne[ i ] );

for( int j = 0; j < arrTwo.length; j++ )
alTwo.add( arrTwo[ j ] );

alOne.addAll( alTwo );
Collections.sort( alOne );

System.out.println( alOne );
}
}


Regards.

[dlorde]

Why write your own error-prone looping code when the JDK provides all you need?

Use the Arrays class to get the array contents into two Lists, add the Lists to the Vector and sort the Vector using the Collections class: // Create two arrays of Strings
String[] one = new String[4];
one[0] = "Auckland";
one[1] = "Boston";
one[2] = "Munich";
one[3] = "Ohio";

String[] two = new String[4];
two[0] = "London";
two[1] = "NYC";
two[2] = "Rome";
two[3] = "Sydney";

// Make Lists from arrays
List list1 = Arrays.asList(one);
List list2 = Arrays.asList(two);

// Add lists to Vector
Vector vector = new Vector(list1);
vector.addAll(list2);

// Sort Vector
Collections.sort(vector);

// Output results
for (int i=0; i<vector.size(); i++) {
System.out.println(vector.elementAt(i));
}Whenever there is a hard job to be done I assign it to a lazy man; he is sure to find an easy way of doing it...
W. Chrysler

[MtX]

Thanks for all the replies..... I think I can only use what we've learned so far...Ive never used arrayMerger or Collections before.. so I dont think I should use it.

anyways, so far, ive read two text files into two vectors.. right now im tryin to merge the two vectors into a sorted vector...im tryin to compare the first elements to each other, then put the lower one into the new vector.... if I use compareTo, it only gives me < > or =, so... im not really sure what to do

[Barancle]

MtX, ArrayMerger doesn't exist except for the fact that I made it. You are allowed to use for loops and if else statements aren't you?

If you don't want it to be a class just make a method that does the same thing as the mergeArrays method. I tried to make the mergeArrays method so it does exactly what you described, it takes two sorted String Arrays and returns one sorted Vector. If you don't understand how the mergeArrays method works then you need to ask some more questions.

[MtX]

here's what i came up wtih so far but it doesnt work....

// The "ABCInc" class.
import java.awt.*;
import java.io.*;
import java.util.*;
import hsa.Console;

public class ABCInc
{
static Console c; // The output console

public static void main (String [] args) throws IOException
{
c = new Console ();

Vector f1 = new Vector ();
Vector f2 = new Vector ();
Vector v = new Vector ();
String fileName, fileName2, fileName3, line, line2;
int counter = 0;


c.println ("Welcome to ABC Inc.");
c.println ();
c.println ("What is the name of the first file you want to merge?");
fileName = c.readLine ();
c.println ("What is the name of the second file you want to merge?");
fileName2 = c.readLine ();


BufferedReader input = new BufferedReader (new FileReader (fileName));
line = input.readLine ();
while (line != null)
{
line = input.readLine ();
f1.addElement (line);
}
c.println ();
BufferedReader input2 = new BufferedReader (new FileReader (fileName2));
line2 = input2.readLine ();
while (line2 != null)
{
line2 = input2.readLine ();
f2.addElement (line2);
}


for (int i = 0 ; i < f1.size () ; i++)
{
for (int j = 0 ; j < f2.size () ; j++)
{
if (f1.elementAt (i) < (f2.elementAt (j))
v.addElement (i);
else
v.addElement (j);
}
}



} // main method
} // ABCInc class

[Barancle]

Well, as I didn't see a question I took the liberty of making something that does work. It my not be the best solution but from what I tested it seems to do the job.
import java.io.*;
import java.util.Vector;

class ABCInc{
public static void main(String[] args){
Vector merged = new Vector();
Vector f1 = new Vector();
Vector f2 = new Vector();

// add your console stuff here to get the file names and
// change file1.txt and file2.txt to the files you get from
// the user
String file1 = "file1.txt";
String file2 = "file2.txt";


// Grab the files and put them in Vectors f1 and f2
try{
BufferedReader input = new BufferedReader (new FileReader (file1));
String line = input.readLine ();
while (line != null){
f1.addElement (line);
line = input.readLine ();

}
input = new BufferedReader (new FileReader (file2));
line = input.readLine ();
while (line != null){
f2.addElement (line);
line = input.readLine ();
}
}
catch(Exception e){
// You should have catches for each type of exception and what
// to do in each case
}

// Merge the two Vectors together
int limit = f1.size() + f2.size();
for (int i = 0; i < limit; i++){
if(f1.isEmpty())
merged.addElement(f2.remove(0));
else if(f2.isEmpty())
merged.addElement(f1.remove(0));
else if(f1.firstElement().toString().charAt(0) < f2.firstElement().toString().charAt(0))
merged.addElement(f1.remove(0));
else
merged.addElement(f2.remove(0));
}

// Print the results and so you can check if it's in order
System.out.println(merged);
}
}

[Barancle]

One note, the way I compare the Strings is not very good, it only looks at the first letter of every city. But it should at least give you a good starting point.

[dlorde]

Originally posted by Barancle
One note, the way I compare the Strings is not very good, it only looks at the first letter of every city. But it should at least give you a good starting point. Why don't you use String.compareTo(...) or String.compareToIgnoreCase(...) ?

Why do it the hard way if better methods are available?

[Barancle]

Why don't you use String.compareTo(...) or String.compareToIgnoreCase(...) ?

Good call dlorde, that works much better, I don't know what I was thinking.

MtX, so change this line

else if(f1.firstElement().toString().charAt(0) < f2.firstElement().toString().charAt(0))
merged.addElement(f1.remove(0));

to this...

else if(f1.firstElement().toString().compareToIgnoreCase(f2.firstElement().toString()) < 0)
merged.addElement(f1.remove(0));

[MtX]

Originally posted by Barancle
Good call dlorde, that works much better, I don't know what I was thinking.

MtX, so change this line

else if(f1.firstElement().toString().charAt(0) < f2.firstElement().toString().charAt(0))
merged.addElement(f1.remove(0));

to this...

else if(f1.firstElement().toString().compareToIgnoreCase(f2.firstElement().toString()) < 0)
merged.addElement(f1.remove(0));

hmmmmm, the newer one..... isnt the element of a vector already a string object, is it necessary to convert it toString???

i tried doing this:


int i = 0;
int j = 0;
while(i < f1.size() && j < f2.size())
{
if (((String)f1.elementAt(i)).compareTo(f2.elementAt(j)) < 0) {
v.addElement (f1.elementAt (i));
i++;
} else {
v.addElement (f2.elementAt (j));
j++;
}

}


but i get an error saying: no method named "compareTo" was found in type "java.lang.Object"

[CornedBee]

The member has a runtime type of String, but the return value of all getter methods is Object. You have to convert it to a string somehow, and toString() is the easiest way.

[Barancle]

MtX, your while loop will not work corectly. It will stop after only one of the files is used up truncating all the left over cities in the other file. This is why i set up my for loop the way I did. You can use a while loop, that's fine, but you still have to account for the fact that one file is always going to end before the other one, and it needs to properly add all the elements of the left over file.

[MtX]

Good news... I got it to successfully merge two sorted files into a vector... now that the first part is done.... its time to move onto the second....

Using the merged file, create a menu that will be able to:

1. Add new customers
2. Remove customers
3. Search for customers
4. Sort the data base (all files stored on disk will be sorted)
5. Print out the data base to console ( the screen should not hide any customers because it moves too quickly)
6. Read the file current.txt and write to the file

im planning on usin a switch statement to create this menu.. also creating separate methods for each menu option.. im gonna play around and try to successfully code every option so it works, ill post any questions/concerns if i have if i encounter any :P

[cjard]

i recommend implementing the search method first, as it makes other operations where a specific thing must be found, much easier (like deletes, are a process of: find, delete)