Sorting Dojo: Первые шаги

Сегодня решил немного в сортировку углубиться. Интересная алгоритмическая задачка. Их стольковсяких разных есть. Когда-то давно изучал их подробно, а с течением времнеи (и без code reuse) позабывал все. Вот и решил рефрешнуть.

На Википедии есть полно всяких алгоритмов - хорошая точка старта. Но! Во-первых не всегда там выкладывают код на Java (чаще псевдокодом), а во-вторых багов там так же не мало. Значит нужны тесты. Написал чуть чуть кода, потом еще чуть чуть, потом еще... Затянуло, в общем и получился фреймворчик.

Фреймворчик умеет генерировать массив данных заданной величины и рендомом выставлять по нему int числа. Верхнюю границу рендома так же можно выставлять. Тем самым можно сделать так, чтобы было много дублирующихся данных. А это в свою очередь поможет проверить устойчивая ли реализация или нет. Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи.

Чтобы эта проверка (на устойчивость) состоялась надо было еще рядом со значением элементов массива еще и айдишку хранить, чтобы потом по ним относительно оригинала проверять куда мувались элементы. В общем от массива int[] не осталось и следа - создал свой класс, который инкапсулирует в себе массив элементов каждый из которых - айдишка и значение.

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

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

Вот пример самой простой пузырьковой сортировки

public class BubbleSorter implements Sorter {
    @Override
    public void sort(Array data) {
        int size = data.size();
        for (int j=0; j < size - 1; j++) {
            for (int i=0; i < size - j - 1; i++) {
                if (data.get(i).compareTo(data.get(i+1)) > 0) {
                    data.swap(i, i+1);
                }
            }
        }
    }
}

Sorter - это собственно алгоритм сортировки, которому на вход кормится Array

public interface Sorter {
    void sort(Array data);
}

Array - тоже интерфейс, показывающий что клиент может делать с массивом

public interface Array<T extends Comparable> {
    int size();

    void swap(int index1, int index2);

    Element<T> get(int index);

    void set(int index, T value);

    void copy(int fromIndex, int toIndex);

    void set(int index, Element data);

    int compare(int index1, int index2);
}

И вот пишешь свой алгоритм, запускаешь тест и опля!

---------------------------------------------------------
Sorter:BubbleSorter
Stable
Array length:1000
Score:507.0
Operations:{SIZE=1, SET=486138, GET=1485138}
---------------------------------------------------------
Sorter:BubbleFlaggedSorter
Stable
Array length:1000
Score:507.0
Operations:{SIZE=1, SET=486138, GET=1482882}
---------------------------------------------------------
Sorter:BubbleSelectionSorter
Not stable
Array length:1000
Score:576.0
Operations:{SIZE=1, SET=367888, GET=1367744}
---------------------------------------------------------
Sorter:SelectionSorter
Not stable
Array length:1000
Score:997.0
Operations:{SIZE=1, SET=1970, GET=1000970}
---------------------------------------------------------
Sorter:CocktailSorter
Stable
Array length:1000
Score:613.0
Operations:{SIZE=1, SET=486138, GET=1143870}
---------------------------------------------------------
Sorter:GnomeSorter
Stable
Array length:1000
Score:684.0
Operations:{SIZE=1, SET=486138, GET=974260}
---------------------------------------------------------
Sorter:InsertionSorter
Stable
Array length:1000
Score:1365.0
Operations:{SIZE=1, SET=244068, GET=488129}
---------------------------------------------------------
Sorter:QuickSorter
Not stable
Array length:1000
Score:35710.0
Operations:{SIZE=1, SET=6882, GET=21120}
---------------------------------------------------------
Sorter:DualPivotQuickSorter
Not stable
Array length:1000
Score:57100.0
Operations:{SIZE=2, SET=5500, GET=12011}
---------------------------------------------------------

Как-то так.

Самый оптимальный (с моими тестами) алгоритм, что я нашел - мод алгоритма quick sorting Dual Pivot Quicksort, о котором можно почитать тут. Эксперименты на этом не заканчиваются, но времени сегодня больше нет.

Может кому пригодится...