Anonymous user
Sorting algorithms/Insertion sort: Difference between revisions
→{{header|Prolog}}
(→{{header|Javascript}}: An insertion sort should have the property that nearly sorted lists sort in linear time and the splice method didnt work that way.) |
|||
Line 945:
% L = [1,2,3,5,10,23,34,42] ?
% yes
===Functional approach===
Works with SWI-Prolog.<br>
Insertion sort inserts elements of a list in a sorted list. So we can use foldl to sort a list.
<lang Prolog>% insertion sort
isort(L, LS) :-
foldl(insert, [], L, LS).
% foldl(Pred, Init, List, R).
foldl(_Pred, Val, [], Val).
foldl(Pred, Val, [H | T], Res) :-
call(Pred, Val, H, Val1),
foldl(Pred, Val1, T, Res).
% insertion in a sorted list
insert([], N, [N]).
insert([H | T], N, [N, H|T]) :-
N =< H, !.
insert([H | T], N, [H|L1]) :-
insert(T, N, L1).
</lang>
Example use:
<pre> ?- isort([2,23,42,3,10,1,34,5],L).
L = [1,2,3,5,10,23,34,42]
</pre>
=={{header|PureBasic}}==
<lang PureBasic>Procedure insertionSort(Array a(1))
| |||