Sorting algorithms/Strand sort: Difference between revisions
m
→{{header|AppleScript}}: Made into an in-place sort and more efficient.
(Added AppleScript.) |
m (→{{header|AppleScript}}: Made into an in-place sort and more efficient.) |
||
Line 50:
=={{header|AppleScript}}==
Strand sort seems to be essentially a merge sort with a particular way of setting up the initial blocks.
<syntaxhighlight lang="applescript">--
on strandSort(theList, l, r)
--
set listLength to (count theList)
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}
if ((l < 1) or (r > listLength)) then
script o
property
property
property ranges : {}
end script
-- Individually list-wrap the items in o's src to avoid having to
--
end repeat
-- Extract "strands" of existing order from the sort range items
-- and write the resulting runs over the range in the original list.
set i to l
repeat until (i > r)
set j to i
set
-- Do the same with any later values that are sequentially greater or equal.
if (kVal < jVal) then▼
repeat with k from 2 to (count o's src)
else
set j to j + 1
set o's
set
set
end if
end repeat
set o's ranges's end to {i, j} -- Note this strand's range in the list.
set o's src to o's src's lists -- Lose src's zapped sublists. **
set i to j + 1
end repeat
set
if (
--
-- the auxiliary list has to be the source or the destination during the first pass.
▲ set o's dest to o's src's items
-- The destination in the final pass has to be the original list.
repeat while (2 ^
end repeat
if (passCount mod 2 = 0) then
set o's src to o's dest
set o's dest to o's dest's items
else
set o's src to o's dest's items
end if
-- Merge the strands.
repeat passCount times
set k to l -- Destination index.
repeat with rr from 2 to strandCount by 2 -- Per pair of ranges.
set {{i, ix}, {j, jx}} to o's ranges's items (rr - 1) thru rr
set o's ranges's item (rr - 1) to {i, jx}
set o's ranges's item rr to missing value
set
set
repeat until (k > jx)
if (
set o's dest's item k to
else▼
repeat with i from i to ix
set k to k + 1
set o's dest's item k to o's src's item i
end repeat
▲ else
▲ set jVal to o's src's item j
end if
else
set o's dest's item k to
set iv to o's src's item i
else▼
repeat with k from j to jx
set o's dest's item k to o's src's item k
end repeat
▲ else
▲ set iVal to o's src's item i
end if
end if
Line 127 ⟶ 146:
end repeat
end repeat
if (rr <
set {i, ix} to o's ranges's end
repeat with k from i to ix
Line 135 ⟶ 154:
set o's ranges to o's ranges's lists
set
set {o's src, o's dest} to {o's dest, o's src}
end repeat
return
end strandSort
local lst
strandSort(lst, 1, -1)
return lst</syntaxhighlight>
{{output}}
| |||