Rosetta Code

Sorting algorithms/Insertion sort: Difference between revisions

Page Discussion

Sorting algorithms/Insertion sort (view source)

Revision as of 21:57, 29 January 2009

9 bytes removed ,  15 years ago
m
Links, formatting, more code -> lang changes
(→‎{{header|C}}: fixed broken tags for code highlighting)
m (Links, formatting, more code -> lang changes)
Line 1:
[[Category:Less Than 20 Examples]]{{task|Sorting Algorithms}}
{{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 [http[wp://en.wikipedia.org/wiki/Insertion_sort#Algorithm |wikipedia]]):
insertionSort(array A)
for i = 1 to length[A]-1 do
Line 14:
 
=={{header|Ada}}==
<codelang ada>type Data_Array is array(Natural range <>) of Integer;
procedure Insertion_Sort(Item : in out Data_Array) is
Line 32:
end loop;
end Insertion_Sort;
</codelang>
=={{header|ALGOL 68}}==
{{trans|Ada}}
Line 104:
 
=={{header|Common Lisp}}==
<codelang lisp>(defun span (predicate list)
(let ((tail (member-if-not predicate list)))
(values (ldiff list tail) tail)))
Line 117:
(defun insertion-sort (list)
(reduce #'insert list :initial-value nil))
</codelang>
 
=={{header|D}}==
<codelang d>import std.stdio: writefln;
void insertionSort(T)(T[] A) {
Line 142:
writefln(a2);
}
</codelang>
=={{header|Forth}}==
<pre>
Line 166:
 
=={{header|Fortran}}==
<codelang fortran>
SUBROUTINE Insertion_Sort(a)
REAL, INTENT(in out), DIMENSION(:) :: a
Line 182:
END DO
END SUBROUTINE Insertion_Sort
</codelang>
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
<codelang fortran>
DO i = 2, SIZE(a)
j = i - 1
Line 192:
a(j+1:i) = cshift(a(j+1:i),-1)
END DO
</codelang>
 
=={{header|Haskell}}==
<codelang haskell>
insert x [] = [x]
insert x (y:ys) | x <= y = x:y:ys
Line 206:
-- *Main> insertionSort [6,8,5,9,3,2,1,4,7]
-- [1,2,3,4,5,6,7,8,9]
</codelang>
 
=={{header|Java}}==
<codelang javajava5>
public static void insertSort(int[] A){
for(int i = 1; i < A.length; i++){
Line 221:
}
}
</codelang>
 
=={{header|Modula-3}}==
{{trans|Ada}}
<codelang modula3>
MODULE InsertSort;
 
Line 242:
END IntSort;
END InsertSort.
</codelang>
 
=={{header|OCaml}}==
<codelang ocaml>let rec insert x = function
[] -> [x]
| y :: ys ->
Line 253:
let insertion_sort lst = List.fold_right insert lst [];;
 
insertion_sort [6;8;5;9;3;2;1;4;7];;</codelang>
 
=={{header|Perl}}==
<codelang perl>
sub insertion_sort {
$arr = shift;
Line 272:
insertion_sort($a);
print join(' ', @{$a}), "\n";
</codelang>
Output:
-31 0 1 2 4 65 83 99 782
Line 300:
 
=={{header|Python}}==
<codelang python>
def insertion_sort(l):
for i in xrange(1, len(l)):
Line 309:
j -= 1
l[j+1] = key
</codelang>
===Insertion sort with binary search===
<codelang python>
def insertion_sort_bin(seq):
for i in range(1, len(seq)):
Line 327:
# insert key at position ``low``
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]
</codelang>
 
=={{header|Scheme}}==
<codelang scheme>(define (insert x lst)
(if (null? lst)
(list x)
Line 345:
(insertion-sort (cdr lst)))))
 
(insertion-sort '(6 8 5 9 3 2 1 4 7))</codelang>
 
=={{header|UnixPipes}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/42721"