Сортировка вставками

Сегодня мы рассмотрим реализацию алгоритма сортировки вставками на Scala. Это очень интересный алгоритм сортировки, не быстрый (сложность O(n^2)), но обладающий парой особенностей:

  1. Не сортирует уже упорядоченные данные
  2. Позволяет выполнять сортировку динамически выбираемых данных

Для начала случай с сортировкой массива:

Здесь всё довольно просто, цикл обхода элементов, а внутри процедура выбора места для элемента обходом влево от текущего.

Для реализации сортировки динамически поступающих данных нам понадобиться коллекция с быстрой вставкой элементов (O(1)) и навигацией к соседним элементам за O(1). Подойдёт обычный двусвязный список:

Отдельный класс для списка не используется, нам хватит манипуляций с элементами.

Ну и теперь сам алгоритм:

Обе функции оперируют объектами типа A, для которого в контексте исполнения определено преобразование (возможно неявное)  к Ordered[A].

Результаты тестов показывают, что реализация для динамических данных проигрывает сортировке на массиве. Это происходит из-за накладных расходов на создание объектов двусвязного списка.

Количество элементов Сортировка массива, сек Сортировка динамически поступающих данных, сек
1000 14 50
10000 201 366
100000 26850 33995

Из таблицы видно, что отношение времени выполнения динамического случая к статическому уменьшается при увеличении количества элементов. Динамический метод сортировки очень полезен для работы с буферизованными данными поступающими по сети: он позволяет не дожидаться получения всего массива и во время ожидания новых элементов выполнять сортировку старых.
Удачных алгоритмов и структур данных!

Yuriy Artamonov on GithubYuriy Artamonov on LinkedinYuriy Artamonov on Twitter
Yuriy Artamonov
Software Developer
До последнего времени Юрий принимал активное участие в разработке опенсорс-фреймворка CUBA Platform, специализируясь на архитектуре и фронтенд-технологиях. Преподавал в Самарском университете разработку приложений для мобильных устройств, основы UI/UX и менторил студентов.

В настоящее время работает в компании JetBrains в команде IntelliJ IDEA Ultimate. Когда выдаётся свободное время, пишет статьи и контрибьютит в проекты с открытым исходным кодом. Обожает реализовывать странные идеи с лозунгом: «А почему бы и нет?».