Sorting algorithms/Insertion sort: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 34:
{{trans|Python}}
<
L(i) 1 .< l.len
V j = i - 1
Line 45:
V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
insertion_sort(&arr)
print(arr)</
{{out}}
Line 56:
These programs use two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.
===Basic===
<
INSSORT CSECT
USING INSSORT,R13 base register
Line 112:
XDEC DS CL12 for xdeco
YREGS symbolics for registers
END INSSORT</
{{out}}
<pre>
Line 120:
===Assembler Structured Macros===
No harmful gotos [:)Dijkstra], no labels. It's cleaner, but is it clearer?
<
INSSORTS CSECT
USING INSSORTS,R13 base register
Line 172:
XDEC DS CL12 for xdeco
YREGS symbolics for registers
END INSSORTS</
{{out}}
Same as previous
Line 178:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program insertionSort64.s */
Line 340:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ACL2}}==
<
(cond ((endp xs) (list x))
((< x (first xs))
Line 353:
nil
(insert (first xs)
(isort (rest xs)))))</
=={{header|Action!}}==
<
INT i
Line 407:
Test(c,8)
Test(d,12)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Insertion_sort.png Screenshot from Atari 8-bit computer]
Line 433:
=={{header|ActionScript}}==
<
{
for(var i:int = 1; i < array.length;i++)
Line 447:
}
return array;
}</
=={{header|Ada}}==
<
procedure Insertion_Sort(Item : in out Data_Array) is
Line 467:
Item(J + 1) := Value;
end loop;
end Insertion_Sort;</
=={{header|ALGOL 68}}==
Line 477:
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}
<
PROC in place insertion sort = (REF[]DATA item)VOID:
Line 501:
in place insertion sort(ref data);
FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);
print((data))</
{{out}}
<pre>
Line 510:
=={{header|ALGOL W}}==
External in-place insertion sort routine for integers. From the pseudo code but with variable bounds.
<
% of an array parameter, the lower and upper bounds must be specified in lb and ub %
procedure insertionSortI ( integer array A ( * ); integer value lb, ub ) ;
Line 522:
end while_j_ge_0_and_Aj_gt_v ;
A( j + 1 ) := v
end insertionSortI ;</
Test the insertionSortI procedure.
<
% external in-place insertion sort procedure %
procedure insertionSortI ( integer array A( * ); integer value lb, ub ) ;
Line 539:
write( i_w := 1, d( 1 ) );
for i := 2 until 8 do writeon( i_w := 1, d( i ) )
end.</
{{out}}
<pre>
Line 547:
=={{header|AppleScript}}==
<
on insertionSort(theList, l, r) -- Sort items l thru r of theList.
set listLength to (count theList)
Line 599:
set aList to {60, 73, 11, 66, 6, 77, 41, 97, 59, 45, 64, 15, 91, 100, 22, 89, 77, 59, 54, 61}
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
return aList</
{{output}}
<
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program insertionSort.s */
Line 830:
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|Arturo}}==
<
arr: new items
loop 1..(size items)-1 'i [
Line 851:
]
print insertionSort [3 1 2 8 5 7 9 4 6]</
{{out}}
Line 863:
This implementation finds the position at which the element is to be inserted, and then uses '''array_subcirculate''' to move it into place. The prelude's implementation of '''array_subcirculate''' is a '''memmove(3)'''.
<
(*------------------------------------------------------------------*)
Line 948:
print! (" ", arr[i]);
println! ()
end</
{{out}}
Line 962:
(The complications are necessary to prevent us accidentally having two copies of a linear value. Having two copies would introduce such nasty possibilities as a double-free error, use of a destroyed list, etc.)
<
(*------------------------------------------------------------------*)
Line 1,123:
array_uninitize<Strptr1> (arr, i2sz SIZE);
array_ptr_free (pf_arr, pfgc_arr | p_arr)
end</
{{out}}
Line 1,137:
None of the activities in the following implementation requires allocating a new node. The original list is consumed. However, you can use this code to non-destructively sort a non-linear list by first creating a copy, casting the copy to a linear list, and sorting the copy, then casting the result to a non-linear list.
<
(*------------------------------------------------------------------*)
Line 1,322:
val () = list_vt_freelin lst
in
end</
{{out}}
Line 1,332:
=={{header|AutoHotkey}}==
contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276481.html#276481 forum]
<
MsgBox % InsertionSort("xxx")
MsgBox % InsertionSort("3,2,1")
Line 1,348:
sorted .= "," . a%A_Index%
Return SubStr(sorted,2) ; drop leading comma
}</
=={{header|AWK}}==
Sort standard input (storing lines into an array) and output to standard output
<
line[NR] = $0
}
Line 1,369:
print line[i]
}
}</
=={{header|Bash}}==
<
# Sorting integers with insertion sort
Line 1,452:
fi
#END</
{{out}}
Line 1,465:
=={{header|B4X}}==
The array type can be changed to Object and it will then work with any numeric type.
<
For i = 1 To A.Length - 1
Dim value As Int = A(i)
Line 1,484:
Next
End Sub
</syntaxhighlight>
{{out}}
<pre>
Line 1,500:
This version should work on any BASIC that can accept arrays as function arguments.
<
DIM n(10) AS INTEGER, L AS INTEGER, o AS STRING
Line 1,529:
theList(j + 1) = insertionElement
NEXT
END SUB</
{{out}}
Line 1,540:
Sorts N elements in array i() into ascending order. Invoke with GO SUB 500.
<
510 IF i(j)<=i(j+1) THEN NEXT j: RETURN
520 LET c=i(j+1)
530 FOR k=j TO 1 STEP -1: IF i(k)>c THEN LET i(k+1)=i(k): NEXT k
540 LET i(k+1)=c
600 NEXT j: RETURN</
For those who prefer GO TOs over conditional NEXTs (fine in ZX BASIC but problematic for compilers and stack-dependent interpreters like NextBASIC’s integer extensions) replace NEXT J: RETURN in line 510 with GO TO 600 and use this line 530:
Line 1,554:
==={{header|BBC BASIC}}===
Note that the array index is assumed to start at zero.
<
test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
PROCinsertionsort(test(), 10)
Line 1,574:
a(j%) = t
NEXT
ENDPROC</
{{out}}
<pre>
Line 1,581:
==={{header|Commodore BASIC}}===
<
10 DIM A(10): N=9
11 REM GENERATE SOME RANDOM NUMBERS AND PRINT THEM
Line 1,590:
32 RETURN
50 PRINT: FOR I=0 TO N: PRINTA(I): NEXT: RETURN
</syntaxhighlight>
==={{header|IS-BASIC}}===
<
110 RANDOMIZE
120 NUMERIC ARRAY(5 TO 21)
Line 1,619:
340 LET A(I+1)=SW
350 NEXT
360 END DEF</
=={{header|BCPL}}==
<
let insertionSort(A, len) be
Line 1,647:
insertionSort(array, length)
write("After: ", array, length)
$)</
{{out}}
<pre>Before: 4 65 2 -31 0 99 2 83 782 1
Line 1,653:
=={{header|C}}==
<
void insertion_sort(int*, const size_t);
Line 1,685:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,693:
=={{header|C sharp|C#}}==
<
using System;
Line 1,713:
}
}
}</
'''Example''':
<
using System;
Line 1,724:
Console.WriteLine(String.Join(" ", entries));
}
}</
=={{header|C++}}==
Line 1,730:
g++ -std=c++11 insertion.cpp
Uses binary search via std::upper_bound() to find the insertion position in logarithmic time and then performs the insertion via std::rotate() in linear time.
<
#include <iostream>
#include <iterator>
Line 1,762:
std::cout << "\n";
}</
{{out}}
<pre>
Line 1,769:
=={{header|Clojure}}==
<
(defn insertion-sort [coll]
(reduce (fn [result input]
Line 1,776:
[]
coll))
</syntaxhighlight>
Translated from the Haskell example:
<
(defn in-sort! [data]
(letfn [(insert ([raw x](insert [] raw x))
Line 1,788:
(reduce insert [] data)))
;Usage:(in-sort! [6,8,5,9,3,2,1,4,7])
;Returns: [1 2 3 4 5 6 7 8 9]</
=={{header|CLU}}==
<
insertion_sort = proc [T: type] (a: array[T])
where T has lt: proctype (T,T) returns (bool)
Line 1,826:
insertion_sort[int](test)
stream$puts(po, "After: ") print_arr[int](test, 3, po)
end start_up</
{{out}}
<pre>Before: 7 -5 0 2 99 16 4 20 47 19
Line 1,832:
=={{header|CMake}}==
<
function(insertion_sort var)
math(EXPR last "${ARGC} - 1") # Sort ARGV[1..last].
Line 1,862:
endforeach(i)
set("${var}" "${answer}" PARENT_SCOPE)
endfunction(insertion_sort)</
<
message(STATUS "${result}") # -- 11;22;33;44;55;66</
=={{header|COBOL}}==
This exerpt contains just enough of the procedure division to show the sort itself. The appropriate data division entries can be inferred. See also the entry for the Bubble sort for a full program.
<
PERFORM E-INSERTION VARYING WB-IX-1 FROM 1 BY 1
UNTIL WB-IX-1 > WC-SIZE.
Line 1,895:
F-999.
EXIT.</
And a fully runnable version, by Steve Williams
{{works with|GnuCOBOL}}
<syntaxhighlight lang="cobol">
>>SOURCE FORMAT FREE
*> This code is dedicated to the public domain
Line 1,969:
stop run
.
end program insertionsort.</
{{out}}
Line 1,978:
=={{header|Common Lisp}}==
<
(let ((tail (member-if-not predicate list)))
(values (ldiff list tail) tail)))
Line 1,990:
(defun insertion-sort (list)
(reduce #'insert list :initial-value nil))</
<
(if (cdr sequence)
(insert (car sequence) ;; insert the current item into
Line 2,009:
(insert item ;; the list of the item sorted with the rest of the list
(cdr sequence)
predicate)))))</
=={{header|D}}==
<
foreach (immutable i, value; data[1 .. $]) {
auto j = i + 1;
Line 2,026:
items.insertionSort;
items.writeln;
}</
{{out}}
<pre>[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]</pre>
Line 2,032:
===Higher Level Version===
{{trans|C++}}
<
void insertionSort(R)(R arr)
Line 2,062:
assert(arr3.isSorted);
}
}</
{{out}}
<pre>arr1 sorted: [2, 4, 11, 17, 19, 24, 25, 28, 44, 46]
Line 2,071:
{{trans|Java}}
<
insertSort(List<int> array){
Line 2,090:
print('${a}');
}
</syntaxhighlight>
{{out}}
<pre>array unsorted: [10, 3, 11, 15, 19, 1];
Line 2,101:
Static array is an arbitrary-based array of fixed length
<
{$APPTYPE CONSOLE}
Line 2,150:
Writeln;
Readln;
end.</
{{out}}
<pre>
Line 2,159:
===String sort===
// string is 1-based variable-length array of Char
<
var
I, J, L: Integer;
Line 2,175:
S[J + 1]:= Ch;
end;
end;</
<pre>
// in : S = 'the quick brown fox jumps over the lazy dog'
Line 2,185:
A direct conversion of the pseudocode.
<
for i in 1..!(array.size()) {
def value := array[i]
Line 2,195:
array[j+1] := value
}
}</
Test case:
<
> insertionSort(a)
> a
# value: [10, 10, 10, 13, 14, 17, 22, 23, 24, 26, 27, 27, 39, 40, 47, 50, 52, 53, 54, 55, 59, 60, 61, 62, 63, 65, 67, 71, 75, 75, 78, 83, 85, 85, 88, 91, 93, 94, 96, 99].diverge()</
=={{header|EasyLang}}==
<syntaxhighlight lang="text">subr sort
for i = 1 to len data[] - 1
h = data[i]
Line 2,219:
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
call sort
print data[]</
=={{header|Eiffel}}==
Line 2,228:
For a more complete explanation of the Eiffel sort examples, see the [[Sorting algorithms/Bubble sort#Eiffel|Bubble sort]].
<
MY_SORTED_SET [G -> COMPARABLE]
inherit
Line 2,259:
end
end</
=={{header|Elena}}==
ELENA 5.0 :
<
extension op
Line 2,295:
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.insertionSort().asEnumerable());
}</
{{out}}
<pre>
Line 2,303:
=={{header|Elixir}}==
<
def insert_sort(list) when is_list(list), do: insert_sort(list, [])
Line 2,312:
defp insert(x, sorted) when x < hd(sorted), do: [x | sorted]
defp insert(x, [h | t]), do: [h | insert(x, t)]
end</
Example:
Line 2,321:
=={{header|Emacs Lisp}}==
<
"Return minimum or maximum of NUMBERS using COMPARATOR."
(let ((extremum (car numbers)))
Line 2,350:
nil))
(insertion-sort '(1 2 3 9 8 7 25 12 3 2 1) #'>)</
{{out}}
Line 2,357:
=={{header|Erlang}}==
<
-export([insertion/1]).
Line 2,364:
insert(X,[]) -> [X];
insert(X,L=[H|_]) when X =< H -> [X|L];
insert(X,[H|T]) -> [H|insert(X, T)].</
And the calls:
<
{ok,sort}
2> sort:insertion([5,3,9,4,1,6,8,2,7]).
[1,2,3,4,5,6,7,8,9]</
=={{header|ERRE}}==
Note: array index is assumed to start at zero.
<syntaxhighlight lang="erre">
PROGRAM INSERTION_SORT
Line 2,408:
PRINT
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 2,416:
=={{header|Euphoria}}==
<
object temp
integer j
Line 2,437:
pretty_print(1,s,{2})
puts(1,"\nAfter: ")
pretty_print(1,insertion_sort(s),{2})</
{{out}}
Line 2,475:
=={{header|F Sharp|F#}}==
Procedural Version
<
// This function performs an insertion sort with an array.
// The input parameter is a generic array (any type that can perform comparison).
Line 2,490:
B.[j+1] <- value
B // the array B is returned
</syntaxhighlight>
Functional Version
<
let insertionSort collection =
Line 2,509:
| x::xs, ys -> xs |> isort (sinsert x ys)
collection |> isort []
</syntaxhighlight>
=={{header|Factor}}==
{{trans|Haskell}}
<
: insertion-sort ( seq -- sorted-seq )
<reversed> V{ } clone [ swap insort-left! ] reduce ;
{ 6 8 5 9 3 2 1 4 7 } insertion-sort .</
{{out}}
<pre>
Line 2,527:
=={{header|Forth}}==
<
dup @ >r ( r: v ) \ v = a[i]
begin
Line 2,544:
create test 7 , 3 , 0 , 2 , 9 , 1 , 6 , 8 , 4 , 5 ,
test 10 sort
test 10 cells dump</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
integer :: n, i, j
Line 2,564:
a(j + 1) = x
end do
end subroutine</
=== Alternate Fortran 77 version ===
<
IMPLICIT NONE
INTEGER N,I,J
Line 2,581:
20 A(J + 1) = X
30 CONTINUE
END</
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Line 2,633:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>unsort -7 -1 4 -6 5 2 1 -2 0 -5 -4 6 -3 7 3
Line 2,639:
=={{header|GAP}}==
<
local n, i, j, x;
n := Length(L);
Line 2,656:
InsertionSort(s);
s;
# "ABCDEFGHIJKLMNOPQRSTUVWXYZ"</
=={{header|Go}}==
<
import "fmt"
Line 2,681:
insertionSort(list)
fmt.Println("sorted! ", list)
}</
{{out}}
<pre>
Line 2,689:
A generic version that takes any container that conforms to <code>sort.Interface</code>:
<
import (
Line 2,710:
insertionSort(sort.IntSlice(list))
fmt.Println("sorted! ", list)
}</
{{out}}
<pre>
Line 2,718:
Using binary search to locate the place to insert:
<
import (
Line 2,740:
insertionSort(list)
fmt.Println("sorted! ", list)
}</
{{out}}
<pre>
Line 2,749:
=={{header|Groovy}}==
Solution:
<
def size = list.size()
Line 2,761:
}
list
}</
Test:
<
println (insertionSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))</
{{out}}
Line 2,772:
=={{header|Haskell}}==
<
insertionSort :: Ord a => [a] -> [a]
Line 2,779:
-- Example use:
-- *Main> insertionSort [6,8,5,9,3,2,1,4,7]
-- [1,2,3,4,5,6,7,8,9]</
=={{header|Haxe}}==
<
@:generic
public static function sort<T>(arr:Array<T>) {
Line 2,814:
Sys.println('Sorted Strings: ' + stringArray);
}
}</
{{out}}
Line 2,827:
=={{header|HicEst}}==
<
value = A(i)
j = i - 1
Line 2,838:
ENDIF
A(j+1) = value
ENDDO</
=={{header|Icon}} and {{header|Unicon}}==
<
demosort(insertionsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
Line 2,857:
}
return X
end</
Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'sortop', and 'demosort' in Bubble Sort]]. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.
Line 2,871:
=={{header|Io}}==
<syntaxhighlight lang="io">
List do(
insertionSortInPlace := method(
Line 2,888:
lst := list(7, 6, 5, 9, 8, 4, 3, 1, 2, 0)
lst insertionSortInPlace println # ==> list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)</
A shorter, but slightly less efficient, version:
<
insertionSortInPlace := method(
# In fact, we could've done slice(1, size - 1) foreach(...)
Line 2,904:
lst := list(7, 6, 5, 9, 8, 4, 3, 1, 2, 0)
lst insertionSortInPlace println # ==> list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
</syntaxhighlight>
=={{header|Isabelle}}==
<
imports Main
begin
Line 2,964:
unfolding rosettacode_haskell_insertionsort_def by(induction xs) simp+
end</
Line 2,970:
{{eff note|J|/:~}}
Solution inspired by the Common LISP solution:
<
Example of use:
<
_38 1 2 3 4 32 34 95 120</
=={{header|Java}}==
<
for(int i = 1; i < A.length; i++){
int value = A[i];
Line 2,986:
A[j + 1] = value;
}
}</
Using some built-in algorithms (warning: not stable, due to the lack of an "upper bound" binary search function)
{{trans|C++}}
<
for (int i = 1; i < a.size(); i++) {
int j = Math.abs(Collections.binarySearch(a.subList(0, i), a.get(i)) + 1);
Line 3,003:
a[j] = x;
}
}</
=={{header|JavaScript}}==
<
function insertionSort (a) {
for (var i = 0; i < a.length; i++) {
Line 3,019:
var a = [4, 65, 2, -31, 0, 99, 83, 782, 1];
insertionSort(a);
document.write(a.join(" "));</
=={{header|jq}}==
{{works with|jq|1.4}}
The insertion sort can be expressed directly in jq as follows:
<
reduce .[] as $x ([]; insert($x));</
The following solution uses an "industrial strength" implementation of bsearch (binary search) that requires the following control structure:
<
def do_until(condition; next):
def u: if condition then . else (next|u) end;
u;</
bsearch is the only non-trivial part of this solution, and so we include
Line 3,040:
(-1 - ix), where ix is the insertion point that would leave the array sorted.
If the input is not sorted, bsearch will terminate but with irrelevant results.<
if length == 0 then -1
elif length == 1 then
Line 3,077:
def insertion_sort:
reduce .[] as $x ([]; insert($x));</
Example:<
{{Out}}
[null,-1.1,1,1,1.1,2,[null],{"null":null}]
=={{header|Julia}}==
<
function insertionsort!(A::Array{T}) where T <: Number
Line 3,099:
x = randn(5)
@show x insertionsort!(x)</
{{out}}
Line 3,106:
=={{header|Kotlin}}==
<
for (index in 1 until array.size) {
val value = array[index]
Line 3,132:
insertionSort(numbers)
printArray("Sorted:", numbers)
}</
{{out}}
Line 3,139:
=={{header|Ksh}}==
<
# An insertion sort in ksh
Line 3,177:
printf "%d " ${arr[i]}
done
printf "%s\n" " )"</
{{out}}
Line 3,183:
=={{header|Lambdatalk}}==
<
{def sort
Line 3,209:
{sort {A}}
-> [-31,0,1,2,4,65,83,99,782]
</syntaxhighlight>
=={{header|Liberty BASIC}}==
<
dim A(itemCount)
for i = 1 to itemCount
Line 3,242:
next i
print
return</
=={{header|Lua}}==
Binary variation of Insertion sort (Has better complexity)
<
local function lower_bound(container, container_begin, container_end, value, comparator)
local count = container_end - container_begin + 1
Line 3,291:
binary_insertion_sort_impl(container, comparator)
end
end</
<
local st, en = st or 1, en or #tb
local mid = math.floor((st + en)/2)
Line 3,308:
end
print(unpack(isort{4,5,2,7,8,3}))</
=={{header|Maple}}==
<
len := numelems(arr):
for i from 2 to len do
Line 3,322:
arr[j+1] := val:
end do:
arr;</
{{Out|Output}}
<pre>[0,0,2,3,3,8,17,36,40,72]</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
For[i = 2, i <= Length[A], i++,
value = A[[i]]; j = i - 1;
Line 3,333:
A[[j + 1]] = value;];
A
]</
{{out}}
<pre>insertionSort@{ 2, 1, 3, 5}
Line 3,340:
=={{header|MATLAB}} / {{header|Octave}}==
This is a direct translation of the pseudo-code above, except that it has been modified to compensate for MATLAB's 1 based arrays.
<
for i = (2:numel(list))
Line 3,355:
end %for
end %insertionSort</
Sample Usage:
<
ans =
1 2 3 4 5 6</
=={{header|Maxima}}==
<
[n: length(u), x, j],
for i from 2 thru n do (
Line 3,376:
u[j + 1]: x
)
)$</
=={{header|MAXScript}}==
<syntaxhighlight lang="maxscript">
fn inSort arr =
(
Line 3,394:
return arr
)
</syntaxhighlight>
Output:
<syntaxhighlight lang="maxscript">
b = for i in 1 to 20 collect random 1 40
#(2, 28, 35, 31, 27, 24, 2, 22, 15, 34, 9, 10, 22, 40, 26, 5, 23, 6, 18, 33)
a = insort b
#(2, 2, 5, 6, 9, 10, 15, 18, 22, 22, 23, 24, 26, 27, 28, 31, 33, 34, 35, 40)
</syntaxhighlight>
=={{header|ML}}==
==={{header|mLite}}===
{{trans|OCaml}}
<
let
fun insert
Line 3,420:
println ` insertion_sort [6,8,5,9,3,2,1,4,7];
</syntaxhighlight>
Output
<pre>
Line 3,427:
==={{header|Standard ML}}===
<
fun insert (x, []) = [x]
| insert (x, y::ys) =
Line 3,436:
end;
insertion_sort Int.compare [6,8,5,9,3,2,1,4,7];</
=={{header|Modula-3}}==
{{trans|Ada}}
<
PROCEDURE IntSort(VAR item: ARRAY OF INTEGER) =
Line 3,455:
END;
END IntSort;
END InsertSort.</
=={{header|N/t/roff}}==
Line 3,462:
===Sliding method===
<
..
.de array
Line 3,516:
.a.pushln 13 64 22 87 54 87 23 92 11 64 5 9 3 3 0
.insertionsort a
.a.dump</
===Swapping method===
<
..
.de array
Line 3,563:
.a.pushln 13 64 22 87 54 87 23 92 11 64 5 9 3 3 0
.insertionsort a
.a.dump</
=={{header|Nanoquery}}==
{{trans|Python}}
<
for i in range(1, len(L) - 1)
j = i - 1
Line 3,579:
return L
end</
=={{header|Nemerle}}==
From the psuedocode.
<
using Nemerle.English;
Line 3,609:
foreach (i in arr) Write($"$i ");
}
}</
=={{header|NetRexx}}==
<
options replace format comments java crossref savelog symbols binary
Line 3,659:
return ArrayList(A)
</syntaxhighlight>
{{out}}
<pre>
Line 3,682:
=={{header|Nim}}==
<
for i in 1 .. a.high:
let value = a[i]
Line 3,693:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
insertSort a
echo a</
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Objeck}}==
<
bundle Default {
class Insert {
Line 3,722:
}
}
</syntaxhighlight>
=={{header|OCaml}}==
<
match lst with
[] -> [x]
Line 3,734:
let insertion_sort = List.fold_left insert [];;
insertion_sort [6;8;5;9;3;2;1;4;7];;</
=={{header|Oforth}}==
Line 3,740:
Returns a new sorted list.
<
| l i j v |
a asListBuffer ->l
Line 3,753:
l put(j 1 +, v)
]
l ;</
{{out}}
Line 3,764:
=={{header|ooRexx}}==
{{trans|REXX}}
<
/* using the insertion sort algorithm */
Call gen /* fill the array with test data */
Line 3,806:
Say 'Element' right(j,length(x.0)) arg(1)":" x.j
End
Return</
{{out}}
<pre>Element 1 before sort: ---Monday's Child Is Fair of Face (by Mother Goose)---
Line 3,832:
=={{header|Oz}}==
Direct translation of pseudocode. In-place sorting of mutable arrays.
<
proc {InsertionSort A}
Low = {Array.low A}
Line 3,852:
in
{InsertionSort Arr}
{Show {Array.toRecord unit Arr}}</
=={{header|PARI/GP}}==
<
for(i=1,#v-1,
my(j=i-1,x=v[i]);
Line 3,865:
);
v
};</
=={{header|Pascal}}==
Line 3,871:
=={{header|Perl}}==
<
sub insertion_sort {
my (@list) = @_;
Line 3,888:
my @a = insertion_sort(4, 65, 2, -31, 0, 99, 83, 782, 1);
print "@a\n";
</syntaxhighlight>
{{out}}
-31 0 1 2 4 65 83 99 782
Line 3,894:
=={{header|Phix}}==
Copy of [[Sorting_algorithms/Insertion_sort#Euphoria|Euphoria]]
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">insertion_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">temp</span>
Line 3,914:
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Before: "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">s</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"After: "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">insertion_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 3,922:
=={{header|PHP}}==
<
for($i=0;$i<count($arr);$i++){
$val = $arr[$i];
Line 3,936:
$arr = array(4,2,1,6,9,3,8,7);
insertionSort($arr);
echo implode(',',$arr);</
<pre>1,2,3,4,6,7,8,9</pre>
=={{header|PicoLisp}}==
<
(for (I (cdr Lst) I (cdr I))
(for (J Lst (n== J I) (cdr J))
(T (> (car J) (car I))
(rot J (offset I J)) ) ) )
Lst )</
{{out}}
<pre>: (insertionSort (5 3 1 7 4 1 1 20))
Line 3,951:
=={{header|PL/I}}==
<
insert_sort: proc(array);
dcl array(*) fixed bin(31);
Line 3,969:
end;
end insert_sort;
</syntaxhighlight>
=={{header|PL/M}}==
<
/* INSERTION SORT ON 16-BIT INTEGERS */
Line 4,017:
CALL BDOS(0,0);
EOF</
{{out}}
<pre>0 1 2 2 3 4 8 31 65 99 782</pre>
Line 4,023:
=={{header|PowerShell}}==
Very similar to the PHP code.
<
for($i=0;$i -lt $arr.length;$i++){
$val = $arr[$i]
Line 4,037:
$arr = @(4,2,1,6,9,3,8,7)
insertionSort($arr)
$arr -join ","</
{{Out}}
<pre>1,2,3,4,6,7,8,9</pre>
=={{header|Prolog}}==
<
insert_sort_intern(L1,[],L2).
Line 4,055:
!.
insert([H|T],X,[H|T2]) :-
insert(T,X,T2).</
% Example use:
Line 4,065:
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.
<
isort(L, LS) :-
foldl(insert, [], L, LS).
Line 4,084:
insert([H | T], N, [H|L1]) :-
insert(T, N, L1).
</syntaxhighlight>
Example use:
<pre> ?- isort([2,23,42,3,10,1,34,5],L).
Line 4,091:
=={{header|PureBasic}}==
<
Protected low, high
Protected firstIndex, lastIndex = ArraySize(a())
Line 4,110:
Wend
EndIf
EndProcedure</
=={{header|Python}}==
<
for i in xrange(1, len(L)):
j = i-1
Line 4,120:
L[j+1] = L[j]
j -= 1
L[j+1] = key</
Using pythonic iterators:
<
for i, value in enumerate(L):
for j in range(i - 1, -1, -1):
if L[j] > value:
L[j + 1] = L[j]
L[j] = value</
===Insertion sort with binary search===
<
for i in range(1, len(seq)):
key = seq[i]
Line 4,145:
up = middle
# insert key at position ``low``
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]</
This is also built-in to the standard library:
<
def insertion_sort_bin(seq):
for i in range(1, len(seq)):
bisect.insort(seq, seq.pop(i), 0, i)</
=={{header|Qi}}==
Based on the scheme version.
<
X [] -> [X]
X [Y|Ys] -> [X Y|Ys] where (<= X Y)
Line 4,166:
(insertion-sort [6 8 5 9 3 2 1 4 7])
</syntaxhighlight>
=={{Header|Quackery}}==
<
[ swap 2dup findwith
[ over > ] [ ]
nip stuff ] ] is insertionsort ( [ --> [ )</
=={{header|R}}==
Direct translation of pseudocode.
<
{
for(i in 2:(length(x)))
Line 4,191:
x
}
insertionsort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782</
R has native vectorized operations which allow the following, more efficient implementation.
<syntaxhighlight lang="r">
insertion_sort <- function(x) {
for (j in 2:length(x)) {
Line 4,213:
}
}
</syntaxhighlight>
=={{header|Racket}}==
This implementation makes use of the pattern matching facilities in the Racket distribution.
<
#lang racket
Line 4,227:
[(cons y rst) (cond [(< x y) (cons x ys)]
[else (cons y (insert x rst))])]))
(foldl insert '() l))</
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
for 1 .. @a.end -> $i {
my $value = @a[$i];
Line 4,246:
say 'input = ' ~ @data;
say 'output = ' ~ @data.&insertion_sort;
</syntaxhighlight>
{{out}}
Line 4,254:
=={{header|Rascal}}==
<
public list[int] insertionSort(a){
Line 4,267:
}
return a;
}</
{{out}}
<
list[int]: [-31,0,1,2,4,65,83,99,782]</
=={{header|REALbasic}}==
<
for insertionElementIndex as Integer = 1 to UBound(theList)
dim insertionElement as Integer = theList(insertionElementIndex)
Line 4,283:
theList(j + 1) = insertionElement
next
End Sub</
=={{header|REBOL}}==
<
; This program works with REBOL version R2 and R3, to make it work with Red
; change the word func to function
Line 4,326:
; just by adding the date! type to the local variable value the same function can sort dates.
probe insertion-sort [12-Jan-2015 11-Jan-2015 11-Jan-2016 12-Jan-2014]
</syntaxhighlight>
{{out}}
Line 4,345:
=={{header|REXX}}==
<
call gen /*generate the array's (data) elements.*/
call show 'before sort' /*display the before array elements. */
Line 4,374:
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do j=1 for #; say ' element' right(j,length(#)) arg(1)": " @.j; end; return</
{{out|output|text= when using the default internal data:}}
<pre>
Line 4,401:
=={{header|Ring}}==
<
alist = [7,6,5,9,8,4,3,1,2,0]
see insertionsort(alist)
Line 4,416:
next
return blist
</syntaxhighlight>
=={{header|Ruby}}==
<
def insertionsort!
1.upto(length - 1) do |i|
Line 4,435:
ary = [7,6,5,9,8,4,3,1,2,0]
p ary.insertionsort!
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</
Alternative version which doesn't swap elements but rather removes and inserts the value at the correct place:
<
def insertionsort!
1.upto(length - 1) do |i|
Line 4,452:
ary = [7,6,5,9,8,4,3,1,2,0]
p ary.insertionsort!
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</
=={{header|Run BASIC}}==
<
sortEnd = 0
global inSort
Line 4,485:
insSort(i) = x
sortEnd = sortEnd + 1
end function</
<pre>End Sort:20
1 124
Line 4,503:
=={{header|Rust}}==
<
for i in 1..arr.len() {
let mut j = i;
Line 4,511:
}
}
}</
=={{header|SASL}}==
Copied from SASL manual, Appendix II, answer (2)(a)
<syntaxhighlight lang="sasl">DEF
sort () = ()
sort (a : x) = insert a (sort x)
Line 4,521:
insert a (b : x) = a < b -> a : b : x
b : insert a x
?</
=={{header|Scala}}==
<
def insert(list: List[X], value: X) = list.span(x => ord.lt(x, value)) match {
case (lower, upper) => lower ::: value :: upper
}
list.foldLeft(List.empty[X])(insert)
}</
=={{header|Scheme}}==
<
(if (null? lst)
(list x)
Line 4,547:
(insertion-sort (cdr lst)))))
(insertion-sort '(6 8 5 9 3 2 1 4 7))</
=={{header|Seed7}}==
<
local
var integer: i is 0;
Line 4,565:
arr[j] := help;
end for;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#insertionSort]
=={{header|Sidef}}==
<
method insertion_sort {
{ |i|
Line 4,586:
var a = 10.of { 100.irand }
say a.insertion_sort</
=={{header|SNOBOL4}}==
<
A = table()
i = 0
Line 4,608:
* output sorted data
while output = A<i>; i = ?lt(i,aSize) i + 1 :s(while)
end</
=={{header|Stata}}==
<
void insertion_sort(real vector a) {
real scalar i, j, n, x
Line 4,625:
}
}
end</
=={{header|Swift}}==
Using generics.
<
for i in 1..<list.count {
var j = i
Line 4,638:
}
}
}</
=={{header|Tcl}}==
<
proc insertionsort {m} {
Line 4,656:
}
puts [insertionsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</
=={{header|TI-83 BASIC}}==
Line 4,683:
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">PRINT "Insertion sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
Line 4,731:
PRINT
RETURN</
=={{header|UnixPipes}}==
<
read a
test -n "$a" && ( selectionsort | sort -nm <(echo $a) -)
}</
<syntaxhighlight lang
=={{header|Ursala}}==
<
insort = ~&i&& @hNCtX ~&r->lx ^\~&rt nleq-~rlrSPrhlPrSCPTlrShlPNCTPQ@rhPlD</
test program:
<
example = insort <45,82,69,82,104,58,88,112,89,74></
{{out}}
<pre>
Line 4,755:
=={{header|Vala}}==
{{trans|Nim}}
<
var count = 0;
for (int i = 1; i < array.length; i++) {
Line 4,773:
foreach (int i in array)
print("%d ", i);
}</
{{out}}
<pre>
Line 4,780:
=={{header|VBA}}==
{{trans|Phix}}<
Private Function insertion_sort(s As Variant) As Variant
Dim temp As Variant
Line 4,801:
Debug.Print "Before: ", Join(s, ", ")
Debug.Print "After: ", Join(insertion_sort(s), "' ")
End Sub</
<pre>Before: 4, 15, delta, 2, -31, 0, alpha, 19, gamma, 2, 13, beta, 782, 1
After: -31' 0' 1' 2' 2' 4' 13' 15' 19' 782' alpha' beta' delta' gamma</pre>
Line 4,807:
=={{header|VBScript}}==
{{trans|REALbasic}}
<
Dim n(9) 'nine is the upperbound.
'since VBS arrays are 0-based, it will have 10 elements.
Line 4,843:
Next
End Sub
</syntaxhighlight>
{{Out}}
<pre>ORIGINAL : 26699;2643;10249;31612;21346;19702;29799;31115;20413;5197;
Line 4,849:
=={{header|Vlang}}==
<
for i in 1 .. arr.len {
value := arr[i]
Line 4,866:
insertion(mut arr)
println('Output: ' + arr.str())
}</
{{out}}
<pre>Input: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
Line 4,872:
=={{header|Wren}}==
<
for (i in 1..a.count-1) {
var v = a[i]
Line 4,890:
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 4,903:
Alternatively we can just call a library method.
{{libheader|Wren-sort}}
<
var as = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
Line 4,911:
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 4,919:
=={{header|XPL0}}==
<
proc InsertionSort(A, L); \Sort array A of length L
Line 4,939:
InsertionSort(A, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]</
{{out}}
Line 4,949:
=={{header|Yabasic}}==
{{trans|FreeBASIC}}
<
sub InsertionSort (matriz())
for i = 1 to arraysize(matriz(),1)
Line 4,979:
print
end
</syntaxhighlight>
=={{header|Yorick}}==
Based on pseudocode, except using 1-based arrays.
<
for(i = 2; i <= numberof(A); i++) {
value = A(i);
Line 4,994:
A(j+1) = value;
}
}</
=={{header|zkl}}==
<
sink:=List();
foreach x in (list){
Line 5,004:
}
sink.close();
}</
<
insertionSort("big fjords vex quick waltz nymph".split()).println();</
{{out}}
<pre>
|