Sorting algorithms/Insertion sort: Difference between revisions

Content added Content deleted
(→‎{{header|C}}: fixed broken tags for code highlighting)
m (Links, formatting, more code -> lang changes)
Line 1: Line 1:
[[Category:Less Than 20 Examples]]{{task|Sorting Algorithms}}
[[Category:Less Than 20 Examples]]{{task|Sorting Algorithms}}
{{Sorting Algorithm}}
{{Sorting Algorithm}}
An O(n^2) sorting algorithm which moves elements one at a time into the correct position. The algorithm is as follows (from the [http://en.wikipedia.org/wiki/Insertion_sort#Algorithm wikipedia]):
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]]):
insertionSort(array A)
insertionSort(array A)
for i = 1 to length[A]-1 do
for i = 1 to length[A]-1 do
Line 14: Line 14:


=={{header|Ada}}==
=={{header|Ada}}==
<code ada>type Data_Array is array(Natural range <>) of Integer;
<lang ada>type Data_Array is array(Natural range <>) of Integer;
procedure Insertion_Sort(Item : in out Data_Array) is
procedure Insertion_Sort(Item : in out Data_Array) is
Line 32: Line 32:
end loop;
end loop;
end Insertion_Sort;
end Insertion_Sort;
</code>
</lang>
=={{header|ALGOL 68}}==
=={{header|ALGOL 68}}==
{{trans|Ada}}
{{trans|Ada}}
Line 104: Line 104:


=={{header|Common Lisp}}==
=={{header|Common Lisp}}==
<code lisp>(defun span (predicate list)
<lang lisp>(defun span (predicate list)
(let ((tail (member-if-not predicate list)))
(let ((tail (member-if-not predicate list)))
(values (ldiff list tail) tail)))
(values (ldiff list tail) tail)))
Line 117: Line 117:
(defun insertion-sort (list)
(defun insertion-sort (list)
(reduce #'insert list :initial-value nil))
(reduce #'insert list :initial-value nil))
</code>
</lang>


=={{header|D}}==
=={{header|D}}==
<code d>import std.stdio: writefln;
<lang d>import std.stdio: writefln;
void insertionSort(T)(T[] A) {
void insertionSort(T)(T[] A) {
Line 142: Line 142:
writefln(a2);
writefln(a2);
}
}
</code>
</lang>
=={{header|Forth}}==
=={{header|Forth}}==
<pre>
<pre>
Line 166: Line 166:


=={{header|Fortran}}==
=={{header|Fortran}}==
<code fortran>
<lang fortran>
SUBROUTINE Insertion_Sort(a)
SUBROUTINE Insertion_Sort(a)
REAL, INTENT(in out), DIMENSION(:) :: a
REAL, INTENT(in out), DIMENSION(:) :: a
Line 182: Line 182:
END DO
END DO
END SUBROUTINE Insertion_Sort
END SUBROUTINE Insertion_Sort
</code>
</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
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
<code fortran>
<lang fortran>
DO i = 2, SIZE(a)
DO i = 2, SIZE(a)
j = i - 1
j = i - 1
Line 192: Line 192:
a(j+1:i) = cshift(a(j+1:i),-1)
a(j+1:i) = cshift(a(j+1:i),-1)
END DO
END DO
</code>
</lang>


=={{header|Haskell}}==
=={{header|Haskell}}==
<code haskell>
<lang haskell>
insert x [] = [x]
insert x [] = [x]
insert x (y:ys) | x <= y = x:y:ys
insert x (y:ys) | x <= y = x:y:ys
Line 206: Line 206:
-- *Main> insertionSort [6,8,5,9,3,2,1,4,7]
-- *Main> insertionSort [6,8,5,9,3,2,1,4,7]
-- [1,2,3,4,5,6,7,8,9]
-- [1,2,3,4,5,6,7,8,9]
</code>
</lang>


=={{header|Java}}==
=={{header|Java}}==
<code java>
<lang java5>
public static void insertSort(int[] A){
public static void insertSort(int[] A){
for(int i = 1; i < A.length; i++){
for(int i = 1; i < A.length; i++){
Line 221: Line 221:
}
}
}
}
</code>
</lang>


=={{header|Modula-3}}==
=={{header|Modula-3}}==
{{trans|Ada}}
{{trans|Ada}}
<code modula3>
<lang modula3>
MODULE InsertSort;
MODULE InsertSort;


Line 242: Line 242:
END IntSort;
END IntSort;
END InsertSort.
END InsertSort.
</code>
</lang>


=={{header|OCaml}}==
=={{header|OCaml}}==
<code ocaml>let rec insert x = function
<lang ocaml>let rec insert x = function
[] -> [x]
[] -> [x]
| y :: ys ->
| y :: ys ->
Line 253: Line 253:
let insertion_sort lst = List.fold_right insert lst [];;
let insertion_sort lst = List.fold_right insert lst [];;


insertion_sort [6;8;5;9;3;2;1;4;7];;</code>
insertion_sort [6;8;5;9;3;2;1;4;7];;</lang>


=={{header|Perl}}==
=={{header|Perl}}==
<code perl>
<lang perl>
sub insertion_sort {
sub insertion_sort {
$arr = shift;
$arr = shift;
Line 272: Line 272:
insertion_sort($a);
insertion_sort($a);
print join(' ', @{$a}), "\n";
print join(' ', @{$a}), "\n";
</code>
</lang>
Output:
Output:
-31 0 1 2 4 65 83 99 782
-31 0 1 2 4 65 83 99 782
Line 300: Line 300:


=={{header|Python}}==
=={{header|Python}}==
<code python>
<lang python>
def insertion_sort(l):
def insertion_sort(l):
for i in xrange(1, len(l)):
for i in xrange(1, len(l)):
Line 309: Line 309:
j -= 1
j -= 1
l[j+1] = key
l[j+1] = key
</code>
</lang>
===Insertion sort with binary search===
===Insertion sort with binary search===
<code python>
<lang python>
def insertion_sort_bin(seq):
def insertion_sort_bin(seq):
for i in range(1, len(seq)):
for i in range(1, len(seq)):
Line 327: Line 327:
# insert key at position ``low``
# insert key at position ``low``
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]
</code>
</lang>


=={{header|Scheme}}==
=={{header|Scheme}}==
<code scheme>(define (insert x lst)
<lang scheme>(define (insert x lst)
(if (null? lst)
(if (null? lst)
(list x)
(list x)
Line 345: Line 345:
(insertion-sort (cdr lst)))))
(insertion-sort (cdr lst)))))


(insertion-sort '(6 8 5 9 3 2 1 4 7))</code>
(insertion-sort '(6 8 5 9 3 2 1 4 7))</lang>


=={{header|UnixPipes}}==
=={{header|UnixPipes}}==
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort"