Skip to content

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

[Source]

Implementation of dual-pivot quicksort. It operates in-place on the provided Seq, using a small amount of additional memory. The nature of the element-realation is expressed via the supplied comparator.

(The following is paraphrased from Wikipedia.)

Quicksort is a common implementation of a sort algorithm which can sort items of any type for which a "less-than" relation (formally, a total order) is defined.

On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Multi-pivot implementations (of which dual-pivot is one) make efficient use of modern processor caches.

Example program

The following takes an reverse-alphabetical array of Strings ("third", "second", "first"), and sorts it in place alphabetically using the default String Comparator.

It outputs:

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
  ```


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

Constructors

create

[Source]

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

Returns


Public Functions

apply

[Source]

Sort the given seq.

fun box apply(
  a: A)
: A^

Parameters

  • a: A

Returns

  • A^

eq

[Source]

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

Parameters

  • that: Sort[A, B] val

Returns


ne

[Source]

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

Parameters

  • that: Sort[A, B] val

Returns


Private Functions

_sort

[Source]

fun box _sort(
  a: A,
  lo: ISize val,
  hi: ISize val)
: None val ?

Parameters

Returns


_swap

[Source]

fun box _swap(
  a: A,
  i: ISize val,
  j: ISize val)
: None val ?

Parameters

Returns