Sorting algorithms/Insertion sort: Difference between revisions

Content added Content deleted
Line 470:
=={{header|AppleScript}}==
 
<lang applescript>-- SortIn-place rangeinsertion l thru r of a list, in place.sort
on insertionSort(theList, l, r) -- Sort items l thru r of theList.
set listLength to (count theList)▼
if (listLength >< 12) then return▼
-- Convert negative and/or transposed range indices.▼
if (l < 0) then set l to listLength + l + 1
if (r < 0) then set r to listLength + r + 1
if (l > r) then set {l, r} to {r, l}
-- The list as a script property to allow faster references to its items.
script o
property lst : theList
end script
-- Set up a minor optimisation whereby the latest instance of the highest value so far isn't put back▼
▲ set listLength to (count theList)
-- intoput orback re-fetched frominto the list until either it's superseded or the end of the sort is reached.▼
▲ if (listLength > 1) then
set highestSoFar to item l of o's lst's item l▼
▲ -- Convert negative and/or transposed range indices.
if (l < 0) then set lcurrentValue to listLengtho's +lst's item (l + 1)
if (rhighestSoFar <> 0currentValue) then set r to listLength + r + 1
ifset (lo's >lst's r)item then set {l, r} to {r, l}currentValue
else
set highestSoFar to currentValue▼
▲ -- Set up a minor optimisation whereby the latest instance of the highest value so far isn't put back
end if▼
▲ -- into or re-fetched from the list until either it's superseded or the end of the sort is reached.
-- Work through the rest of the range, rotating values back into the sorted group as necessary.▼
▲ set highestSoFar to item l of o's lst
repeat with i set currentValue to itemfrom (l + 12) of o'sto lstr
set currentValue to item i of o's lst's item i▼
if (highestSoFar > currentValue) then
setrepeat itemwith lj offrom o's(i lst- 2) to currentValuel by -1
set thisValue to item j of o's lst's item j▼
if (currentValuethisValue <> thisValuecurrentValue) then▼
set o's setlst's item (j + 1) of o's lst to thisValue▼
else▼
set j to j + 1▼
exit repeat▼
end if▼
end repeat▼
set o's lst's item rj to highestSoFarcurrentValue▼
else
set o's setlst's item (i - 1) of o's lst to highestSoFar▼
set highestSoFar to currentValue
end if
end repeat▼
▲ -- Work through the rest of the range, rotating values back into the sorted group as necessary.
set o's lst's item r to highestSoFar
repeat with i from (l + 2) to r
▲ set currentValue to item i of o's lst
if (currentValue < highestSoFar) then
repeat with j from (i - 2) to l by -1
▲ set thisValue to item j of o's lst
▲ if (currentValue < thisValue) then
▲ set item (j + 1) of o's lst to thisValue
▲ else
▲ set j to j + 1
▲ exit repeat
▲ end if
▲ end repeat
set item j of o's lst to currentValue
else
▲ set item (i - 1) of o's lst to highestSoFar
▲ set highestSoFar to currentValue
end if
▲ end repeat
-- At the end, ensure that the highest value goes back into the list.
▲ set o's lst's item r to highestSoFar
▲ end if
return -- nothing. The input list has been sorted in place.
end insertionSort
property sort : insertionSort
 
-- Test codeDemo:
local aList
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 theitems entire1 listthru -1 of aList.
return aList</lang>
 
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort"