Sorting algorithms/Insertion sort: Difference between revisions

Content added Content deleted
m (→‎{{header|REXX}}: changed a comment.)
(→‎{{header|jq}}: modify to work with jq 1.4)
Line 1,071: Line 1,071:


=={{header|jq}}==
=={{header|jq}}==
{{works with|jq|1.4}}
The insertion sort can be expressed directly in jq as follows:
The insertion sort can be expressed directly in jq as follows:
<lang jq>def insertion_sort:
<lang jq>def insertion_sort:
reduce .[] as $x ([]; insert($x));</lang>where insert/1 inserts its argument into its input, which can, by construction, be assumed here to be sorted. This algorithm will work in jq for any JSON array.
reduce .[] as $x ([]; insert($x));</lang>where insert/1 inserts its argument into its input, which can, by construction, be assumed here to be sorted. This algorithm will work in jq for any JSON array.


The following solution uses an "industrial strength" implementation of bsearch (binary search) that requires a version of jq with "while".
The following solution uses an "industrial strength" implementation of bsearch (binary search) that requires the following control structure:
<lang jq># As soon as "condition" is true, then emit . and stop:
An alternative version that has no special requirements is available on the [[Binary search#jq|Binary search]] page.
def do_until(condition; next):
def u: if condition then . else (next|u) end;
u;</lang>


bsearch is the only non-trivial part of this solution, and so we include
bsearch is the only non-trivial part of this solution, and so we include
Line 1,092: Line 1,096:
# state variable: [start, end, answer]
# state variable: [start, end, answer]
# where start and end are the upper and lower offsets to use.
# where start and end are the upper and lower offsets to use.
| last( [0, length-1, null]
| [0, length-1, null]
| while( .[0] <= .[1] ;
| do_until( .[0] > .[1] ;
(if .[2] != null then (.[1] = -1) # i.e. break
(if .[2] != null then (.[1] = -1) # i.e. break
else
else
( ( (.[1] + .[0]) / 2 ) | floor ) as $mid
( ( (.[1] + .[0]) / 2 ) | floor ) as $mid
| $in[$mid] as $monkey
| $in[$mid] as $monkey
| if $monkey == target then (.[2] = $mid) # success
| if $monkey == target then (.[2] = $mid) # success
elif .[0] == .[1] then (.[1] = -1) # failure
elif .[0] == .[1] then (.[1] = -1) # failure
elif $monkey < target then (.[0] = ($mid + 1))
elif $monkey < target then (.[0] = ($mid + 1))
else (.[1] = ($mid - 1))
else (.[1] = ($mid - 1))
end
end
end )))
end ))
| if .[2] == null then # compute the insertion point
| if .[2] == null then # compute the insertion point
if $in[ .[0] ] < target then (-2 -.[0])
if $in[ .[0] ] < target then (-2 -.[0])
Line 1,122: Line 1,126:


def insertion_sort:
def insertion_sort:
reduce .[] as $x ([]; insert($x));</lang>Example:<lang jq>
reduce .[] as $x ([]; insert($x));</lang>
[1, 2, 1, 1.1, -1.1, null, [null], {"null":null}] | insertion_sort</lang>
Example:<lang jq>[1, 2, 1, 1.1, -1.1, null, [null], {"null":null}] | insertion_sort</lang>
{{Out}}
{{Out}}
[null,-1.1,1,1,1.1,2,[null],{"null":null}]
[null,-1.1,1,1,1.1,2,[null],{"null":null}]


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