Java: Как создать отсортированную строку ArrayList на основе пользовательского объекта ArrayList без использования Sort ()

Question

У меня есть класс с именем Word, в котором каждый экземпляр имеет String, ArrayList<Character> и double. Допустим, есть 3 экземпляра этого класса. Я хотел бы создать новый ArrayList<String>, в котором содержатся все 3 строки слов. Тем не менее, порядок строк должен go от максимума до минимума двойников от их первоначальных экземпляров. Основным условием этого проекта является то, что метод Collections.sort не может быть использован. Пожалуйста, посмотрите код ниже и дайте мне знать, если вы можете придумать способ написать это l oop (необходимо al oop, потому что на самом деле есть +50 000 слов):

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;


public class WordRecommender {

    String fileName;

    public WordRecommender(String fileName) {
        this.fileName = fileName;
    }

    public static void main(String[] args) {

    ArrayList<Word> objectArray = new ArrayList<Word>();

    objectArray.add(new Word("people", null ,0.8));
    objectArray.add(new Word("dogs", null ,0.4));
    objectArray.add(new Word("cats", null ,0.6));

    ArrayList<String> outputArray = new ArrayList<String>();

    for (int i = 0; i < finalArray.size(); i++) {
      // code here to find the value of each double and place the 
      // associated strings into output Array from highest to lowest
    }

    // ideal outputArray order = ["people", "cats", "dogs"]

}

import java.util.ArrayList;

public class Word {

    String wordName;
    ArrayList<Character> uniqueLetters;
    double percent;

    public Word(String string, double percent) {
        ArrayList<Character> tempArray = new ArrayList<Character>();

        for (int i = 0; i < string.length(); i++) { 
            tempArray.add(string.charAt(i));
        }

        this.wordName = string;
        this.uniqueLetters = tempArray;
        this.percent = percent;
    }

}

Answer 1

Результат, который вам нужно достичь, можно разбить на 2 основных шага:

1. Описание того, как, давая 2 Word с, какой из них будет поставлен перед другим в List
2. Использование метода сравнения для фактической сортировки списка Word с.

Шаг 1. Как определить, какое слово стоит первым?

Java имеет интерфейс под названием Comparable. Название довольно очевидно. Когда вы реализуете этот интерфейс в своем классе Word, вы говорите Java, что экземпляры этого класса можно сравнивать друг с другом.

public class Word implements Comparable<Word>{

Когда вы редактируете эту строку в своем классе Word ваша IDE, вероятно, будет жаловаться на «отсутствующий compareTo() метод». Метод compareTo() определен в интерфейсе Comparable, и его задача из 2 экземпляров определяет, какой из них следует считать «большим» (или, в нашем случае, должен быть помещен первым в List).

Пример использования: "apple".compareTo("banana");. Этот вызов метода должен возвращать положительное число, если первый экземпляр («яблоко») «больше», отрицательное число, если второй экземпляр («банан») «больше», или ноль, если оба имеют одинаковое «значение». , Кстати, метод compareTo(), реализованный String s в Java, оценивает экземпляры в алфавитном порядке.

Итак, давайте реализуем нашу версию метода compareTo() для нашего класса Word.

@Override
public int compareTo(Word anotherWord) {
    if(this.percent > anotherWord.percent) {
        return 1;
    } else if (this.percent < anotherWord.percent) {
        return -1;
    } else {
        return 0;
    }
}

Имейте в виду, что эта реализация возвращает положительное значение, если первый экземпляр больше второго, и отрицательное значение наоборот.

Теперь, когда у нас есть способ сравнивая нашу Words, мы можем перейти к части сортировки.

Шаг 2. Алгоритмы сортировки

В inte rnet доступно огромное количество алгоритмов сортировки. Некоторые из них менее эффективны, некоторые проще в реализации. Вы можете исследовать некоторые из них здесь .

Для меня самый простой алгоритм сортировки называется BubbleSort . Однако это не очень эффективно.

ArrayList<Word> objectArray = new ArrayList<Word>();

objectArray.add(new Word("people", 0.8));
objectArray.add(new Word("dogs", 0.4));
objectArray.add(new Word("cats", 0.6));

for(int i = 0; i < objectArray.size() - 1; i++) {
    for(int j = 0; j < objectArray.size() - i - 1; j++) {
        // Remember: a compareTo() call returning a negative number
        // means that the first instance is smaller than the second.
        if(objectArray.get(j).compareTo(objectArray.get(j + 1)) < 0) {
            Word auxiliary = objectArray.get(j);
            objectArray.set(j, objectArray.get(j + 1));
            objectArray.set(j + 1, auxiliary);
        }
    }
}

Эти два вложенных цикла for будут сортировать objectArray в порядке убывания percent.

Answer 2

Я реализовал решение, которое включает алгоритм сортировки и использование java.util.Comparable обоих.

Во-первых, вам нужно реализовать класс Word с java.util.Comparable, чтобы вы могли определить, как сравнивать Word класс, чтобы определить, какой из них больше или ниже другого. В этом случае это будет поле percent.

public class Word implements Comparable<Word> {

