sort.pony (ponyc-0.33.1) | : | sort.pony (ponyc-0.33.2) | ||
---|---|---|---|---|

skipping to change at line 22 | skipping to change at line 22 | |||

On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, | 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 impleme ntations | it makes O(n2) comparisons, though this behavior is rare. Multi-pivot impleme ntations | |||

(of which dual-pivot is one) make efficient use of modern processor caches. | (of which dual-pivot is one) make efficient use of modern processor caches. | |||

## Example program | ## Example program | |||

The following takes an reverse-alphabetical array of Strings ("third", "second ", "first"), | The following takes an reverse-alphabetical array of Strings ("third", "second ", "first"), | |||

and sorts it in place alphabetically using the default String Comparator. | and sorts it in place alphabetically using the default String Comparator. | |||

It outputs: | It outputs: | |||

first | > first | |||

second | > second | |||

third | > third | |||

```pony | ```pony | |||

use "collections" | use "collections" | |||

actor Main | actor Main | |||

new create(env:Env) => | new create(env:Env) => | |||

let array = [ "third"; "second"; "first" ] | let array = [ "third"; "second"; "first" ] | |||

let sorted_array = Sort[Array[String], String](array) | let sorted_array = Sort[Array[String], String](array) | |||

for e in sorted_array.values() do | for e in sorted_array.values() do | |||

env.out.print(e) // prints "first \n second \n third" | env.out.print(e) // prints "first \n second \n third" | |||

end | end | |||

``` | ``` | |||

""" | """ | |||

fun apply(a: A): A^ => | fun apply(a: A): A^ => | |||

""" | """ | |||

Sort the given seq. | Sort the given seq. | |||

""" | """ | |||

try _sort(a, 0, a.size().isize() - 1)? end | try _sort(a, 0, a.size().isize() - 1)? end | |||

a | a | |||

fun _sort(a: A, lo: ISize, hi: ISize) ? => | fun _sort(a: A, lo: ISize, hi: ISize) ? => | |||

if hi <= lo then return end | if hi <= lo then return end | |||

End of changes. 3 change blocks. | ||||

12 lines changed or deleted | | 12 lines changed or added |