Anonymous user
Sorting algorithms/Quicksort: Difference between revisions
→{{header|Ruby}}: ++ sather (a sather guru likely can do it better and using methods or technics I dont know still)
(→{{header|Ruby}}: ++ sather (a sather guru likely can do it better and using methods or technics I dont know still)) |
|||
Line 1,286:
end
end</lang>
=={{header|Sather}}==
<lang sather>class SORT{T < $IS_LT{T}} is
private toarray(v:T):ARRAY{T} is
res ::= #ARRAY{T}(1);
res[0] := v;
return res;
end;
private afilter(a:ARRAY{T}, cmp:ROUT{T,T}:BOOL, p:T):ARRAY{T} is
filtered ::= #ARRAY{T};
loop v ::= a.elt!;
if cmp.call(v, p) then
filtered := filtered.append(toarray(v));
end;
end;
return filtered;
end;
private mlt(a, b:T):BOOL is return a < b; end;
private mgt(a, b:T):BOOL is return a > b; end;
quick_sort(inout a:ARRAY{T}) is
if a.size < 2 then return; end;
pivot ::= a.median;
left:ARRAY{T} := afilter(a, bind(mlt(_,_)), pivot);
right:ARRAY{T} := afilter(a, bind(mgt(_,_)), pivot);
quick_sort(inout left);
quick_sort(inout right);
res ::= #ARRAY{T};
res := res.append(left, toarray(pivot), right);
a := res;
end;
end;</lang>
<lang sather>class MAIN is
main is
a:ARRAY{INT} := |10, 9, 8, 7, 6, -10, 5, 4, 656, -11|;
b ::= a.copy;
SORT{INT}::quick_sort(inout a);
#OUT + a + "\n" + b.sort + "\n";
end;
end;</lang>
The ARRAY class has a builtin sorting method, which is quicksort (but under certain condition an insertion sort is used instead), exactly <code>quicksort_range</code>; this implementation is original.
=={{header|Scala}}==
| |||