Dutch national flag problem: Difference between revisions
→{{header|AppleScript}}: Further minor tidy. Also added solution using Dijkstra's algorithm.
(Added Swift solution) |
(→{{header|AppleScript}}: Further minor tidy. Also added solution using Dijkstra's algorithm.) |
||
Line 500:
property colours : {"red", "white", "blue"}
property balls : {}
on isGreater(a, b)▼
return ((a ≠ b) and ((a is "blue") or (b is "red")))▼
end isGreater▼
end script
Line 505 ⟶ 510:
set end of o's balls to some item of o's colours
end repeat
▲ -- Sort the balls using a custom comparison handler.
script redWhiteBlue▼
▲ on isGreater(a, b)
▲ return ((a ≠ b) and ((a is "blue") or (b is "red")))
▲ end isGreater
end script▼
-- Return the sorted list.▼
return o's balls
end DutchNationalFlagProblem
Line 527 ⟶ 523:
Result:
{"red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "red", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "white", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue", "blue"}</pre>
In the unlikely event of this being something you'll want done often at very high speeds, Dijkstra's own algorithm for the task is somewhat faster:
<syntaxhighlight lang="applescript">on threeWayPartition(theList, order) -- Dijkstra's algorithm.
property lst : theList
▲ end script
set {v1, v2, v3} to order
set {i, j, k} to {1, 1, (count o's lst)}
repeat until (j > k)
set this to o's lst's item j
if (this = v3) then
set o's lst's item j to o's lst's item k
set o's lst's item k to this
set k to k - 1
else
if (this = v1) then
set o's lst's item j to o's lst's item i
set o's lst's item i to this
set i to i + 1
end if
set j to j + 1
end if
end repeat
end threeWayPartition
on DutchNationalFlagProblem(numberOfBalls)
script o
property balls : {}
end script
set colours to {"red", "white", "blue"}
repeat numberOfBalls times
set end of o's balls to some item of colours
end repeat
threeWayPartition(o's balls, colours)
return o's balls
end DutchNationalFlagProblem
DutchNationalFlagProblem(100)</syntaxhighlight>
=={{header|Applesoft BASIC}}==
|