Доброго времени суток!
После телефонного собеседования в одну известную компанию, где меня попросили перечислить несколько видов сортировок (я назвал 10, к слову), я слегка озадачился этим вопросом.
Подумав минут 30 над этой проблемой, загуглив какие ещё есть виды сортировок, наткнулся на сортировку подсчётом. И пришёл к выводу, что её можно улучшить, что и постарался сделать.
Итак. Берём сортировку подсчётом и деревом.
Строим дерево Пар (Ключ, Количество), где Ключ отвечает за элемент массива, а Количество — количество повторений этого эл-та массива. Дерево, естественно, сбалансированное, АВЛ или чёрно-красное, но у АВЛ слишком жёсткие требования, так что второй вариант предпочтительнее.
Далее всё логично. Добавляем все элементы массива в Пару, а Пару ищем в дереве (чтобы избежать пересоздания объектов используем заранее созданную Пару, у которой меняем Ключ. Здесь Количество нас не интересует, поскольку мы ищем соответствие исключительно по Ключу). Если такой Ключ уже есть, увеличиваем Количество, иначе добавляем новую Пару (Ключ, 1).
Переписываем массив, удаляя каждый раз вершину и записывая Ключ столько раз, сколько у него Количество.
В худшем случае получится O(n log n) времени и O(n) дополнительной памяти. В лучшем — O(n) времени и O(1) памяти. Нетрудно видеть, что данная сортировка лучше всего работает в случае, когда минимально возможное множество X, которому принадлежат все элементы массива, невелико относительно размерности массива. В противном случае константа будет хуже, чем у сортировки деревом (из-за расходов по созданию пар).
Тесты:
1. Писал на Java
2. Чтобы не реализовывать дерево самому, для описанного алгоритма использовал TreeSet, который работает на чёрно-красном дереве, обычный ArrayList и встроенную сортировку (list.sort()) в качестве ориентира для сравнения (выбрал ArrayList, поскольку он реализован на массиве, но, в отличие от int[] работает с объектами. Таким образом, условия получаются равными, ведь TreeSet тоже работает с объектами, а не с int)
Испытания проводил на 10 млн элементов массива, которые принимали значение:
[0; 10] — мой алгоритм выигрывает в скорости примерно в 4-4,5 раза
[0; 100] — мой алгоритм выигрывает в скорости примерно в 3-3,5 раза
[0; 1000] — мой алгоритм выигрывает в скорости примерно в 2-3 раза
[0; 10_000] — мой алгоритм выигрывает в скорости примерно в 1,6-2 раза
[0; 100_000] — мой алгоритм выигрывает в скорости примерно в 1,3-1,45 раза
[0; 1000_000] — мой алгоритм проиграл в скорости примерно в 1,1-1,2 раза
Надеюсь, что кому-то окажутся полезными эта статья с моими размышлениями и новая сортировка, которую я в свою честь назвал UsatovSort, не пропадут зря!
Исходный код на Java:
static void usatovSort(Integer[] arr) {
TreeSet<MyPair> tree = new TreeSet<>();
MyPair temp; // ссылка на Пару, которую мы теряем при поиске в TreeSet
MyPair mp = new MyPair(); // Пара, которая не теряется при поиске
for (int i : arr) {
temp = mp;
temp.first = i;
temp = tree.ceiling(temp);
if (temp != null && temp.first == i) //порядок условий важнен, т.к
//если первое не выполняется, то проверка второго не производится
temp.second++;
else tree.add(new MyPair(i, 1));
}
int ptr = 0; // индекс по которому записываем очередной элемент массива
while (!tree.isEmpty()) {
temp = tree.pollFirst();
for (int i = 0; i < temp.second; i++)
arr[ptr++] = temp.first;
}
}
class MyPair implements Comparable<MyPair> {
int first; // в нашем случае - Ключ
int second; // в нашем случае - Количество
public MyPair() {
}
public MyPair(int first, int second) {
this.first = first;
this.second = second;
}
@Override
public int compareTo(MyPair o) {
return first - o.first;
}
}
Автор: человек со стажем
