Sorting algorithms/Insertion sort: Difference between revisions

<lang applescript>-- In-place insertion sort

on insertionSort(theList, l, r) -- Sort items l thru r of theList.

set listLength to (count theList)

if (listLength < 2) 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.

-- Set up a minor optimisation whereby the latest instance of the highest value so far isn't

-- put back into the list until either it's superseded or the end of the sort is reached.

set highestSoFar to o's lst's item l

set currentValue to o's lst's item (l + 1)

if (highestSoFar > currentValue) then

set o's lst's item l to currentValue

else

set highestSoFar to currentValue

end if

-- Work through the rest of the range, rotating values back into the sorted group as necessary.

repeat with i from (l + 2) to r

set currentValue to o's lst's item i

repeat with j from (i - 2) to l by -1

set thisValue to o's lst's item j

if (thisValue > currentValue) then

set o's lst's item (j + 1) to thisValue

else

set j to j + 1

exit repeat

end if

end repeat

set o's lst's item j to currentValue

set o's lst's item (i - 1) to highestSoFar

end repeat

set o's lst's item r to highestSoFar

return -- nothing.

-- Demo:

local aList

sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.