Sorting algorithms/Insertion sort: Difference between revisions
→{{header|jq}}: modify to work with jq 1.4
m (→{{header|REXX}}: changed a comment.) |
(→{{header|jq}}: modify to work with jq 1.4) |
||
Line 1,071:
=={{header|jq}}==
{{works with|jq|1.4}}
The insertion sort can be expressed directly in jq as follows:
<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.
The following solution uses an "industrial strength" implementation of bsearch (binary search) that requires
<lang jq># As soon as "condition" is true, then emit . and stop:
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
Line 1,092 ⟶ 1,096:
# state variable: [start, end, answer]
# where start and end are the upper and lower offsets to use.
| if .[2] == null then # compute the insertion point
if $in[ .[0] ] < target then (-2 -.[0])
Line 1,122 ⟶ 1,126:
def insertion_sort:
reduce .[] as $x ([]; insert($x));</lang
Example:<lang jq>[1, 2, 1, 1.1, -1.1, null, [null], {"null":null}] | insertion_sort</lang>
{{Out}}
[null,-1.1,1,1,1.1,2,[null],{"null":null}]
=={{header|Liberty BASIC}}==
| |||