Sorting a linked list using insert sort method in Java

Question

I have an assignment for my class to sort a LinkedList that we made previously using the insert sort method. We created the List by reading in an excel file with 5 contributors listed. I realize this sounds like a repeat question...however, all of the samples I can find deal with Integers or arrays, nothing that I can find deals with strings or with a LinkedList like the one I am using. The other problem, the examples I do find that deal with more than just integers assume you made the list "from scratch", using Head and Node and stuff like that...as you can see in my code, I did not make mine from scratch, I just used the build in Java utility to make mine. Anyways, my code may not be super efficient, but I got a 100 on every assignment so far, so it's good enough for the school I guess, but any suggestions to make it better are welcome as well. I am a beginner to programming, only experience I have is previous classes. So, here is my code:

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

public class ChrisJohnson_Unit3_IP {

static class Contributor{   //create class to store contributor information
  //declare variables
  private String firstName;
  private String lastName;
  private String country;
  private String phone;
  private double contribution;
  private int id;

  //methods for setting variable values
  public String getFirstName(){
      return firstName;
  }

  public void setFirstName(String firstName){
      this.firstName = firstName;
  }
  public String getLastName(){
      return lastName;
  }

  public void setLastName(String lastName){
      this.lastName = lastName;
  }

  public String getCountry(){
      return country;
  }

  public void setCountry(String country){
      this.country = country;
  }

  public String getPhone() {
      return phone;
  }

  public void setPhone(String phone){
      this.phone = phone;
  }

  public double getContribution(){
      return contribution;
  }

  public void setContribution(double contribution){
      this.contribution = contribution;
  }

  public int getId(){
      return id;
  }

  public void setId(int id){
      this.id = id;
  }

  public void Print(){//method to print class objects
      System.out.printf("%-10s %-10s %-8s %-15s %s %-15s %d %n", firstName,     lastName, country,
      phone, "$", contribution, id);
  }
}//end Contributor class

static LinkedList contributorList = new LinkedList(); //create new  Contributor Linked List
static Hashtable<String, Contributor> memberID = new Hashtable<>();//create new Hash Table

 public static void main(String[] arg) throws Exception {

 String response;
 String ID;

 Contributor contributorData = null;


 Scanner in = new Scanner(System.in);

 //print Welcome message and describe program to user
 System.out.println("Welcome! This program will read your contributors.csv file "
      + "and store it into a list. \nTThe program will then sort the list and"
      + "print it for you to view/n");

 System.out.println("Press enter to read the currently saved contributors.csv file...");
 in.nextLine();

 BufferedReader File = 
    new BufferedReader(new FileReader("contributors.csv"));

 String dataRow = File.readLine(); // Read first line.
 // The while checks to see if the data is null. If 
 // it is, end of file has been reached. If not, 
 // data will be processed.

 while (dataRow != null){//While to read contributors.csv file and store in Contributor object

 String[] data = dataRow.split(",");
 contributorData = new Contributor(); //create new Contributor object

 //store data into Contributor object
  contributorData.setFirstName(data[0]);
  contributorData.setLastName(data[1]);
  contributorData.setCountry(data[2]);
  contributorData.setPhone(data[3]);
  contributorData.setContribution(Double.parseDouble(data[4]));
  contributorData.setId(Integer.parseInt(data[5]));
  ID = Integer.toString(contributorData.getId());
  contributorList.push(contributorData);//add object to top of   contributorList

  memberID.put(ID,contributorData);//add contributor ID to key element of  Hash Table
  dataRow = File.readLine(); // Read next line of data.
 }//end While to read contributors.csv file

 File.close();//close CSV file

 System.out.println("Here is your unsorted contributor list:\n");
 //call Print method to print the list
 System.out.printf("%-10s %-10s %-8s %-15s %-17s %s %n", "First", "Last",
      "Country", "Phone #", "Contribution", "ID");
 Iterator<Contributor> iter = contributorList.iterator();
 while(iter.hasNext()){
  iter.next().Print();
 }//end while

 System.out.println("Thank you for using this program!");
 } //main()

 }//end ChrisJohnson_Unit3_IP class

Again, the List has to be sorted by Name using the insert sort method. I understand the basic concept of the sort method, but honestly have no clue how to implement it here. I'm not looking for someone to do my homework for me, just give me a push in the right direction. Any help would be greatly appreciated, if you need anymore information please let me know. This assignment is due Monday, so hopefully someone is able to help me out by then. And yes, I have already written my instructor asking for help, I have been out of town all week so I have been trying to play catchup. Thank you for taking the time to read my question

Answer 1

Use ListIterator to find the correct point to insert the element and to the insertion. This allows you to do the insertion sort more efficiently than with the "standard approach", which would run in O(n³), since get and set runs in O(i) for index i. (The inner loop would run in O(i²), since O(1+2+...+i) = O(i²) and O(1²+2²+...+n²) = O(n³)).

Note that using a Iterator is enough to find the insertion point in O(n) and achieve O(n²) running time, but using ListIterator allows you to find and insert the element as well as remove the element for the next iteration of the outer loop iteration only a single iterator, if used in a clever way.

---

Using a Comparator to compare objects by a specified criterion also allows you to specify a criterion to sort by:

return value of comparator.compare(a, b)   |     meaning
-----------------------------------------------------------
           0                               |       a == b
         > 0                               |       a > b
         < 0                               |       a < b

In java 8 you can easily create a Comparator given the method reference to a method returning the sort criterion given a object:

Comparator<Contributor> comparator = Comparator.comparing(Contributor::getLastName);

Without using method references this can be done using compareTo of a object implementing the Comparable interface, like String:

Comparator<Contributor> comparator = new Comparator<Contributor>() {

    @Override
    public int compare(Contributor o1, Contributor o2) {
        return o1.getLastName().compareTo(o2.getLastName());
    }

};

This way you use the Strategy Pattern for the ordering relation allowing you to use different sortings by passing different Comparators. And it's also the way the Collections class allows you to sort Lists with arbitrary contents, see Collections.sort(List, Comparator).

Answer 2

First of all, I should say that doing an insertion sort on a linked list is totally pointless. Secondly, you could do something like the following, if you add a getName method that concatenates first and last names of the contributor (you can concatanate while sorting, but your code will be messier).

for( int i = 1; i < contributorList.size(); i++)
{
    int j = i;
    Contributor tmp;
    while( j > 0 && contributorList.get(j-1).getName().compareTo( contributorList.get(j).getName()) > 0)
    {
        tmp = contributorList.remove( j);
        contributorList.add( j-1, tmp);
        j = j - 1;
    }
}

Answer 3

First change your contributorList to use the Generic type of the objects it holds. That is LinkedList<Contributor>;. Second change the Object to implement Comparable. That is class Contributor implements Comparable<Contributor> and implement method public int compareTo(Contributor other). Third, pick a sorting method and implement it using compareTo to compare the objects for sorting.