"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())?