Пользовательский алгоритм сортировки в Java?

Question

Привет, ребята, поэтому я хочу написать небольшую Java программу, которая поможет мне отсортировать список. Представьте, что список выглядит так: Яблоки, Грейпфруты, Бананы, Ананасы, Кокосы

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

Моя идея до сих пор заключалась в том, что это может выглядеть примерно так: 1013 * написано в список. Затем сравнивают грейпфрут и яблоко, и пользователь говорит, что ему нравится больше (здесь яблоки), поэтому грейпфруты перемещаются под яблоками. Затем он сравнивает бананы, например, с яблоками, и пользователь говорит программе, что ему больше нравятся бананы, поэтому он идет выше яблок и больше не нужно сравнивать с грейпфрутом, что экономит много времени. Программа должна обработать несколько сотен записей и сравнений, чтобы сэкономить время, задав меньше вопросов, что сэкономит много времени. Я на правильном пути? Кроме того, что было бы лучшим способом ввода списка, массива, массива или ...?

Как это должно быть реализовано? Есть ли подходящий алгоритм сортировки? Заранее спасибо!

Answer 1

Вы должны построить дерево бинарного поиска.

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

После того, как «дерево предпочтений» было построено, вы можете выполнить итерацию по глубине дерева, назначая добавочные «значения предпочтений» каждому фрукту, и строить Map<String, Integer>, так что вы можете быстро найти любые значения предпочтений фруктов, или порядковый номер сортировки.

Answer 2

Самый простой способ - использовать Collections.sort с пользовательским компаратором, который запрашивает пользовательский ввод.

Scanner sc = new Scanner(System.in);
Collections.sort(fruits, (a, b) -> {
    System.out.println("Do you prefer " + a + " or " + b + "?");
    String preference = sc.next();
    return preference.equals(a) ? -1 : preference.equals(b) ? 1 : 0;
});

Answer 3

Принятый ответ - хорошо, но рассмотрим также эту альтернативу:

Вы можете хранить фрукты в максимальной куче, что можно сделать с помощью ArrayList (когда вы не знаете количество фруктов). заранее) или простой массив.

Когда вы вставляете новый фрукт, он добавляется в конец массива, и когда вы позволяете ему просеивать (согласно алгоритму кучи), вы спрашиваете пользователя результат сравнения (ий), пока фрукт не будет считаться менее любимым, чем тот, с которым сравнивается (или он становится root - с индексом 0).

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