Java: сортировка элементов

Question

Я знаю, что мы обычно используем java.util.Arrays.sort(Object[], Comparator). JavaDoc говорит, что это модифицированная сортировка слиянием.

Но мне нужен алгоритм сортировки, который сравнивает каждый объект с каждым объектом. У меня будет много элементов, порядок которых не имеет значения. Но есть некоторые элементы, которые действительно должны идти после определенного другого элемента (не обязательно последовательно). И я думаю (но не знаю), что слияния недостаточно ...

Возможно, то, чего я хочу достичь, даже не называется сортировкой ?

Нужно ли внедрять такую ​​систему самостоятельно или для этого есть что-то?

---

Пример:

Obj1, Obj2, Obj3, Obj4

Порядок следующих пар не имеет значения (что означает, что мой Компаратор должен вернуть 0):

Obj1, Obj2 (*)
Obj1, Obj3
Obj2, Obj3
Obj2, Obj4 (*)
Obj3, Obj4

Но! Действительно необходимо, чтобы за Obj4 следовал Obj1 .

Из-за двух (*) пар это математически означает, что Obj1 == Obj4.

Будет ли он работать с помощью mergesort?

Спасибо

Answer 1

Похоже, у вас есть набор DAG (ациклические ориентированные графы).Я думаю, вам нужно смоделировать это, а затем выполнить топологическую сортировку каждого из них.Один подход:

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

Для всех элементов без прямых зависимостей выведите элемент и удалите его из hashMap.Повторяйте, пока hashmap не станет пустым.

Если списки зависимостей часто бывают длинными, это будет неэффективно.Он предназначен для среднего числа прямых зависимостей до 5 или около того.Если производительность является проблемой из-за того, что выполняется слишком много проходов «Повторить, пока хэш-карта пуста», следует использовать двунаправленную структуру данных для представления графов зависимостей или, возможно, список записей карты, которые имеют только одну зависимость от этого проходаи, следовательно, являются сильными кандидатами на следующий проход.

Вот непроверенный эскиз:

class Obj           { String id;    }

class ObjWrapper    {
    String id;
    Obj obj;
    String[] depends; // may be null, may have null entries

    public ObjWrapper(Obj obj, String[] depends) {
        this.id = obj.id;
        this.obj = obj;
        if ( depends != null )
            this.depends = Arrays.copyOf(depends, depends.length);
    }
}

// order the objects by dependency. 
ArrayList<Obj> orderObjs(Iterable<ObjWrapper> objs)
{
    ArrayList<Obj> output = new ArrayList();
    HashMap<String, ObjWrapper> objMap = new HashMap();
    for ( ObjWrapper obj : objs )  
        objMap.put(obj.id, obj);  
    while ( !objMap.isEmpty() ) {
        Iterator<ObjWrapper> iter = objMap.values().iterator();
        while ( iter.hasNext() ) {
            ObjWrapper objWrapper = iter.next();
            if ( !hasDependencies(objWrapper, objMap) ) {
                output.add(objWrapper.obj);
                // must use iter to remove from hash, or bad things happen.
                iter.remove();  
            }
        }
    }
    return output;
}

boolean hasDependencies(ObjWrapper objWrapper, 
                        HashMap<String, ObjWrapper> objMap)
{
    if ( objWrapper.depends == null ) return false;
    for ( String depend : objWrapper.depends )   {
        if ( depend != null ) 
            if ( objMap.containsKey(depend) )
                return true;
            else
                depend = null;  // to speed up future passes
    }
    return false;
}

Answer 2

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

Answer 3

Вы реализовали компаратор (и передали его в стандартную сортировку слиянием), что-то вроде этого:

int compare(Object o1, Object o2) {
  if (o1 instanceOf NotMatter) {
     if (o2 instanceOf NotMatter) {
        return 0;
     }
     return -1;
  }
  if (o2 instanceOf NotMatter) {
     return 1;
  }

  // ok, now we have two important objects
  if (o1.better(o2) {
     return 1;
  }
  if (o2.better(o1) {
     return -1;
  }
  return 0;
}

Answer 4

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

Попробуйтечтобы формально (математически) выразить конечный порядок, который вам нужен.

Тот факт, что порядок двух элементов не имеет значения, не означает, что ваш компаратор должен вернуть 0. Он должен вернуть 0, если они равны.

Answer 5

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

edit Теперь, когда вы добавили пример, я не думаю, что вам даже нужна сортировка. Допустим, элементы X, Y и Z должны идти после некоторого элемента A. Все, что вам нужно сделать, это сдвинуть X, Y и Z в конец списка. Это можно сделать за O(n) раз, а не за O(n logn).

.

Кроме того, вы можете переместить А в начало списка.