    String wordName;
    ArrayList<Character> uniqueLetters;
    double percent;

    public Word(String string, double percent) {
        ArrayList<Character> tempArray = new ArrayList<Character>();

        for (int i = 0; i < string.length(); i++) {
            tempArray.add(string.charAt(i));
        }

        this.wordName = string;
        this.uniqueLetters = tempArray;
        this.percent = percent;
    }

    @Override
    public int compareTo(Word o) {
        // It is better to delegate to built-in Double compare 
        // because all we need to compare doubles
        return Double.compare(this.percent, o.percent);
    }

    @Override
    public String toString() {
        return this.wordName;
    }

}

Во-вторых, наиболее важной частью является реализация алгоритма сортировки. Может быть сложно реализовать их самостоятельно, поэтому я предлагаю изучить их в первую очередь.

Для моего решения это будет обычная реализация алгоритма быстрой сортировки следующим образом:

public class QuickSort {

    private Word[] array;

    public QuickSort(Word... words) {
        this.array = words;
    }

    public Word[] sort(){
        this.sort(this.array, 0, this.array.length-1);
        return this.array;
    }

    private void sort(Word[] array, int begin, int end) {

        //exit condition
        if (begin >= end)
            return;

        Word pivot = array[end];
        int sortIndex = begin;

        for (int i = begin; i < end; i++) {
            // instead of > we use compareTo to externalize comparison logic 
            // greater than (>) means we sort in descending order  
            if (array[i].compareTo(pivot) > 0) {
                Word swap = array[sortIndex];
                array[sortIndex] = array[i];
                array[i] = swap;
                sortIndex++;
            }
        }
        //placing pivot to the sort index
        Word swap = array[sortIndex];
        array[sortIndex] = pivot;
        array[end] = swap;

        this.sort(array, begin, sortIndex-1);
        this.sort(array, sortIndex+1, end);

    }

}

Наконец, вы просто используете вспомогательный класс QuickSort для сортировки вашей коллекции Word и получить отсортированный вывод:

public class WordRecommender {

    String fileName;

    public WordRecommender(String fileName) {
        this.fileName = fileName;
    }

    public static void main(String[] args) {

        ArrayList<Word> objectArray = new ArrayList<Word>();

        objectArray.add(new Word("people" ,0.8));
        objectArray.add(new Word("dogs", 0.4));
        objectArray.add(new Word("cats" ,0.6));

        QuickSort quickSort = new QuickSort(objectArray.toArray(new Word[]{}));
        Word[] sortedWordArray = quickSort.sort();

        //output: [people, cats, dogs]
        System.out.println(Arrays.asList(sortedWordArray));

    }

}