sort as string enters array alphabetical java

Question

so I am trying to enter information into an array in the correct alphabetical order spot as it is entered. Right now I have it entering everything into the array unordered then I order it using a sort method after but my professor says, "To receive full credit, you must insert each item into its sorted position in the array as it is read in. It is not ok to read it all in and call a sort routine." How can I enter the item into the correct spot into the array? This is what I have

public class NumberCollection2
{
  String nextName;
  int nextNumber;
  private Person[] people = new Person[50];
  private int size =0; 

  public void load()
  {
    try
    {
      Scanner in = new Scanner(new File ("numbers.txt"));

      while (in.hasNextLine())
      {
        nextName = in.next();
        nextNumber = in.nextInt();
        people[size]=new Person(nextName, nextNumber);
        size++;
        in.nextLine();

      }

      //use exchange sort to sort in ascending alphabetical order
      int i, j;

      for ( i = 0;  i < size - 1;  i++ )
      {
        for ( j = i + 1;  j < size;  j++ )
        {  
          if ( people[ i ].getName().compareTo(nextName) > 0 )
          {                                            
            Person temp = people [ i ];
            people [ i ] = people [j];    
            people[j] = temp; 

          } 
        } 

      }

    }

Use `Arrays.binarySearch()`, you will know where to insert it — fge, Feb 16 '14 at 22:55
I just looked that method up because I've never used it and it says "The java.util.Arrays.binarySearch(int[] a, int key) method searches the specified array of ints for the specified value using the binary search algorithm.The array must be sorted before making this call.If it is not sorted, the results are undefined." My array isn't technically going to be sorted so I'm confused with that — Jess Anastasio, Feb 16 '14 at 23:03
Actually, yes, your array its going to be sorted: because, when you start, is empty, then when you have one element, you use this binarySearch, to know where to put the second element, and so on... — Ale Zalazar, Feb 16 '14 at 23:55
The optimal solution is using a priority queue, which will lead to an insertion time of O(lgn) (for an overall insertion time of O(nlgn). But then it all depends on the details of the assignment since a priority queue is a more complex data structure than an array. — Giovanni Botta, Feb 17 '14 at 00:20

score 1 · Answer 1 · edited Feb 17 '14 at 00:05

1

Your teacher probably expects from you to implement the InsertSort algoritm. See this sources for more details:

It should look something like:

while (in.hasNextLine())
{
    nextName = in.next();
    nextNumber = in.nextInt();
    for(i = size; i > 0; --i) {
        if ( people[i - 1].getName().compareTo(nextName) <= 0 ) {
            break;
        }
        people[i] = people[i-1];
    }
    people[i] = new Person(nextName, nextNumber);
    size++;
    in.nextLine();
}

edited Feb 17 '14 at 00:05

Martin Tournoij

26,737
24
105
146

answered Feb 16 '14 at 23:13

Andrei B

2,740
17
12

Hey I tried your method and tried to have it just print the array for me and all I got as output was [LPerson;@a51064e To print out the array all I have to do is System.out.println(people); right? Thanks!! – Jess Anastasio Feb 17 '14 at 01:40
No. That prints only the array signature. To print its contents you should do for(i = 0; i < size; ++i) System.our.println(people[i].getName()); – Andrei B Feb 17 '14 at 13:34

sort as string enters array alphabetical java

1 Answers1