Сегодня мы рассмотрим реализацию алгоритма сортировки вставками на Scala. Это очень интересный алгоритм сортировки, не быстрый (сложность O(n^2)), но обладающий парой особенностей:
- Не сортирует уже упорядоченные данные
- Позволяет выполнять сортировку динамически выбираемых данных
Для начала случай с сортировкой массива:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def sort[A <% Ordered[A]](source: Array[A]): Array[A] = { val destination = source.clone() (1 to destination.length - 1).foreach { case keyIndex => val key = destination(keyIndex) var destIndex = keyIndex - 1 while (destIndex >= 0 && destination(destIndex) > key) { destination(destIndex + 1) = destination(destIndex) destIndex = destIndex - 1 } destination(destIndex + 1) = key } destination } |
Здесь всё довольно просто, цикл обхода элементов, а внутри процедура выбора места для элемента обходом влево от текущего.
Для реализации сортировки динамически поступающих данных нам понадобиться коллекция с быстрой вставкой элементов (O(1)) и навигацией к соседним элементам за O(1). Подойдёт обычный двусвязный список:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
package org.strangeway.scsc.sys import collection.mutable.ListBuffer class DoubleLinkedNode[A](newNodeValue: A, prevOption: DoubleLinkedNode[A], nextOption: DoubleLinkedNode[A]) { private var prevNode: DoubleLinkedNode[A] = if (prevOption == null) this else prevOption private var nextNode: DoubleLinkedNode[A] = if (nextOption == null) this else nextOption var value: A = newNodeValue def head(nodeValue: A): DoubleLinkedNode[A] = { val node = new DoubleLinkedNode[A](nodeValue, this, nextNode) val oldNextNode = nextNode nextNode = node oldNextNode.prevNode = nextNode node } def tail(nodeValue: A): DoubleLinkedNode[A] = { val node = new DoubleLinkedNode[A](nodeValue, prevNode, this) val oldPrevNode = prevNode prevNode = node oldPrevNode.nextNode = prevNode node } def previous = prevNode def next = nextNode } object DoubleLinkedNodeHead { def apply[A](nodeValue: A) = new DoubleLinkedNode[A](nodeValue, null, null) implicit def DoubleLinkedNodeToList[A](value: DoubleLinkedNode[A]) : List[A] = { val lb = ListBuffer[A](value.value) var cursor = value.next while (cursor != value) { lb += cursor.value cursor = cursor.next } lb.toList } } |
Отдельный класс для списка не используется, нам хватит манипуляций с элементами.
Ну и теперь сам алгоритм:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def sortDynamic[A <% Ordered[A]](source: Iterator[A]): List[A] = { val head = DoubleLinkedNodeHead(source.next()) while (source.hasNext) { val tail: DoubleLinkedNode[A] = head.tail(source.next()) val key : A = tail.value var destNode = tail.previous while (destNode != head.previous && destNode.value > key) { val node = destNode node.next.value = node.value destNode = node.previous } destNode.next.value = key } head } |
Обе функции оперируют объектами типа A, для которого в контексте исполнения определено преобразование (возможно неявное) к Ordered[A].
Результаты тестов показывают, что реализация для динамических данных проигрывает сортировке на массиве. Это происходит из-за накладных расходов на создание объектов двусвязного списка.
| Количество элементов | Сортировка массива, сек | Сортировка динамически поступающих данных, сек |
|---|---|---|
| 1000 | 14 | 50 |
| 10000 | 201 | 366 |
| 100000 | 26850 | 33995 |
Из таблицы видно, что отношение времени выполнения динамического случая к статическому уменьшается при увеличении количества элементов. Динамический метод сортировки очень полезен для работы с буферизованными данными поступающими по сети: он позволяет не дожидаться получения всего массива и во время ожидания новых элементов выполнять сортировку старых.
Удачных алгоритмов и структур данных!
В настоящее время работает в компании JetBrains в команде IntelliJ IDEA Ultimate. Когда выдаётся свободное время, пишет статьи и контрибьютит в проекты с открытым исходным кодом. Обожает реализовывать странные идеи с лозунгом: «А почему бы и нет?».
