Сортировка

Оптимизация сортировки вставками в Java

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

Ниже представлена одна из возможных реализаций этого алгоритма на Java:

При выполнении программы левая, от текущего элемента сортировки, часть массива будет отсортированной по возрастанию, правая часть массива не сортирована. Ища нужную позицию для вставки, мы последовательно сравниваем проверяемый элемент с каждым элементом в уже отсортированной части массива, двигаясь справа  налево, при этом поэлементно смещаем массив, пока не найдем нужную позицию. Всё вроде бы хорошо с алгоритмом: простота, нетребовательность к памяти, но есть одна проблема — его асимптотическая сложность равняется О(n²), т.е. скорость сортировки очень сильно снижается с увеличением количества элементов сортируемого массива.

Есть способ немного оптимизировать данный алгоритм и увеличить производительность. Так как основные накладные расходы при сортировке у нас уходят на поиск индекса для вставки и на смещение отсортированной части массива, то мы можем воспользоваться парой полезных инструментов (в контексте Java):

  1. Arrays.binarySearch(…).
  2. System.arraycopy(…).

Что нам даст применение этих инструментов?

Arrays.binarySearch()  (JavaDoc) позволит нам найти требуемый для вставки элемента индекс и уменьшить количество операций сравнения при его поиске. Асимптотическая сложность O(log(n)). Более подробно с работой алгоритма бинарного поиска можно ознакомиться по ссылке (wiki).

System.arraycopy(…) (JavaDoc),  в свою очередь, позволит сократить количество операций копирования, заменяя поэлементное смещение на групповое:

System.arraycopyгде:

k — текущая позиция в сортируемом массиве.

index — индекс ячейки найденный с помощью Arrays.binarySearch(…) , куда требуется вставить текущий элемент arr[k],

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

Помимо этого, метод  System.arraycopy(…) в Java реализован нативно, т.е. его код написан на более низком уровне и оптимизирован под операционную систему и архитектуру машины.

 

У коллег, впервые сталкивающихся с Arrays.binarySearch, могут возникнуть затруднения с возвращаемым индексом и его значениями. Если заглянуть в исходники, то суть метода в том, что он возвращает конкретный индекс в случае нахождения в массиве искомого значения, например, для массива [1],[2],[3],[7],[8],[9]  поиск значения [7] выдаст результат index = 3. А при поиске отсутствующего в массиве элемента он выдаст индекс ячейки с максимально приближенным, в соответствующем направлении, значением к искомому, но в отрицательном значении и увеличенном на единицу:  -(low + 1)

Например:

  • при поиске [-6] возвращаемое значение будет index = -1,
  • при поиске [10] возвращаемое значение будет index = -7,
  • при поиске [5] возвращаемое значение будет index = -4,

Зная про хитрость с отрицательными значениями и увеличением на единицу, мы можем абсолютно точно получить требуемый индекс для вставки нашего элемента. Делаем проверку if (index < 0) { корректируем индекс}  и методом System.arraycopy(arr, index, arr, index + 1, k — index) смещаем соответствующую отсортированную часть.

 

Как работает System.arraycopy ? Очень просто! Он принимает на входе несколько параметров (Object src,  int  srcPos, Object dest, int destPos, int length)  и копирует группу ячеек длиной int length из массива-источника Object src, начиная с позиции int srcPos в массив-получатель Object dest в позицию  int destPos.

Например для массивов

int[] src = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

int[] dest= new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

выполнение команды System.arraycopy(src, 4, dest, 2, 5); приведет к копированию части массива src в массив dest с результатом [0, 0, 4, 5, 6, 7, 8, 0, 0, 0]

System.arraycopy

В контексте оптимизации нашего алгоритма сортировки вставками мы можем в качестве массива-получателя использовать массив-источник: System.arraycopy(src, 3, src, 4, 3), тем самым копируя свою часть внутрь себя:

System.arraycopy

Далее нам остается только скопировать, предварительно сохраненный в отдельную переменную, элемент [6] в новую позицию:

System.arraycopy

Примененные выше инструменты позволяют сократить время выполнения метода на 28,4% при сортировке массива состоящего из 262144 рандомных элементов на машине с процессором Core i5-750@2,67GHz. Неплохо!

Пример оптимизации алгоритма представленного в начале статьи
  • Сергей

    А если перед 5-й строкой вставить if (newElement > arr[k — 1]) continue; не будет ли это быстрее? 🙂

    • Vadim Dyachenko

      Сделал замеры — на полностью рандомном массиве прироста нет. А вот если массив нужно «досортировать», то прирост скорости, я думаю, будет существенный.