Adding elements to array in alphebetical order

Question

I'm writing a program which adds telephone entries into a staff phone directory, I want to add the elements to the array in alphabetical order (using surnames) rather than adding the elements then calling Arrays.sort every time a new entry is added, as that would be less efficient. Here is some code I have so far, I'm not sure how to compare each element in the array with the following one and so forth.

public class ArrayDirectory implements Directory {

Entry [] directory = new Entry [50];

@Override
public void addEntry(String initials, String surname, int extension) {

     //Entries are added here in alphabetical order

}

Here is my Entry class -

public class Entry  {

private String initals,surname;
private int extention;

public Entry(String initals, String surname, int extention){
    this.initals = initals;
    this.surname = surname;
    this.extention = extention;
}

public String getInitals(){

    return initals; 
}
public String getSurname(){

    return surname;
}
public int getExtention(){

    return extention;
}

}

Any suggestions, do I override compareTo? Thanks

edit - should have noted I have been asked to use an array. Sorry for the confusion.

Edit 2: updated my addEntry method and overriden compareTo in Entry -

public void addEntry(String initials, String surname, int extension) {

    for (int i = 0; i < directory.length; i++) {
        if (directory[i] != null) {
            int y = directory[i].getSurname().compareTo(surname);
            if (y == 1) {
                int position = i;
                break;
            }
        } else if (directory[i] == null) {
            int position = i;
            break;
        }
    }
}

And my compareTo method -

public int compareTo(Entry other) {     
    return this.surname.compareTo(other.getSurname());
}

I'm not sure how to shift the elements in the array to the right after I have found the correct position? Thank you for all of you help.

Arrays.sort() is not particularly innefficient for what you are doing... The time that you will take will be used shifting the remainder of the array. — Anubian Noob
– Anubian Noob, Commented Apr 16, 2014 at 23:39

terpinmd · Accepted Answer · 2014-04-16 23:49:33Z

1

If you dont have to use an array then your using the wrong data structure.

No matter what path you need to implement Comparable:

public class Entry implements Comparable<Entry>{

..

@Override
public int compareTo(Entry other) {
    // TODO Auto-generated method stub
    return this.surname.compareTo(other.getSurname());
}
..

Consider using a SortedSet:

   Set<Entry> map = new TreeSet<Entry>();

   map.add(new Entry("JEH", "Hamlet", 123));
   map.add(new Entry("AAC", "Adams", 123));
   map.add(new Entry("FAM", "Monti", 321));

That will print in the desired order. If you must use an Array then you need to sort it upon insert.

answered Apr 16, 2014 at 23:49

terpinmd

1,0189 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bhesh Gurung · Accepted Answer · 2014-04-17 17:01:43Z

You could make Entry comparable and implement the compareTo in it. But you don't really have to in this case because String is already comparable.

Since this is a homework, I think it will be best to just give you some suggestions on how to proceed, instead of handing you the code -

In your method you do not need to sort the array, you just need to insert it at the correct location in the array.

loop through the array starting at the first index
as you pass through each element in the array, you will have to check following two conditions
1. is the element null
2. is the surname of current element greater than surname-argument to the method
as soon as you find the element that satisfies any of the above conditions, record the index and break the loop
then, starting at that index shift the rest of elements to the right
and finally create a new instance of Entry for the provided arguments and set it at that index

Note: This doesn't take care of the situation where you are out of the space in the array.

Update:

I think you mixed up my answer and @David Wallace's answer. It wasn't my suggestion to implement compareTo. Also, it's great that you at least gave it a try and came back.

int position = -1; //declare the position outside (if declared inside, it's not visible outside the loop)
for (int i = 0; i < directory.length; i++) {
     // position = i; just assign value of i inside the loop
}

//use the position after the loop
int j = position; // start at position
Entry temp = null; // temp will temporarily hold the entry at the next index
while(true) { 
    temp = directory[j + 1]; // since we need move entry at j to j+1, first we need save the entry at j+1
    directory[j + 1] = directory[j]; // entry at j to j+1
    if(temp == null) { // if the next entry is null, don't really need to move no more, so break
        break;
    }
}
// finally place new entry at index position
directory[position] = //the new Entry

How would I go about shifting the elements right? I've updated my code above. Thank you

Dawood ibn Kareem · Accepted Answer · 2014-04-16 23:51:28Z

0

Make Entry implement Comparable<Entry> and write the appropriate compareTo method in your Entry class. Then, in your insert method, you want to

Use Arrays.binarySearch to find the right place in the array to insert your the entry.
Use System.arraycopy to shift everything in the array that's after the appropriate location one place to the right.
Set the appropriate entry.

You'll want to check out the Javadoc for Arrays.binarySearch and System.arraycopy.

edited Apr 16, 2014 at 23:51

answered Apr 16, 2014 at 23:45

Dawood ibn Kareem

80.2k15 gold badges103 silver badges112 bronze badges

Comments

Bohemian · Accepted Answer · 2014-04-17 00:49:06Z

Firstly, never use arrays unless you absolutely have to. Use Collecctions instead - they are far easier to deal with and have support for lots of operations you commonly want to perform on groups of things.

In your case, a TreeSet would be a good choice. If you want to sort the entries by surname only in this usage (and not generally), you can pass a customer Comparator to the constructor:

Set<Entry> directory = new TreeSet<>(new Comparator<Entry>() {
    @Override
    public int compare(Entry o1, Entry o2) {
        return o1.getSurname().compareTo(o2.getSurname());
    }
});

If your always want to sort Entry objects using surname, have your Entry class implement Comparable<Entry> and move the code into the compareTo() method of the Entry class.

Collectives™ on Stack Overflow

Adding elements to array in alphebetical order

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related