Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
(→{{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: | Line 945: | ||
% L = [1,2,3,5,10,23,34,42] ? |
% L = [1,2,3,5,10,23,34,42] ? |
||
% yes |
% 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}}== |
=={{header|PureBasic}}== |
||
<lang PureBasic>Procedure insertionSort(Array a(1)) |
<lang PureBasic>Procedure insertionSort(Array a(1)) |