Как я могу отсортировать ArrayList с сортировкой вставок? - PullRequest
Новая
       48

Как я могу отсортировать ArrayList с сортировкой вставок?

0 голосов
/ 16 мая 2019

У меня есть задание, в котором мой учитель просит нас импортировать текстовый файл с ключами 2043 Euromillions в следующем формате: 

1987 45 12 14 39 43 48 8 10
1981 23 12 18 22 29 45 10 12
1980 6 29 31 45 46 50 4 8
2018 19 2 4 16 19 50 6 12
1986 23 1 10 33 38 42 7 12
1986 40 18 23 26 27 36 7 12
...

Я импортировал файл в ArrayList, и мне нужно использовать сортировку вставками для сортировки ключей по дате (первое число - год, а следующее - неделя) и в следующем формате: 

{1987/45} |12|14|39|43|48| |8|10|
{1981/23} |12|18|22|29|45| |10|12|
...

Есть идеи, как отсортировать ключи по дате и сохранить их в Array или ArrayList?

Я импортировал файл в ArrayList, но, если это было хорошей идеей, я попытался отсортировать ArrayList, но безуспешно. 

private static ArrayList<String> ImportedKeys = new ArrayList<String>();

public static void importarChaves() {

String linha;

        int year,week,ball1,ball2,ball3,ball4,ball5,star1,star2;

        File file=new File("Documento/euromilhoes.txt");
        Scanner leitor=null;
        try {
            leitor = new Scanner(file);
        } catch (FileNotFoundException e) {
            System.out.println("File not found");
            e.printStackTrace();
        }
        int count = 0;
        while(leitor.hasNextLine()){

            linha=leitor.nextLine();
            // System.out.println(linha);

            Scanner lerString=new Scanner(linha);

            year=lerString.nextInt();
            week=lerString.nextInt();
            ball1=lerString.nextInt();
            ball2=lerString.nextInt();
            ball3=lerString.nextInt();
            ball4=lerString.nextInt();
            ball5=lerString.nextInt();
            star1=lerString.nextInt();
            star2=lerString.nextInt();

            ImportedKeys.add(linha);

            count++;
            lerString.close();


        }

1 Ответ

1 голос
/ 16 мая 2019

Несколько вещей. Во-первых, сортировка вставкой - это очень специфический тип сортировки, в котором вы сортируете при вставке. То есть в любой момент ваш массив отсортирован. Когда вы добавляете 400-й элемент, он вставляется в правильное место.

Вот что я бы сделал. Во-первых, я бы начал с гораздо более короткого файла с примерами, чтобы ваш вывод был разумным. 10 строк.

Я бы создал объект, который представляет одну строку, но не как строку, а как объект с различными частями. Помните, что вы не можете выполнить сравнение строк, потому что 6-я неделя будет сортироваться после 11-й. Таким образом, ваш объект может содержать числовой год, числовую неделю и затем все остальное.

Тогда я бы сделал это: я бы написал просто метод ввода, который читает файл и создает (несортированный) массив ваших новых объектов. Проверьте это, прочитав ваш файл и распечатав результаты. Это подтвердит, что вы правильно читаете.

Тогда я бы понял несколько понятий.

  1. Пустой список отсортирован.
  2. Список с 1 элементом отсортирован.
  3. Если список отсортирован, вы можете выполнить бинарный поиск по нему.

Что такое бинарный поиск? 

class MyArray extends ArrayList<MyObject> {
    public int insertionPoint(int year, int month {
         return insertionPoint(year, month, 0, length());
    }

    private int insertionPoint(int year, int month, int low, int high) {
        if (low >= high) {
             return low;
        }
        int mid = (low + high) / 2;
        MyObject obj = get(mid);
        if (obj.year < year || (obj.year == year && obj.month < month)) {
            return insertionPoint(year, month, low, mid);
        }
        return insertionPoint(year, month, mid+1, high);
    }
}

Это бинарный поиск. Это ОЧЕНЬ ОЧЕНЬ важная концепция. Ваш список отсортирован, что означает, что вы можете быстро найти существующий объект (или куда должен идти новый объект), разделив список пополам. Допустим, есть 2000 предметов. Вы проверяете 1000-й товар. Если вы ищете место до этого (см. Оператор if), тогда. вам нужно только посмотреть в первой половине списка. В противном случае вы смотрите во второй половине.

Если у вас есть точка вставки, вы можете просто вставить свой НОВЫЙ элемент в список в этой точке. И это список вставки.

Примечание: я пишу код вручную, а не в IDE. Это может быть не идеально.

В общем, когда вы закончите, это ДОЛЖНО быть менее 100 строк кода. Этого должно быть достаточно для определения вашего нового объекта, а также определения отсортированного списка, который знает, как выполнить вставку, и кода для его проверки.

Но хитрость сортировки вставки:

  1. Сохраняйте ваш массив отсортированным по ходу
  2. Понять бинарный поиск
  3. Тебе нужно понять рекурсию. Мой второй метод выше очень рекурсивный. Он разбивает список на более мелкие части, пока не выяснит, куда должен перейти ваш следующий элемент.

Итак, что вы делаете:

  1. Создайте объект MyObject (или как вы его называете).
  2. int location = myList.insertLocation (object.year, object.week)
  3. добавить (местоположение, объект)
...