Dutch national flag problem: Difference between revisions
Added Uiua solution
(Dutch national flag problem in BASIC256) |
(Added Uiua solution) |
||
(29 intermediate revisions by 16 users not shown) | |||
Line 27:
{{trans|Python: Construct from ball counts}}
<
F dutch_flag_sort3(items)
Line 38:
print(‘Original Ball order: ’balls)
V sorted_balls = dutch_flag_sort3(balls)
print(‘Sorted Ball Order: ’sorted_balls)</
{{out}}
Line 49:
This works for ABAP Version 7.40 and above, the color blue is excluded as an option for the last entry to insure an unsorted sequence.
<syntaxhighlight lang="abap">
report z_dutch_national_flag_problem.
Line 208:
write:|{ sequence }, is sorted? -> { dutch_national_flag_problem->is_sorted( sequence ) }|, /.
</syntaxhighlight>
{{output}}
Line 219:
=={{header|Action!}}==
{{libheader|Action! Tool Kit}}
<
PROC PrintArray(BYTE ARRAY a BYTE len)
Line 276:
PrintE("Sorting is invalid!")
FI
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Dutch_national_flag_problem.png Screenshot from Atari 8-bit computer]
Line 291:
=={{header|Ada}}==
<
procedure Dutch_National_Flag is
Line 389:
Print("After Sorting: ", A);
end Dutch_National_Flag;</
{{out}}
Line 404:
=={{header|ALGOL 68}}==
<
# ball sets are represented by STRING items, red by "R", white by "W" and blue by "B" #
# returns the balls sorted into red, white and blue order #
Line 480:
print( ( "after: ", balls, IF sorted balls( balls ) THEN "" ELSE " NOT" FI, " sorted", newline ) )
OD
END</
{{out}}
<pre>
Line 492:
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">use AppleScript version "2.3.1" -- OS X 10.9 (Mavericks) or later.
use sorter : script ¬
on DutchNationalFlagProblem(numberOfBalls)
script o
property colours : {"red", "white", "blue"}
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
repeat numberOfBalls times
set end of o's balls to some item of o's colours
end repeat
return o's balls
end DutchNationalFlagProblem
DutchNationalFlagProblem(100)</
{{output}}
<pre>Log:
(*blue,
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", "
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}}==
{{trans|ZX_Spectrum_Basic}}
<syntaxhighlight lang="applesoftbasic"> 100 READ C$(0),C$(1),C$(2)
110 DATARED,WHITE,BLUE,0
120 PRINT "RANDOM:
130 FOR N = 0 TO 9
140 LET B%(N) = RND (1) * 3
150 GOSUB 250
160 NEXT N
170 PRINT
180 READ S
190 PRINT "SORTED:
200 FOR I = 0 TO 2
210 FOR N = 0 TO 9
220 ON B%(N) = I GOSUB 250
230 NEXT N,I
240 END
250 PRINT SPC( S)C$(B%(N));
260 LET S = 1
270 RETURN </syntaxhighlight>
=={{header|AutoHotkey}}==
<
Random,k,3,MaxBalls
Loop,% k{
Line 549 ⟶ 602:
F:=RTrim(F,",")
Sort,F,N D`,
MsgBox,% F:=RegExReplace(RegExReplace(RegExReplace(F,"(1)","Red"),"(2)","White"),"(3)","Blue")</
=={{header|AutoIt}}==
Given each color a value in descending order ( Red = 1, White = 2 And Blue = 3)
<syntaxhighlight lang="autoit">
#include <Array.au3>
Dutch_Flag(50)
Line 578 ⟶ 631:
_ArrayDisplay($avArray)
EndFunc ;==>Dutch_Flag
</syntaxhighlight>
=={{header|AWK}}==
{{works with|gawk}}
<
BEGIN {
weight[1] = "red"; weight[2] = "white"; weight[3] = "blue";
Line 630 ⟶ 683:
return 1
}
</syntaxhighlight>
Output:
<syntaxhighlight lang="text">
BEFORE: blue red white red white blue red white blue white
Line 640 ⟶ 693:
Sorting is valid.
</syntaxhighlight>
=={{header|
==={{header|BaCon}}===
<syntaxhighlight lang="qbasic">DECLARE color$[] = { "red", "white", "blue" }
DOTIMES 16
Line 651 ⟶ 705:
PRINT "Unsorted: ", ball$
PRINT " Sorted: ", REPLACE$(SORT$(REPLACE$(ball$, "blue", "z")), "z", "blue")</
{{out}}
<pre>
Line 658 ⟶ 712:
</pre>
==={{header|BASIC256}}===
<
dim flag = {"Red","White","Blue"}
dim balls(9)
Line 677 ⟶ 731:
if balls[j] = kolor then print balls[j]; " |";
next j
next i</
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<
Sort% = FN_sortinit(0,0)
Line 718 ⟶ 772:
prev% = weight%
NEXT
IF NOT sorted% PRINT "Error: Balls are not in correct order!"</
{{out}}
<pre>
Line 726 ⟶ 780:
=={{header|C}}==
<
#include <stdlib.h> //srand(), rand(), RAND_MAX, qsort()
#include <stdbool.h> //true, false
Line 779 ⟶ 833:
}
return 0;
}</
{{out}}
<pre>Accidentally still sorted:rrrww
Line 786 ⟶ 840:
=={{header|C++}}==
<
#include <iostream>
Line 826 ⟶ 880:
dnf_partition(balls, balls + 9, WHITE, BLUE);
print(balls, 9);
}</
{{out}}
<pre>
Line 836 ⟶ 890:
=={{header|C_sharp|C#}}==
<
using System.Collections.Generic;
using System.Linq;
Line 911 ⟶ 965:
}
}
</syntaxhighlight>
=={{header|Ceylon}}==
Be sure to add ceylon.random in your module.ceylon file.
<
DefaultRandom
Line 996 ⟶ 1,050:
print(sortedBalls1);
print(sortedBalls2);
}</
=={{header|Clojure}}==
<
(get {:red 1 :white 2 :blue 3} color))
Line 1,018 ⟶ 1,072:
(if in-dutch-flag-order?
(recur num-balls)
balls)))</
{{out}}
Line 1,028 ⟶ 1,082:
(sort-in-dutch-flag-order balls) ; (:red :red :red :red :red :white :white :white :white :white
; :white :white :blue :blue :blue :blue :blue :blue :blue :blue)
</pre>
=={{header|Common Lisp}}==
{{trans|Clojure}}
<syntaxhighlight lang="lisp">
(defun dutch-flag-order (color)
(case color (:red 1) (:white 2) (:blue 3)))
(defun sort-in-dutch-flag-order (balls)
(sort (copy-list balls) #'< :key #'dutch-flag-order))
(defun make-random-balls (count)
(loop :repeat count
:collect (nth (random 3) '(:red :white :blue))))
(defun make-balls (count)
(loop :for balls = (make-random-balls count)
:while (equal balls (sort-in-dutch-flag-order balls))
:finally (return balls)))
;; Alternative version showcasing iterate's finding clause
(defun make-balls2 (count)
(iter (for balls = (make-random-balls count))
(finding balls such-that (not (equal balls (sort-in-dutch-flag-order balls))))))
</syntaxhighlight>
{{out}}
<pre>
CL-USER> (defvar *balls* (make-balls 20))
*BALLS*
CL-USER> *balls*
(:WHITE :WHITE :WHITE :WHITE :RED :BLUE :RED :RED :WHITE :WHITE :RED :BLUE :RED
:RED :BLUE :WHITE :BLUE :BLUE :BLUE :BLUE)
CL-USER> (sort-in-dutch-flag-order *balls*)
(:RED :RED :RED :RED :RED :RED :WHITE :WHITE :WHITE :WHITE :WHITE :WHITE :WHITE
:BLUE :BLUE :BLUE :BLUE :BLUE :BLUE :BLUE)
</pre>
=={{header|D}}==
<
enum DutchColors { red, white, blue }
Line 1,061 ⟶ 1,150:
writeln("\nSorted Ball Order:\n", balls);
assert(balls[].isSorted, "Balls not sorted.");
}</
{{out}}
<pre>Original Ball order:
Line 1,070 ⟶ 1,159:
===Bidirectional Range Version===
<
std.array, std.traits;
Line 1,141 ⟶ 1,230:
assert(balls[0 .. n].isSorted());
}
}</
The output is the same.
Line 1,147 ⟶ 1,236:
This version uses more contract programming and asserts to verify the code correctness.
With hints from: toccata.lri.fr/gallery/flag.en.html
<
enum Color : ubyte { blue, white, red }
Line 1,239 ⟶ 1,328:
writeln("\nSorted Ball Order:\n", balls);
assert(balls[].isSorted, "Balls not sorted.");
}</
The output is the same.
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|Classes,SysUtils,StdCtrls}}
Encodes the colors to strings of "1" "2" and "3" to allow them to be sorted. Then it sses Delphi TStringList to sort the colors.
<syntaxhighlight lang="Delphi">
const TestOrder: array [0..11] of string =
('Blue','Blue','White','Blue','White','Blue',
'Red','White','White','Blue','White','Red');
procedure DoDutchFlag(Memo: TMemo; Order: array of string);
{Solve dutch flag color order using TStringList component}
{Encode colors "Red", "White" and "Blue" to "1", "2", and "3" }
{This allows them to be sorted in the TString List}
var I: integer;
var SL: TStringList;
var S2: string;
function DecodeList(SL: TStringList): string;
{Convert encoded colors 1, 2 and 3 to Red, White and Blue}
var I: integer;
begin
Result:='';
for I:=0 to SL.Count-1 do
begin
if I>0 then Result:=Result+',';
if SL[I]='1' then Result:=Result+'Red'
else if SL[I]='2' then Result:=Result+'White'
else Result:=Result+'Blue'
end;
end;
begin
SL:=TStringList.Create;
try
{Encode colors from array of strings}
for I:=0 to High(TestOrder) do
begin
if Order[I]='Red' then SL.Add('1')
else if Order[I]='White' then SL.Add('2')
else SL.Add('3');
end;
Memo.Lines.Add('Original Order:');
Memo.Lines.Add('['+DecodeList(SL)+']');
SL.Sort;
Memo.Lines.Add('Original Order:');
Memo.Lines.Add('['+DecodeList(SL)+']');
finally SL.Free; end;
end;
procedure ShowDutchFlag(Memo: TMemo);
begin
DoDutchFlag(Memo,TestOrder);
end;
</syntaxhighlight>
{{out}}
<pre>
Original Order:
[Blue,Blue,White,Blue,White,Blue,Red,White,White,Blue,White,Red]
Original Order:
[Red,Red,White,White,White,White,White,Blue,Blue,Blue,Blue,Blue]
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
col$[] = [ "red" "white" "blue" ]
for i to 8
b[] &= randint 3
.
for b in b[]
write col$[b] & " "
if b < b0
not_sorted = 1
.
b0 = b
.
print ""
print ""
if not_sorted = 0
print "already sorted"
else
for i = 1 to len b[] - 1
for j = i + 1 to len b[]
if b[j] < b[i]
swap b[j] b[i]
.
.
.
for b in b[]
write col$[b] & " "
.
.
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<
defp ball(:red), do: 1
defp ball(:white), do: 2
Line 1,276 ⟶ 1,464:
end
Dutch_national_flag.problem</
{{out}}
Line 1,287 ⟶ 1,475:
=={{header|Erlang}}==
<
-export([random_balls/1, is_dutch/1, dutch/1]).
Line 1,312 ⟶ 1,500:
dutch(R, W, B, [red | L]) -> dutch([red|R], W, B, L);
dutch(R, W, B, [white | L]) -> dutch(R, [white|W], B, L);
dutch(R, W, B, [blue | L]) -> dutch(R, W, [blue|B], L).</
Sample usage:
<
L = random_balls(10),
case is_dutch(L) of
true -> io:format("The random sequence ~p is already in the order of the Dutch flag!~n", [L]);
false -> io:format("The starting random sequence is ~p;~nThe ordered sequence is ~p.~n", [L, dutch(L)])
end.</
{{out}}
Line 1,329 ⟶ 1,517:
=={{header|F_Sharp|F#}}==
<
* Changing the order is only allowed by swapping 2 elements
* Every element must only be inspected once
Line 1,362 ⟶ 1,550:
let sorted = rs @ ws @ bs
printfn "The sequence %A is sorted: %b" sorted (isDutch sorted)
0</
{{out}}
<pre>Sort the sequence of 10 balls: [Red; White; Red; Blue; White; White; Blue; Blue; White; White]
Line 1,369 ⟶ 1,557:
=={{header|Factor}}==
{{works with|Factor|0.99 2020-01-23}}
<
sequences ;
Line 1,388 ⟶ 1,576:
] while 3nip ;
10 3 random-non-sorted-integers dup . dnf-sort! .</
{{out}}
<pre>
Line 1,403 ⟶ 1,591:
https://github.com/bfox9900/CAMEL99-V2/blob/master/Video/DIJKSTRAFLAG%20.mp4
<syntaxhighlight lang="text">\ Dutch flag DEMO for CAMEL99 Forth
\ *SORTS IN PLACE FROM Video MEMORY*
Line 1,551 ⟶ 1,739:
CR ." Completed"
;
</syntaxhighlight>
=={{header|Fortran}}==
Line 1,557 ⟶ 1,745:
Abhor code duplication. I've repeated code anyway to demonstrate FORTRAN pointers, which behave like an alias. A subroutine with traditional arguments including the number of valid elements of the array is appropriate. I'd use one long array instead of 3 arrays and the size intrinsic.
<syntaxhighlight lang="text">
!-*- mode: compilation; default-directory: "/tmp/" -*-
!Compilation started at Mon Jun 3 11:18:24
Line 1,663 ⟶ 1,851:
end program Netherlands
</syntaxhighlight>
=={{header|FreeBASIC}}==
<
' El problema planteado por Edsger Dijkstra es:
' "Dado un número de bolas rojas, azules y blancas en orden aleatorio,
Line 1,690 ⟶ 1,878:
Next i
End
</syntaxhighlight>
=={{header|Gambas}}==
'''[https://gambas-playground.proko.eu/?gist=e57a862aff12647fa80c84a595161cb9 Click this link to run this code]'''
<
Dim Red As String = "0"
Dim White As String = "1"
Line 1,719 ⟶ 1,907:
Next
End</
Output:
<pre>
Line 1,727 ⟶ 1,915:
=={{header|Go}}==
<
import (
Line 1,814 ⟶ 2,002:
f.sort3()
fmt.Println(f)
}</
{{out}}
<pre>
Line 1,831 ⟶ 2,019:
The function "sort" works with anything that belongs to the Eq and Ord classes.
The function "randomRIO" takes a range of two integers to give a random value within the range. We make Color an instance of Enum so that we can give Red, White and Blue as integers to randomRIO and convert the random number back to Red, White or Blue.
<
import System.Random (randomRIO)
import System.IO.Unsafe (unsafePerformIO)
Line 1,856 ⟶ 2,044:
False -> do
putStrLn $ "The starting random sequence is " ++ show a ++ "\n"
putStrLn $ "The ordered sequence is " ++ show (dutch a)</
{{out}}
<pre>
Line 1,867 ⟶ 2,055:
To understand ''why'' Dijsktra was interested in the problem, here's an example showing difficiency of using generic sort:
<
mk012 :: Int -> Int -> [Int] -- definitely unordered
Line 1,887 ⟶ 2,075:
-- print $ inorder $ dutch1 s -- O(n)
print $ inorder $ dutch2 s -- O(n)
where s = mk012 10000000 42</
=={{header|Icon}} and {{header|Unicon}}==
Line 1,899 ⟶ 2,087:
force at least one of each color ball, change "?n-1" to "?n" in the 3rd line.
<
n := integer(!a) | 20
every (nr|nw|nb) := ?n-1
Line 1,920 ⟶ 2,108:
every (s := "") ||:= (find(c := !cset(w),w),c)
return s
end</
A few sample runs:
Line 1,942 ⟶ 2,130:
=={{header|J}}==
We shall define a routine to convert the values 0 1 2 to ball names:
<
and its inverse
<
Next, we need a random assortment of balls:
<
BALLS
┌────┬───┬────┬───┬───┬─────┬─────┬─────┬────┬────┬─────┬────┬────┬───┬────┬───┬─────┬───┬────┬───┐
│blue│red│blue│red│red│white│white│white│blue│blue│white│blue│blue│red│blue│red│white│red│blue│red│
└────┴───┴────┴───┴───┴─────┴─────┴─────┴────┴────┴─────┴────┴────┴───┴────┴───┴─────┴───┴────┴───┘</
And we want to sort them in their canonical order:
<
┌───┬───┬───┬───┬───┬───┬───┬─────┬─────┬─────┬─────┬─────┬────┬────┬────┬────┬────┬────┬────┬────┐
│red│red│red│red│red│red│red│white│white│white│white│white│blue│blue│blue│blue│blue│blue│blue│blue│
└───┴───┴───┴───┴───┴───┴───┴─────┴─────┴─────┴─────┴─────┴────┴────┴────┴────┴────┴────┴────┴────┘</
Note that if we were not using J's built in sort, we would probably want to use [[Counting_sort|bin sort]] here.
Anyways, we can test that they are indeed sorted properly:
<
=={{header|Java}}==
The elements of an <code>enum</code> implement <code>Comparable</code> so the build-in sort works. You can also use this comparability to check the sort has worked.
<
import java.util.Random;
Line 1,992 ⟶ 2,180:
System.out.println("Correctly sorted: " + sorted);
}
}</
{{out}}
Line 2,001 ⟶ 2,189:
=={{header|Javascript}}==
===ES6===
<
/**
Line 2,082 ⟶ 2,270:
};
dutchNationalFlag();
</syntaxhighlight>
{{out}}
<pre>
Line 2,091 ⟶ 2,279:
Dutch Sorted balls: Red,Red,Red,Red,Red,Red,Red,Red,Red,White,White,White,White,White,White,White,Blue,Blue,Blue,Blue,Blue,Blue
Is sorted: true
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq.'''
'''Adapted from [[#Wren|Wren]]'''
In the following, /dev/random is used as a source of entropy.
In a bash or bash-like environment, a suitable invocation would
be as follows:
<pre>
< /dev/random tr -cd '0-9' | fold -w 1 | jq -Mcnr -f dnf.jq
</pre>
'''dnf.jq'''
<syntaxhighlight lang=jq>
# Output: a PRN in range(0; .)
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
def colors: ["Red", "White", "Blue"];
def colorMap: {"Red": 0, "White": 1, "Blue": 2 };
def task($nballs):
def sorted:
. == sort_by(colorMap[.]);
def generate:
[range(0; $nballs) | colors[ 3|prn ] ]
| if sorted then generate else . end;
generate
| "Before sorting : \(.)",
"After sorting : \(sort_by(colorMap[.]))" ;
task(9)
</syntaxhighlight>
{{output}}
<pre>
Before sorting : ["Blue","Red","Blue","White","Blue","White","Red","White","Blue"]
After sorting : ["Red","Red","White","White","White","Blue","Blue","Blue","Blue"]
</pre>
Line 2,097 ⟶ 2,329:
'''Function'''
<syntaxhighlight lang="julia">
const COLORS = ["red", "white", "blue"]
Line 2,122 ⟶ 2,354:
dutchsort!(copy(a), lo, hi)
end
</syntaxhighlight>
'''Main'''
<syntaxhighlight lang="julia">
function formatdf(a::Array{ASCIIString,1})
i = 0
Line 2,156 ⟶ 2,388:
@time e = sort(d, by=x->findfirst(COLORS, x))
println(formatdf(e))
</syntaxhighlight>
{{out}}
Line 2,176 ⟶ 2,408:
=={{header|Kotlin}}==
{{trans|D}}
<
import java.util.Random
Line 2,228 ⟶ 2,460:
// print the colors of the balls after sorting
println("After sorting : ${balls.contentToString()}")
}</
Sample output:
Line 2,237 ⟶ 2,469:
=={{header|Lasso}}==
<
local(r = array, w = array, b = array)
with i in #a do => {
Line 2,252 ⟶ 2,484:
}
orderdutchflag(array('Red', 'Red', 'Blue', 'Blue', 'Blue', 'Red', 'Red', 'Red', 'White', 'Blue'))</
{{out}}
<pre>array(Red, Red, Red, Red, Red, White, Blue, Blue, Blue, Blue)</pre>
=={{header|Logo}}==
<
make "colors {red white blue}
Line 2,324 ⟶ 2,556:
setitem :a :array item :b :array
setitem :b :array :temp
end</
Test code:
<syntaxhighlight lang="text">do.while [
make "list random_balls 10
] [dutch? :list]
Line 2,333 ⟶ 2,565:
print (sentence [Start list:] arraytolist :list)
print (sentence [Sorted:] arraytolist dutch :list)
bye</
{{out}}
Line 2,341 ⟶ 2,573:
=={{header|Lua}}==
The task seems to allow for some interpretation, so attempting to follow as literally as possible.
<
math.randomseed(os.time())
N, balls, colors = 10, {}, { "red", "white", "blue" }
Line 2,367 ⟶ 2,599:
-- "3. Check the sorted balls are in the order of the Dutch national flag."
print("SORTED: "..table.concat(balls,","))
print(issorted(balls) and "Properly sorted." or "IMPROPERLY SORTED!!")</
{{out}}
<pre>RANDOM: white,white,blue,blue,red,red,blue,white,red,white
Line 2,376 ⟶ 2,608:
Most times the Three Way Partition makes more changed than the first algorithm. Also if the array is sorted from the start, no changes give the first algorithm and 23 changes the Three Way Partition,
<syntaxhighlight lang="m2000 interpreter">
Report "Dutch Flag from Dijkstra"
const center=2
Line 2,541 ⟶ 2,773:
Print "changes: "; many
</syntaxhighlight>
{{out}}
Line 2,561 ⟶ 2,793:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
{{out}}
<pre>flagSort[{WHITE, RED, RED, WHITE, WHITE, BLUE, WHITE, BLUE, BLUE, WHITE, WHITE, BLUE}]
Line 2,572 ⟶ 2,804:
The number of colors may be specified as argument in the command line. By default, 10 colors are randomly chosen.
<
type Color {.pure.} = enum Red = "R", White = "W", Blue = "B"
Line 2,635 ⟶ 2,867:
threeWayPartition(sortedColors, White)
doAssert sortedColors.isSorted()
echo "Sorted: ", sortedColors.join("")</
{{out}}
Line 2,644 ⟶ 2,876:
=={{header|PARI/GP}}==
A [[counting sort]] might be more appropriate here, but that would conceal the details of the sort.
<
if (a==b,
0
Line 2,657 ⟶ 2,889:
while(inorder(v), v=r(10));
v=vecsort(v,compare);
inorder(v)</
{{out}}
Line 2,664 ⟶ 2,896:
=={{header|Perl}}==
The task is probably not to just sort an array. The wikipedia links has a slightly better explanation that leads to the following code:
<
use strict;
use 5.010; # //
Line 2,735 ⟶ 2,967:
show($balls);
are_ordered($balls) or die "Incorrect\n";</
You can run it with no parameters, it sorts 10 balls in such a case. If you provide one parameter, it is used as the number of balls. The second parameter turns on debugging that shows how the balls are being swapped.
=={{header|Phix}}==
Minimizes the number of read and swap operations, straight translation of the wikipedia pseudocode:
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">three_way_partition</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">mid</span><span style="color: #0000FF;">)</span>
Line 2,780 ⟶ 3,012:
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Unsorted"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">unsorted</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Sorted"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sorted</span><span style="color: #0000FF;">)</span>
<!--</
<small>I thought of unsorted=shuffle(unsorted) in the "oops" loop, but of course that'd repeat forever should they all be the same colour.</small>
{{out}}
Line 2,789 ⟶ 3,021:
=={{header|Picat}}==
<
_ = random2(), % random seed
N = 21,
Line 2,812 ⟶ 3,044:
dutch_sort(L,MapInv) = [R : _=R in [MapInv.get(R)=R : R in L].sort()].
inverse(Map) = new_map([V=K : K=V in Map]).</
{{out}}
Line 2,819 ⟶ 3,051:
=={{header|PicoLisp}}==
<
(list
(def 'RED 1)
Line 2,831 ⟶ 3,063:
(prin "Sorted balls ")
(print S)
(prinl " are sorted") )</
{{out}}
<pre>Original balls (RED BLUE WHITE BLUE BLUE RED WHITE WHITE WHITE) not sorted
Line 2,838 ⟶ 3,070:
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<syntaxhighlight lang="powershell">
$Colors = 'red', 'white','blue'
Line 2,855 ⟶ 3,087:
''
$SortedBalls
</syntaxhighlight>
{{out}}
<pre>
Line 2,884 ⟶ 3,116:
Works with SWI-Prolog 6.1.11
===Prolog spirit===
<
length(L, N),
repeat,
Line 2,943 ⟶ 3,175:
is_dutch_flag_blue([]).
</syntaxhighlight>
{{out}}
<pre> ?- dutch_flag(20).
Line 2,956 ⟶ 3,188:
===Functional spirit===
Use of filters.
<
length(L, N),
Line 3,018 ⟶ 3,250:
is_dutch_flag_blue([]).
</syntaxhighlight>
=={{header|Python}}==
===Python: Sorted===
The heart of the idiomatic Dutch sort in python is the call to function <code>sorted</code> in function <code>dutch_flag_sort</code>.
<
colours_in_order = 'Red White Blue'.split()
Line 3,057 ⟶ 3,289:
if __name__ == '__main__':
main()</
{{out|Sample output}}
<pre>Original Ball order: ['Red', 'Red', 'Blue', 'Blue', 'Blue', 'Red', 'Red', 'Red', 'White', 'Blue']
Line 3,067 ⟶ 3,299:
Replace the function/function call dutch_flag_sort above, with dutch_flag_sort2 defined as:
<
def dutch_flag_sort2(items, order=colours_in_order):
'return summed filter of items using the given order'
return list(chain.from_iterable(filter(lambda c: c==colour, items)
for colour in order))</
Or equivalently using a list comprehension (though perhaps less clear):
<
'return summed filter of items using the given order'
return [c for colour in order for c in items if c==colour]</
Output follows that of the sorting solution above.
Line 3,083 ⟶ 3,315:
Replace the function/function call dutch_flag_sort above, with dutch_flag_sort3 defined as:
<
'counts each colour to construct flag'
return sum([[colour] * items.count(colour) for colour in order], [])</
Output follows that of the sorting solution above.
===Python: Explicit in-place sort===
<
colours_in_order = 'Red White Blue'.split()
Line 3,138 ⟶ 3,370:
if __name__ == '__main__':
main()</
Output follows that of the sorting solution above.
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
Line 3,179 ⟶ 3,411:
balls sorted (if (dutch-order? sorted) 'OK 'BAD)))
(for-each test (list sort-balls/key sort-balls/compare))
</syntaxhighlight>
{{out}}
Line 3,196 ⟶ 3,428:
(formerly Perl 6)
Here are five ways to do it, all one liners (apart from the test apparatus).
<syntaxhighlight lang="raku"
my @colors;
Line 3,225 ⟶ 3,457:
say "Using multiple greps";
how'bout { @colors = flat (.grep(red), .grep(white), .grep(blue) given @colors) }</
{{out}}
<pre>Using functional sort
Line 3,263 ⟶ 3,495:
The REXX solution could've been simplified somewhat by the use of the '''countstr''' BIF (but some older REXX interpreters don't have).
<
/*────────────────────────────────── order of colors on the Dutch flag: red white blue.*/
parse arg N colors /*obtain optional arguments from the CL*/
Line 3,294 ⟶ 3,526:
/*──────────────────────────────────────────────────────────────────────────────────────*/
countWords: procedure; parse arg ?,hay; s=1
do r=0 until _==0; _=wordpos(?, hay, s); s=_+1; end /*r*/; return r</
'''output''' when using the default input:
<pre>
Line 3,311 ⟶ 3,543:
===colors (as letters)===
<
/*────────────────────────────────── order of colors on the Dutch flag: red white blue.*/
parse arg N colors /*obtain optional arguments from the CL*/
Line 3,339 ⟶ 3,571:
say
say 'The sorted colored ball list has been confirmed as being sorted correctly.'
exit /*stick a fork in it, we're all done. */</
'''output''' when using the default input:
<pre>
Line 3,356 ⟶ 3,588:
=={{header|Ring}}==
<
# Project : Dutch national flag problem
Line 3,379 ⟶ 3,611:
next
next
</syntaxhighlight>
Output:
<pre>
Line 3,387 ⟶ 3,619:
=={{header|Ruby}}==
<
FLAG = {red: 1, white: 2, blue: 3}
Line 3,412 ⟶ 3,644:
puts "Random: #{balls}"
puts "Sorted: #{balls.sort}"
</
{{out}}
<pre>Random: [blue, red, red, red, blue, blue, white, red]
Line 3,419 ⟶ 3,651:
=={{header|Run BASIC}}==
<
print "Random: |";
Line 3,436 ⟶ 3,668:
end if
next j
next i</
<pre>Random: |White |Blue |White |Red |Red |White |Red |Blue |Red |White |
Sorted: |Red |Red |Red |Red |White |White |White |White |Blue |Blue |</pre>
Line 3,442 ⟶ 3,674:
=={{header|Rust}}==
{{libheader|rand}}
<
use rand::Rng;
Line 3,485 ⟶ 3,717:
println!("Oops, did not sort colors correctly!");
}
}</
=={{header|Scala}}==
<
type FlagColor = Value
val Red, White, Blue = Value
Line 3,498 ⟶ 3,730:
println(s"Generated balls (${genBalls mkString " "}) are $sorted.")
println(s"Sorted balls (${sortedBalls mkString " "}) are sorted.")</
{{out}}
<pre>Generated balls (Blue Blue Blue White Blue Blue Red Red Blue White) are not sorted.
Sorted balls (Red Red White White Blue Blue Blue Blue Blue Blue) are sorted.</pre>
=={{header|sed}}==
The first part of the task is skipped, as there is no possibility to create random data within ''sed'' itself.
<syntaxhighlight lang="sed">:la
s/\(WW*\)\([RB].*\)/\2\1/
t la
:lb
s/\(BB*\)\([RW].*\)/\2\1/
t lb
/^RR*WW*BB*$/!d</syntaxhighlight>
{{out}}
<pre>
$ echo WRRWRRRBBWBRRWBWWB | sed -f dutch_flag_sort.sed
RRRRRRRWWWWWWBBBBB
</pre>
=={{header|SQL}}==
<
create table colours (id integer primary key, name varchar(5));
insert into colours (id, name) values ( 1, 'red' );
Line 3,539 ⟶ 3,786:
-- Tidy up
drop table balls;
drop table colours;</
{{out}}
<pre>COLOUR
Line 3,566 ⟶ 3,813:
# ''Sort the balls in a way idiomatic to your language.'' Yup!
# ''Check the sorted balls are in the order of the Dutch national flag.'' Not checked beyond eyeballing - is there a db implementation that gets <tt>order by</tt> wrong??
=={{header|Swift}}==
<syntaxhighlight lang="swift">// Algorithm from https://en.wikipedia.org/wiki/Dutch_national_flag_problem
func partition3<T: Comparable>(_ a: inout [T], mid: T) {
var i = 0
var j = 0
var k = a.count - 1
while j <= k {
if a[j] < mid {
a.swapAt(i, j);
i += 1;
j += 1;
} else if a[j] > mid {
a.swapAt(j, k);
k -= 1;
} else {
j += 1;
}
}
}
func isSorted<T: Comparable>(_ a: [T]) -> Bool {
var i = 0
let n = a.count
while i + 1 < n {
if a[i] > a[i + 1] {
return false
}
i += 1
}
return true
}
enum Ball : CustomStringConvertible, Comparable {
case red
case white
case blue
var description : String {
switch self {
case .red: return "red"
case .white: return "white"
case .blue: return "blue"
}
}
}
var balls: [Ball] = [ Ball.red, Ball.white, Ball.blue,
Ball.red, Ball.white, Ball.blue,
Ball.red, Ball.white, Ball.blue]
balls.shuffle()
print("\(balls)")
print("Sorted: \(isSorted(balls))")
partition3(&balls, mid: Ball.white)
print("\(balls)")
print("Sorted: \(isSorted(balls))")</syntaxhighlight>
{{out}}
<pre>
[white, blue, red, red, white, blue, red, blue, white]
Sorted: false
[red, red, red, white, white, white, blue, blue, blue]
Sorted: true
</pre>
=={{header|Tcl}}==
This isn't very efficient in terms of the sorting itself (and it happens to use <code>lsearch</code> twice in the comparator!) but it is very simple to write like this.
<
proc dutchflagcompare {a b} {
set colors {red white blue}
Line 3,598 ⟶ 3,910:
} else {
puts "sort failed\n$sorted"
}</
{{out}}
<pre>
Line 3,605 ⟶ 3,917:
</pre>
=={{header|uBasic/4tH}}==
This version is based on Edsger Dijkstra's original algorithm. The flag may come out a bit shredded , but it has been assembled the correct way.
<syntaxhighlight lang="text">s = 100
For x = 0 To s-1
@(x) = Rnd(3)
Next
' Edsger Dijkstra algorithm starts here
i = 0
j = 0
k = s-1
Do
While j < k+1
If @(j) = 0 Then ' case "red"
Push @(j) : @(j) = @(i) : @(i) = Pop()
i = i + 1 ' fairly efficient exchange
j = j + 1
Else If @(j) = 2 Then ' case "blue"
Push @(j) : @(j) = @(k) : @(k) = Pop()
k = k - 1 ' fairly efficient exchange
Else ' you'd expect case "white" here
j = j + 1
Endif Endif
Loop
' end of Dijkstra's algorithm
n = 0
For x = 0 To s-1 ' now show the whole shebang
If @(x) # n Then Print : n = @(x)
Print Chr(Peek ("RWB", @(x)));
Next
Print</syntaxhighlight>
{{Out}}
<pre>RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
0 OK, 0:858</pre>
=={{header|Uiua}}==
Steps:
# Carefully pick the symbols to give the required order.
# Assume Kai is better at writing algorithms than I am.
<syntaxhighlight lang="uiua">
⊸⊏⊸⍏[⍥(⊡⌊×3⚂"RWb")30] # Build it, sort it.
⟨"oops"|"sorted"⟩≍⇡⧻⟜⍏. # Print it, confirm it.
</syntaxhighlight>
{{out}}
<pre>
"RRWWWRbbWRWWRRWWbbbRWbWWWRbRbb"
"RRRRRRRRRWWWWWWWWWWWWbbbbbbbbb"
"sorted"
</pre>
=={{header|UNIX Shell}}==
{{works with|Bash}}
<
# to go from name to number, we make variables out of the color names
Line 3,664 ⟶ 4,031:
done
echo "${a[@]}"
}</
Test code:
<
balls=()
while (( ${#balls[@]} < len )) || dutch? "${balls[@]}"; do
Line 3,674 ⟶ 4,041:
echo "Initial list: ${balls[@]}"
balls=($(dutch "${balls[@]}"))
echo "Sorted: ${balls[@]}"</
{{out}}
Line 3,681 ⟶ 4,048:
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
'Solution derived from http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/.
Line 3,726 ⟶ 4,093:
WScript.StdOut.Write "Sorted: " & sort(unsort)
WScript.StdOut.WriteLine
</syntaxhighlight>
{{Out}}
Line 3,736 ⟶ 4,103:
=={{header|Visual FoxPro}}==
===SQL Version===
<
CLOSE DATABASES ALL
LOCAL lcCollate As String, i As Integer, n As Integer
Line 3,771 ⟶ 4,138:
RETURN INT(3*RAND()) + 1
ENDFUNC
</syntaxhighlight>
===Array Version===
<
LOCAL i As Integer, n As Integer, colours As String, k As Integer
colours = "Red,White,Blue"
Line 3,809 ⟶ 4,176:
RETURN INT(3*RAND()) + 1
ENDFUNC
</syntaxhighlight>
=={{header|Wren}}==
{{libheader|Wren-sort}}
<
import "./sort" for Sort
var colors = ["Red", "White", "Blue"]
Line 3,830 ⟶ 4,197:
System.print("Before sorting : %(balls)")
Sort.insertion(balls, colorCmp)
System.print("After sorting : %(balls)")</
{{out}}
Line 3,837 ⟶ 4,204:
Before sorting : [Blue, Blue, White, Blue, White, Blue, Red, White, White]
After sorting : [Red, White, White, White, White, Blue, Blue, Blue, Blue]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">
def Red, White, Blue;
def Size = 10;
int A(Size), N;
proc ShowOrder;
[for N:= 0 to Size-1 do
case A(N) of
Red: Text(0, "Red ");
Blue: Text(0, "Blue ")
other Text(0, "White ");
CrLf(0);
];
proc Part3Ways; \Partition array A three ways (code from Wikipedia)
def Mid = White;
int I, J, K, T;
[I:= 0; J:= 0; K:= Size-1;
while J <= K do
if A(J) < Mid then
[T:= A(I); A(I):= A(J); A(J):= T;
I:= I+1;
J:= J+1;
]
else if A(J) > Mid then
[T:= A(J); A(J):= A(K); A(K):= T;
K:= K-1;
]
else J:= J+1;
];
[for N:= 0 to Size-1 do A(N):= Ran(3);
Text(0, "Original order : ");
ShowOrder;
Part3Ways;
Text(0, "Sorted order : ");
ShowOrder;
]</syntaxhighlight>
{{out}}
<pre>
Original order : Red Red Blue Blue White Red Red White Blue Red
Sorted order : Red Red Red Red Red White White Blue Blue Blue
</pre>
=={{header|zkl}}==
<
fcn colorBalls(balls){ balls.apply(T("red","white","blue").get).concat(", "); }
Line 3,849 ⟶ 4,261:
}while(balls==sortedBalls); // make sure sort does something
println("Original ball order:\n", colorBalls(balls));
println("\nSorted ball order:\n", colorBalls(sortedBalls));</
{{out}}
<pre>
Line 3,861 ⟶ 4,273:
=={{header|ZX Spectrum Basic}}==
{{trans|Run_BASIC}}
<
20 LET c$="RWB"
30 DIM b(10)
Line 3,874 ⟶ 4,286:
120 IF b(j)=i THEN PRINT VAL$ (c$(i)+"$");" ";
130 NEXT j
140 NEXT i</
|