Sorting algorithms/Insertion sort: Difference between revisions
no edit summary
(Add Factor) |
No edit summary |
||
Line 278:
-56 -1 0 0 2 3 9 34
</pre>
=={{header|AppleScript}}==
<lang applescript>on insertionSort(theList)
script o
property lst : theList
end script
set listLength to (count theList)
if (listLength > 1) then
-- Presort the first two values to set up a minor optimisation whereby the most recent instance of the highest value so far
-- is only put back into the list when a value greater than or equal to it turns up or the end of the list is reached.
set highestSoFar to beginning of o's lst
set currentValue to item 2 of o's lst
if (highestSoFar > currentValue) then
set item 1 of o's lst 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 3 to listLength
set currentValue to item i of o's lst
if (currentValue < highestSoFar) then
repeat with j from (i - 2) to 1 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 listLength to highestSoFar
end if
return -- nothing. Either o's lst or theList can be returned if preferred. They and the input list are all the same object.
end insertionSort
set aList to {60, 73, 11, 66, 6, 77, 41, 97, 59, 45, 64, 15, 91, 100, 22, 89, 77, 59, 54, 61}
insertionSort(aList)
return aList
--> {6, 11, 15, 22, 41, 45, 54, 59, 59, 60, 61, 64, 66, 73, 77, 77, 89, 91, 97, 100}</lang>
=={{header|ARM Assembly}}==
| |||