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

• user207421: Why? The assignment is idiotic. Only a madman would sort a linked list.
• Chris Johnson: Totally agree....this class is completely retarded, the assignments are frustrating because nobody in the real world would do any of the things we are learning...but unfortunately I have to do it this way :/ Going to leave a "nice" review on this class when it's over...

Answer 1

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;
 }
}

• Chris Johnson: Well that was a lot easier than I expected...thank you so much! I just used the .getFirstName method that I already had in the Contributor class and that worked just fine. Kind of feel stupid now for not seeing that solution already...thanks again, really saved me a lot of time!
• fabian: It's only pointless, if you don't know how to use LinkedList the right way, see my answer and BTW, your Bubble Sort runs in O(n³) for LinkedList which isn't better than insertion sort.

Answer 2

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.

Answer 3

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(n3), since get and set runs in O(i) for index i. (The inner loop would run in O(i2), since O(1+2+...+i) = O(i2) and O(12+22+...+n2) = O(n3)).

Note that using a Iterator is enough to find the insertion point in O(n) and achieve O(n2) 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).