Сортировка[A: Последовательность[B] ссылка, B: Сравниваемый[B] #чтение]

[Источник]

Реализация сортировки с двумя опорными значениями (dual-pivot quicksort). Она работает на месте с предоставленной Последовательностью, используя небольшое количество дополнительной памяти. Характер отношения элементов выражается через предоставленный компаратор.

(Следующее — это перефразированное описание из Википедии.)

Быстрая сортировка — распространённая реализация алгоритма сортировки, который может сортировать элементы любого типа, для которых определено отношение «меньше, чем» (формально — полная упорядоченность).

В среднем алгоритм выполняет O(n log n) сравнений для сортировки n элементов. В худшем случае он выполняет O(n²) сравнений, хотя такое поведение встречается редко. Реализации с несколькими опорными значениями (в том числе с двумя) эффективно используют кэш современных процессоров.

Пример программы

Следующий пример берёт массив строк в обратном алфавитном порядке ("third", "second", "first") и сортирует его на месте в алфавитном порядке, используя по умолчанию компаратор строк.

Вывод:

first second third

use "collections"

actor Main 
  new create(env:Env) => 
    let array = [ "third"; "second"; "first" ]
    let sorted_array = Sort[Array[String], String](array)
    for e in sorted_array.values() do
      env.out.print(e) // prints "first \n second \n third"
    end

primitive val Sort[A: Seq[B] ref, B: Comparable[B] #read]

Конструкторы

create

[Источник]

new val create()
: Sort[A, B] val^

Возвращаемое значение

• Сортировка[A, B] значение^

Открытые функции

apply

[Источник]

Сортирует заданную последовательность.

fun box apply(
  a: A)
: A^

Параметры

• a: A

Возвращаемое значение

• A^

eq

[Источник]

fun box eq(
  that: Sort[A, B] val)
: Bool val

Параметры

• that: Сортировка[A, B] значение

Возвращаемое значение

• Булево значение

ne

[Источник]

fun box ne(
  that: Sort[A, B] val)
: Bool val

Параметры

• that: Сортировка[A, B] значение

Возвращаемое значение

• Булево значение