Dutch national flag problem: Difference between revisions

Content added Content deleted
(Added Swift solution)
(→‎{{header|AppleScript}}: Further minor tidy. Also added solution using Dijkstra's algorithm.)
Line 500: Line 500:
property colours : {"red", "white", "blue"}
property colours : {"red", "white", "blue"}
property balls : {}
property balls : {}
⚫
⚫
-- Custom comparison handler for the sort.
⚫
on isGreater(a, b)
⚫
return ((a ≠ b) and ((a is "blue") or (b is "red")))
⚫
end isGreater
end script
end script
Line 505: Line 510:
set end of o's balls to some item of o's colours
set end of o's balls to some item of o's colours
end repeat
end repeat
log o's balls
tell sorter to sort(o's balls, 1, numberOfBalls, {comparer:o})
⚫
-- 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
tell sorter to sort(o's balls, 1, -1, {comparer:redWhiteBlue})
⚫
⚫
-- Return the sorted list.
return o's balls
return o's balls
end DutchNationalFlagProblem
end DutchNationalFlagProblem
Line 527: Line 523:
Result:
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>
{"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.
⚫
script o
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
⚫
return -- Input list sorted in place.
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}}==
=={{header|Applesoft BASIC}}==
Retrieved from "https://rosettacode.org/wiki/Dutch_national_flag_problem"