Anonymous user
Sorting algorithms/Insertion sort: Difference between revisions
formatting
(+ AutoHotkey) |
(formatting) |
||
Line 2:
{{Sorting Algorithm}}
An [[O]](n<sup>2</sup>) sorting algorithm which moves elements one at a time into the correct position. The algorithm is as follows (from the [[wp:Insertion_sort#Algorithm|wikipedia]]):
'''function''' ''insertionSort''(array A)
Writing the algorithm for integers will suffice.
Line 31:
Item(J + 1) := Value;
end loop;
end Insertion_Sort;</lang>
</lang>▼
=={{header|ALGOL 68}}==
{{trans|Ada}}
Line 156 ⟶ 155:
(defun insertion-sort (list)
(reduce #'insert list :initial-value nil))</lang>
</lang>▼
=={{header|D}}==
Line 181 ⟶ 179:
insertionSort(a2);
writefln(a2);
▲}</lang>
=={{header|E}}==
Line 207 ⟶ 204:
=={{header|Forth}}==
<pre>: insert ( start end -- start )▼
▲: insert ( start end -- start )
dup @ >r ( r: v ) \ v = a[i]
begin
Line 229 ⟶ 225:
=={{header|Fortran}}==
<lang fortran>SUBROUTINE Insertion_Sort(a)
REAL, INTENT(in out), DIMENSION(:) :: a
REAL :: temp
Line 244 ⟶ 239:
a(j+1) = temp
END DO
END SUBROUTINE Insertion_Sort</lang>
In Fortran 90 and above the intrinsic function CSHIFT can be used to shift the elements in the array but in practice is slower than the above example
<lang fortran>DO i = 2, SIZE(a)
j = i - 1
DO WHILE (j>=1 .AND. a(j) > a(i))
Line 254 ⟶ 247:
END DO
a(j+1:i) = cshift(a(j+1:i),-1)
END DO</lang>
=={{header|Haskell}}==
<lang haskell>insert x [] = [x]
insert x (y:ys) | x <= y = x:y:ys
insert x (y:ys) | otherwise = y:(insert x ys)
Line 268 ⟶ 259:
-- Example use:
-- *Main> insertionSort [6,8,5,9,3,2,1,4,7]
-- [1,2,3,4,5,6,7,8,9]</lang>
=={{header|Java}}==
<lang java5>public static void insertSort(int[] A){
for(int i = 1; i < A.length; i++){
int value = A[i];
Line 283 ⟶ 272:
A[j + 1] = value;
}
▲}</lang>
=={{header|Modula-3}}==
Line 317 ⟶ 305:
=={{header|Perl}}==
<lang perl>sub insertion_sort {
$arr = shift;
for ($i = 0; $i <= $#{$arr}; $i++) {
Line 332 ⟶ 319:
$a = [4, 65, 2, -31, 0, 99, 83, 782, 1];
insertion_sort($a);
print join(' ', @{$a}), "\n";</lang>
Output:
-31 0 1 2 4 65 83 99 782
=={{header|Prolog}}==
<lang prolog>insert_sort(L1,L2) :-▼
▲insert_sort(L1,L2) :-
insert_sort_intern(L1,[],L2).
Line 352 ⟶ 337:
!.
insert([H|T],X,[H|T2]) :-
insert(T,X,T2).</lang>
% Example use:
Line 358 ⟶ 343:
% L = [1,2,3,5,10,23,34,42] ?
% yes
=={{header|Python}}==
<lang python>def insertion_sort(l):
for i in xrange(1, len(l)):
j = i-1
Line 369 ⟶ 352:
l[j+1] = l[j]
j -= 1
l[j+1] = key</lang>
===Insertion sort with binary search===
<lang python>def insertion_sort_bin(seq):
for i in range(1, len(seq)):
key = seq[i]
Line 387 ⟶ 368:
up = middle
# insert key at position ``low``
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]</lang>
=={{header|REALbasic}}==
<lang realbasic> Sub InsertionSort(theList() as Integer)
for insertionElementIndex as Integer = 1 to UBound(theList)
dim insertionElement as Integer = theList(insertionElementIndex)
Line 403 ⟶ 381:
theList(j + 1) = insertionElement
next
End Sub</lang>
=={{header|Ruby}}==
Line 480 ⟶ 457:
}
</pre>
<pre>
cat to.sort | selectionsort
| |||