Averages/Median: Difference between revisions
Content added Content deleted
(→{{header|Erlang}}: make quick sort tail recursive) |
|||
| Line 1,301: | Line 1,301: | ||
qs_median([]) -> error; |
qs_median([]) -> error; |
||
qs_median([X]) -> X; |
|||
qs_median([P|_Tail] = List) -> |
qs_median([P|_Tail] = List) -> |
||
TargetPos = length(List)/2 + 0.5, |
TargetPos = length(List)/2 + 0.5, |
||
qs_median(List, TargetPos, P, |
qs_median(List, TargetPos, P, 0). |
||
qs_median([X], 1 |
qs_median([X], 1, _, 0) -> X; |
||
qs_median([X], 1 |
qs_median([X], 1, _, Acc) -> (X + Acc)/2; |
||
| ⚫ | |||
qs_median([P|Tail], TargetPos, P, up, Acc) when TargetPos > 1 -> |
|||
qs_median(Tail, TargetPos - 1, P, up, Acc); |
|||
| ⚫ | |||
Smaller = [X || X <- Tail, X < P], |
Smaller = [X || X <- Tail, X < P], |
||
LS = length(Smaller), |
LS = length(Smaller), |
||
| Line 1,321: | Line 1,318: | ||
(P+LastP)/2; |
(P+LastP)/2; |
||
qs_continue(P, LS, TargetPos, _LastP, SM, _TL, _Acc) when TargetPos == LS + 0.5 -> |
qs_continue(P, LS, TargetPos, _LastP, SM, _TL, _Acc) when TargetPos == LS + 0.5 -> |
||
qs_median(SM, TargetPos - 0.5, P |
qs_median(SM, TargetPos - 0.5, P, P); |
||
qs_continue(P, LS, TargetPos, _LastP, SM, _TL, Acc) when LS + 1 > TargetPos |
qs_continue(P, LS, TargetPos, _LastP, SM, _TL, Acc) when LS + 1 > TargetPos -> |
||
qs_median(SM, TargetPos, P |
qs_median(SM, TargetPos, P, Acc); |
||
qs_continue(P, LS, TargetPos, _LastP, _SM, TL, Acc) -> |
qs_continue(P, LS, TargetPos, _LastP, _SM, TL, Acc) -> |
||
Larger = [X || X <- TL, X >= P], |
Larger = [X || X <- TL, X >= P], |
||
| Line 1,329: | Line 1,326: | ||
case NewPos == 0.5 of |
case NewPos == 0.5 of |
||
true -> |
true -> |
||
qs_median(Larger, 1, P |
qs_median(Larger, 1, P, P); |
||
false -> |
false -> |
||
qs_median(Larger, NewPos, P |
qs_median(Larger, NewPos, P, Acc) |
||
end. |
end. |
||