Сортировка, выбор и поиск

Сортировка

Поскольку Spire предоставляет специализированный класс типов упорядочения, имеет смысл также предоставить свои собственные методы для выполнения операций на основе Order. Эти методы определены в массивах и "возникают на месте", изменяя массив. Другие коллекции могут воспользоваться преимуществами сортировки путем преобразования в массив, последующей сортировки и обратного преобразования (что уже делает платформа коллекций Scala в большинстве случаев). Таким образом, Spire поддерживает как изменяемые массивы, так и неизменяемые коллекции.

Методы сортировки можно найти в объекте spire.math.Sorting. Это:

• quickSort: самый быстрый, \(O(n*log(n))\), нестабильный с потенциалом \(O(n^{2})\) в худшем случае
• mergeSort: также быстрый, \(O(n*log(n))\), стабильный, но выделяет дополнительное временное пространство
• insertionSort: \(O(n^{2})\), но стабильный и быстрый для небольших массивов
• sort: псевдоним для quickSort

Оба mergeSort и quickSort делегируют insertionSort при работе с массивами (или срезами) ниже определенной длины. Поэтому правильнее было бы назвать их гибридными сортировками.

Выборка

Методы выбора можно найти в аналогичном объекте spire.math.Selection. Учитывая массив и индекс k, эти методы помещают k-й наибольший элемент в позицию k, гарантируя, что все предыдущие элементы меньше или равны, а все последующие элементы больше или равны k-му элементу.

Определено два метода:

• quickSelect: обычно быстрее, нестабильнее, потенциально плохой в худшем случае
• linearSelect: обычно медленнее, но с гарантированной линейной сложностью
• select: псевдоним для quickSelect

Поиск

Методы поиска расположены в объекте spire.math.Searching. Учитывая отсортированный массив (или индексированную последовательность), эти методы найдут индекс нужного элемента (или вернут -1, если он не найден).

• search(array, item): находит индекс item в array.
• search(array, item, lower, upper): поиск осуществляется только между lower и upper.

Поиск также поддерживает более эзотерический метод: minimalElements. Этот метод возвращает минимальные элементы частично упорядоченного набора.

Ссылки:

• Spire home page