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

Question

Я создал разные алгоритмы сортировки, но мне нужно проверить, стабильны ли они или нет, используя java - как мне go сделать это?

Answer 1

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

Вот один из подходов для демонстрации что сортировка оказалась стабильной или нестабильной.

1. Создайте список объектов, которые рандомизируют , основываясь на их критериях сортировки .
2. Поддерживая тот же порядок, добавьте последовательный идентификатор к каждому объекту. Этот id должен не быть частью критериев сортировки.
3. Теперь сортируйте их в порядке по возрастанию .

Теперь вы можете бегать по отсортированному списку и проверять только равные элементы, посмотреть, если идентификаторы находятся в порядке возрастания . Если это так, сортировка вела себя как стабильная сортировка . Если это не так, он вел себя как нестабильная сортировка .

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

Но один нестабильный результат доказывает, что сортировка нестабильна.

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

Answer 2

Чтобы проверить стабильность сортировки:

• Создайте 2 (или более) объекта, которые отличаются, но сравниваются равными.
• Добавьте их в список.
• Добавить их в другой список, но в обратном порядке.
• (Необязательно) Добавьте другие объекты до / после / между "равными" объектами.
• Сортировка обоих списков.

Если порядок «равных» объектов оставался в порядке вставки, то весьма вероятно, что сортировка стабильна. Это не гарантия 100%, но сортировка нескольких списков различной длины повышает уровень достоверности теста.

Пример

class StringNum implements Comparable<StringNum> {
    private final String s;
    private final int n;
    public StringNum(String s, int n) {
        this.s = s;
        this.n = n;
    }
    @Override
    public int compareTo(StringNum that) {
        return this.s.compareTo(that.s); // Only order by string, not by number
    }
    @Override
    public String toString() {
        return this.s + ":" + this.n;
    }
}

StringNum a1 = new StringNum("A", 1);
StringNum b1 = new StringNum("B", 1);
StringNum b2 = new StringNum("B", 2);
StringNum c1 = new StringNum("C", 1);
StringNum c2 = new StringNum("C", 2);
StringNum c3 = new StringNum("C", 3);
StringNum d1 = new StringNum("D", 1);
StringNum d2 = new StringNum("D", 2);
StringNum d3 = new StringNum("D", 3);
StringNum d4 = new StringNum("D", 4);
StringNum e1 = new StringNum("E", 1);
StringNum e2 = new StringNum("E", 2);
StringNum e3 = new StringNum("E", 3);
StringNum e4 = new StringNum("E", 4);
StringNum e5 = new StringNum("E", 5);
List<StringNum> list1 = new ArrayList<>(Arrays.asList(a1, b1, c1, d1, e1, b2, c2, d2, e2, c3, d3, e3, d4, e4, e5));
List<StringNum> list2 = new ArrayList<>(Arrays.asList(e5, e4, e3, e2, e1, d4, d3, d2, d1, c3, c2, c1, b2, b1, a1));
Collections.sort(list1);
Collections.sort(list2);
System.out.println(list1);
System.out.println(list2);

Выходные данные

[A:1, B:1, B:2, C:1, C:2, C:3, D:1, D:2, D:3, D:4, E:1, E:2, E:3, E:4, E:5]
[A:1, B:2, B:1, C:3, C:2, C:1, D:4, D:3, D:2, D:1, E:5, E:4, E:3, E:2, E:1]

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