Сортировка связанного списка с использованием метода сортировки вставки в Java

Question

У меня есть задание для моего класса для сортировки LinkedList, который мы сделали ранее, используя метод сортировки вставки. Мы создали список, прочитав в файле excel список из 5 участников. Я понимаю, что это звучит как повторяющийся вопрос ... однако, все образцы, которые я могу найти, имеют дело с целыми или массивами, ничто из того, что я могу найти со строками или с LinkedList, как тот, который я использую. Другая проблема, примеры, которые я нахожу, которые касаются более чем целых чисел, предполагают, что вы сделали список «с нуля», используя Head и Node, и так далее ... как вы можете видеть в моем коде, я не сделал свой с нуля, я просто использовал сборку в утилите Java, чтобы сделать мой. В любом случае, мой код может быть не очень эффективным, но до сих пор у меня есть 100 на каждое задание, поэтому он достаточно хорош для школы, я думаю, но любые предложения, чтобы сделать ее лучше, также приветствуются. Я начинаю программировать, только опыт у меня есть предыдущие классы. Итак, вот мой код:

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 

Опять же, список должен быть отсортирован по имени, используя метод сортировки вставки. Я понимаю основную концепцию метода сортировки, но, честно говоря, не знаю, как ее реализовать здесь. Я не ищу, чтобы кто-то выполнял мою домашнюю работу для меня, просто дайте мне толчок в правильном направлении. Любая помощь будет принята с благодарностью, если вам нужна дополнительная информация, пожалуйста, дайте мне знать. Это задание должно состояться в понедельник, поэтому, надеюсь, кто-то сможет мне помочь. И да, я уже написал своего инструктора, просящего о помощи, я всю неделю был вне города, поэтому я пытался играть в догонялки. Спасибо, что нашли время, чтобы прочитать мой вопрос.

Answer 1

Прежде всего, я должен сказать, что делать сортировку в связанном списке совершенно бессмысленно. Во-вторых, вы можете сделать что-то вроде следующего, если вы добавите метод getName, который объединяет имена и фамилии вкладчика (вы можете конкатенатировать при сортировке, но ваш код будет более беспорядочным).

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 2

Во-первых изменить ваш contributorList использовать общий тип объектов, которые он держит. То есть LinkedList<Contributor> ;. Второе изменение объекта для реализации Comparable. То есть class Contributor implements Comparable<Contributor> и реализовать метод public int compareTo(Contributor other). В-третьих, выберите метод сортировки и реализуйте его с помощью compareTo, чтобы сравнить объекты для сортировки.

Answer 3

Используйте ListIterator, чтобы найти правильную точку для вставки элемента и вставку. Это позволяет выполнять сортировку более эффективно, чем при «стандартном подходе», который будет работать в O(n³), поскольку get и set работает в O(i) для индекса i. (Внутренний цикл будет работать в O(i²), начиная с O(1+2+...+i) = O(i²) и O(1²+2²+...+n²) = O(n³)).

Обратите внимание, что using a Iterator достаточно, чтобы найти точку вставки в O(n) и достичь O(n²) времени работы, но с использованием ListIterator позволяет найти и вставить элемент, а также удалить элемент для следующей итерации внешней итерации цикла только один итератор, если он используется умным способом.

---

Использование Comparator для сравнения объектов по заданному критерию также позволяет задать критерий для сортировки:

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

В Java-вы можете легко создать Comparator данный метод ссылку на метод, возвращающий критерий сортировки данного объект:

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

без использования ссылок методы это может быть сделано с помощью compareTo объекта, реализующий интерфейс Comparable, как String:

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

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

}; 

Таким образом, вы используете the Strategy Pattern для упорядочения связи, что позволяет использовать различные сортировки, передавая различные Comparator с. И это также способ, которым класс Collections позволяет сортировать List с произвольным содержимым, см. Collections.sort(List, Comparator).