## "Fossies" - the Fresh Open Source Software Archive ### Member "ponyc-0.33.2/packages/collections/sort.pony" (3 Feb 2020, 2488 Bytes) of package /linux/misc/ponyc-0.33.2.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Pony source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "sort.pony": 0.33.1_vs_0.33.2.

```    1 primitive Sort[A: Seq[B] ref, B: Comparable[B] #read]
2   """
3   Implementation of dual-pivot quicksort.  It operates in-place on the provided Seq, using
4   a small amount of additional memory. The nature of the element-realation is expressed via
5   the supplied comparator.
6
7   (The following is paraphrased from [Wikipedia](https://en.wikipedia.org/wiki/Quicksort).)
8
9   Quicksort is a common implementation of a sort algorithm which can sort items of any type
10   for which a "less-than" relation (formally, a total order) is defined.
11
12   On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case,
13   it makes O(n2) comparisons, though this behavior is rare.  Multi-pivot implementations
14   (of which dual-pivot is one) make efficient use of modern processor caches.
15
16   ## Example program
17   The following takes an reverse-alphabetical array of Strings ("third", "second", "first"),
18   and sorts it in place alphabetically using the default String Comparator.
19
20   It outputs:
21
22   > first
23   > second
24   > third
25
26   ```pony
27   use "collections"
28
29   actor Main
30     new create(env:Env) =>
31       let array = [ "third"; "second"; "first" ]
32       let sorted_array = Sort[Array[String], String](array)
33       for e in sorted_array.values() do
34         env.out.print(e) // prints "first \n second \n third"
35       end
36   ```
37   """
38   fun apply(a: A): A^ =>
39     """
40     Sort the given seq.
41     """
42     try _sort(a, 0, a.size().isize() - 1)? end
43     a
44
45   fun _sort(a: A, lo: ISize, hi: ISize) ? =>
46     if hi <= lo then return end
47     // choose outermost elements as pivots
48     if a(lo.usize())? > a(hi.usize())? then _swap(a, lo, hi)? end
49     (var p, var q) = (a(lo.usize())?, a(hi.usize())?)
50     // partition according to invariant
51     (var l, var g) = (lo + 1, hi - 1)
52     var k = l
53     while k <= g do
54       if a(k.usize())? < p then
55         _swap(a, k, l)?
56         l = l + 1
57       elseif a(k.usize())? >= q then
58         while (a(g.usize())? > q) and (k < g) do g = g - 1 end
59         _swap(a, k, g)?
60         g = g - 1
61         if a(k.usize())? < p then
62           _swap(a, k, l)?
63           l = l + 1
64         end
65       end
66       k = k + 1
67     end
68     (l, g) = (l - 1, g + 1)
69     // swap pivots to final positions
70     _swap(a, lo, l)?
71     _swap(a, hi, g)?
72     // recursively sort 3 partitions
73     _sort(a, lo, l - 1)?
74     _sort(a, l + 1, g - 1)?
75     _sort(a, g + 1, hi)?
76
77   fun _swap(a: A, i: ISize, j: ISize) ? =>
78     a(j.usize())? = a(i.usize())? = a(j.usize())?
```