mirror of
https://github.com/roc-lang/roc.git
synced 2025-08-05 12:48:01 +00:00
75 lines
2.2 KiB
Text
75 lines
2.2 KiB
Text
module [sort_by, sort_with, show]
|
|
|
|
show : List I64 -> Str
|
|
show = \list ->
|
|
if List.is_empty(list) then
|
|
"[]"
|
|
else
|
|
content =
|
|
list
|
|
|> List.map(Num.to_str)
|
|
|> Str.join_with(", ")
|
|
|
|
"[${content}]"
|
|
|
|
sort_by : List a, (a -> Num *) -> List a
|
|
sort_by = \list, to_comparable ->
|
|
sort_with(list, \x, y -> Num.compare(to_comparable(x), to_comparable(y)))
|
|
|
|
Order a : a, a -> [LT, GT, EQ]
|
|
|
|
sort_with : List a, (a, a -> [LT, GT, EQ]) -> List a
|
|
sort_with = \list, order ->
|
|
n = List.len(list)
|
|
|
|
quicksort_help(list, order, 0, (n - 1))
|
|
|
|
quicksort_help : List a, Order a, U64, U64 -> List a
|
|
quicksort_help = \list, order, low, high ->
|
|
if low < high then
|
|
when partition(low, high, list, order) is
|
|
Pair(partition_index, partitioned) ->
|
|
partitioned
|
|
|> quicksort_help(order, low, Num.sub_saturated(partition_index, 1))
|
|
|> quicksort_help(order, (partition_index + 1), high)
|
|
else
|
|
list
|
|
|
|
partition : U64, U64, List a, Order a -> [Pair U64 (List a)]
|
|
partition = \low, high, initial_list, order ->
|
|
when List.get(initial_list, high) is
|
|
Ok(pivot) ->
|
|
when partition_help(low, low, initial_list, order, high, pivot) is
|
|
Pair(new_i, new_list) ->
|
|
Pair(new_i, swap(new_i, high, new_list))
|
|
|
|
Err(_) ->
|
|
Pair(low, initial_list)
|
|
|
|
partition_help : U64, U64, List c, Order c, U64, c -> [Pair U64 (List c)]
|
|
partition_help = \i, j, list, order, high, pivot ->
|
|
if j < high then
|
|
when List.get(list, j) is
|
|
Ok(value) ->
|
|
when order(value, pivot) is
|
|
LT | EQ ->
|
|
partition_help((i + 1), (j + 1), swap(i, j, list), order, high, pivot)
|
|
|
|
GT ->
|
|
partition_help(i, (j + 1), list, order, high, pivot)
|
|
|
|
Err(_) ->
|
|
Pair(i, list)
|
|
else
|
|
Pair(i, list)
|
|
|
|
swap : U64, U64, List a -> List a
|
|
swap = \i, j, list ->
|
|
when Pair(List.get(list, i), List.get(list, j)) is
|
|
Pair(Ok(at_i), Ok(at_j)) ->
|
|
list
|
|
|> List.set(i, at_j)
|
|
|> List.set(j, at_i)
|
|
|
|
_ ->
|
|
[]
|