Dutch national flag problem: Difference between revisions

{{trans|Python: Construct from ball counts}}

F dutch_flag_sort3(items)

print(‘Original Ball order: ’balls)

V sorted_balls = dutch_flag_sort3(balls)

{{out}}

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.

report z_dutch_national_flag_problem.

write:|{ sequence }, is sorted? -> { dutch_national_flag_problem->is_sorted( sequence ) }|, /.

{{output}}

=={{header|Action!}}==

{{libheader|Action! Tool Kit}}

PROC PrintArray(BYTE ARRAY a BYTE len)

PrintE("Sorting is invalid!")

FI

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Dutch_national_flag_problem.png Screenshot from Atari 8-bit computer]

=={{header|Ada}}==

procedure Dutch_National_Flag is

Print("After Sorting: ", A);

{{out}}

=={{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 #

print( ( "after: ", balls, IF sorted balls( balls ) THEN "" ELSE " NOT" FI, " sorted", newline ) )

OD

{{out}}

<pre>

=={{header|AppleScript}}==

-- This script uses a customisable AppleScript sort available at <https://macscripter.net/viewtopic.php?pid=194430#p194430>.

-- It's assumed that scripters will know how and where to install it as a library.

end DutchNationalFlagProblem

{{output}}

=={{header|Applesoft BASIC}}==

{{trans|ZX_Spectrum_Basic}}

110 DATARED,WHITE,BLUE,0

120 PRINT "RANDOM:

250 PRINT SPC( S)C$(B%(N));

260 LET S = 1

=={{header|AutoHotkey}}==

Random,k,3,MaxBalls

Loop,% k{

F:=RTrim(F,",")

Sort,F,N D`,

=={{header|AutoIt}}==

Given each color a value in descending order ( Red = 1, White = 2 And Blue = 3)

#include <Array.au3>

Dutch_Flag(50)

_ArrayDisplay($avArray)

EndFunc ;==>Dutch_Flag

=={{header|AWK}}==

{{works with|gawk}}

BEGIN {

weight[1] = "red"; weight[2] = "white"; weight[3] = "blue";

return 1

}

Output:

BEFORE: blue red white red white blue red white blue white

Sorting is valid.

=={{header|BaCon}}==

DOTIMES 16

PRINT "Unsorted: ", ball$

{{out}}

<pre>

=={{header|BASIC256}}==

dim flag = {"Red","White","Blue"}

dim balls(9)

if balls[j] = kolor then print balls[j]; " |";

next j

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

Sort% = FN_sortinit(0,0)

prev% = weight%

NEXT

{{out}}

<pre>

=={{header|C}}==

#include <stdlib.h> //srand(), rand(), RAND_MAX, qsort()

#include <stdbool.h> //true, false

}

return 0;

{{out}}

<pre>Accidentally still sorted:rrrww

=={{header|C++}}==

#include <iostream>

dnf_partition(balls, balls + 9, WHITE, BLUE);

print(balls, 9);

{{out}}

<pre>

=={{header|C_sharp|C#}}==

using System.Collections.Generic;

using System.Linq;

}

}

=={{header|Ceylon}}==

Be sure to add ceylon.random in your module.ceylon file.

DefaultRandom

print(sortedBalls1);

print(sortedBalls2);

=={{header|Clojure}}==

(get {:red 1 :white 2 :blue 3} color))

(if in-dutch-flag-order?

(recur num-balls)

{{out}}

=={{header|D}}==

enum DutchColors { red, white, blue }

writeln("\nSorted Ball Order:\n", balls);

assert(balls[].isSorted, "Balls not sorted.");

{{out}}

<pre>Original Ball order:

===Bidirectional Range Version===

std.array, std.traits;

assert(balls[0 .. n].isSorted());

}

The output is the same.

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 }

writeln("\nSorted Ball Order:\n", balls);

assert(balls[].isSorted, "Balls not sorted.");

The output is the same.

=={{header|Elixir}}==

{{trans|Erlang}}

defp ball(:red), do: 1

defp ball(:white), do: 2

end

{{out}}

=={{header|Erlang}}==

-export([random_balls/1, is_dutch/1, dutch/1]).

dutch(R, W, B, [red | L]) -> dutch([red|R], W, B, L);

dutch(R, W, B, [white | L]) -> dutch(R, [white|W], 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)])

{{out}}

=={{header|F_Sharp|F#}}==

* Changing the order is only allowed by swapping 2 elements

* Every element must only be inspected once

let sorted = rs @ ws @ bs

printfn "The sequence %A is sorted: %b" sorted (isDutch sorted)

{{out}}

<pre>Sort the sequence of 10 balls: [Red; White; Red; Blue; White; White; Blue; Blue; White; White]

=={{header|Factor}}==

{{works with|Factor|0.99 2020-01-23}}

sequences ;

] while 3nip ;

{{out}}

<pre>

https://github.com/bfox9900/CAMEL99-V2/blob/master/Video/DIJKSTRAFLAG%20.mp4

\ *SORTS IN PLACE FROM Video MEMORY*

CR ." Completed"

;

=={{header|Fortran}}==

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.

!-*- mode: compilation; default-directory: "/tmp/" -*-

!Compilation started at Mon Jun 3 11:18:24

end program Netherlands

=={{header|FreeBASIC}}==

' El problema planteado por Edsger Dijkstra es:

' "Dado un número de bolas rojas, azules y blancas en orden aleatorio,

Next i

End

=={{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"

Next

Output:

<pre>

=={{header|Go}}==

import (

f.sort3()

fmt.Println(f)

{{out}}

<pre>

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)

False -> do

putStrLn $ "The starting random sequence is " ++ show a ++ "\n"

{{out}}

<pre>

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

-- print $ inorder $ dutch1 s -- O(n)

print $ inorder $ dutch2 s -- O(n)

=={{header|Icon}} and {{header|Unicon}}==

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

every (s := "") ||:= (find(c := !cset(w),w),c)

return s

A few sample runs:

=={{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;

System.out.println("Correctly sorted: " + sorted);

}

{{out}}

=={{header|Javascript}}==

===ES6===

/**

};

dutchNationalFlag();

{{out}}

<pre>

'''Function'''

const COLORS = ["red", "white", "blue"]

dutchsort!(copy(a), lo, hi)

end

'''Main'''

function formatdf(a::Array{ASCIIString,1})

i = 0

@time e = sort(d, by=x->findfirst(COLORS, x))

println(formatdf(e))

{{out}}

=={{header|Kotlin}}==

{{trans|D}}

import java.util.Random

// print the colors of the balls after sorting

println("After sorting : ${balls.contentToString()}")

Sample output:

=={{header|Lasso}}==

local(r = array, w = array, b = array)

with i in #a do => {

}

{{out}}

<pre>array(Red, Red, Red, Red, Red, White, Blue, Blue, Blue, Blue)</pre>

=={{header|Logo}}==

make "colors {red white blue}

setitem :a :array item :b :array

setitem :b :array :temp

Test code:

make "list random_balls 10

] [dutch? :list]

print (sentence [Start list:] arraytolist :list)

print (sentence [Sorted:] arraytolist dutch :list)

{{out}}

=={{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" }

-- "3. Check the sorted balls are in the order of the Dutch national flag."

print("SORTED: "..table.concat(balls,","))

{{out}}

<pre>RANDOM: white,white,blue,blue,red,red,blue,white,red,white

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,

Report "Dutch Flag from Dijkstra"

const center=2

Print "changes: "; many

{{out}}

=={{header|Mathematica}} / {{header|Wolfram Language}}==

{{out}}

<pre>flagSort[{WHITE, RED, RED, WHITE, WHITE, BLUE, WHITE, BLUE, BLUE, WHITE, WHITE, BLUE}]

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"

threeWayPartition(sortedColors, White)

doAssert sortedColors.isSorted()

{{out}}

=={{header|PARI/GP}}==

A [[counting sort]] might be more appropriate here, but that would conceal the details of the sort.

if (a==b,

0

while(inorder(v), v=r(10));

v=vecsort(v,compare);

{{out}}

=={{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; # //

show($balls);

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>

<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}}

=={{header|Picat}}==

_ = random2(), % random seed

N = 21,

dutch_sort(L,MapInv) = [R : _=R in [MapInv.get(R)=R : R in L].sort()].

{{out}}

=={{header|PicoLisp}}==

(list

(def 'RED 1)

(prin "Sorted balls ")

(print S)

{{out}}

<pre>Original balls (RED BLUE WHITE BLUE BLUE RED WHITE WHITE WHITE) not sorted

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

$Colors = 'red', 'white','blue'

''

$SortedBalls

{{out}}

<pre>

Works with SWI-Prolog 6.1.11

===Prolog spirit===

length(L, N),

repeat,

is_dutch_flag_blue([]).

{{out}}

<pre> ?- dutch_flag(20).

===Functional spirit===

Use of filters.

length(L, N),

is_dutch_flag_blue([]).

=={{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()

if __name__ == '__main__':

{{out|Sample output}}

<pre>Original Ball order: ['Red', 'Red', 'Blue', 'Blue', 'Blue', 'Red', 'Red', 'Red', 'White', 'Blue']

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)

Or equivalently using a list comprehension (though perhaps less clear):

'return summed filter of items using the given order'

Output follows that of the sorting solution above.

Replace the function/function call dutch_flag_sort above, with dutch_flag_sort3 defined as:

'counts each colour to construct flag'

Output follows that of the sorting solution above.

===Python: Explicit in-place sort===

colours_in_order = 'Red White Blue'.split()

if __name__ == '__main__':

Output follows that of the sorting solution above.

=={{header|Racket}}==

#lang racket

balls sorted (if (dutch-order? sorted) 'OK 'BAD)))

(for-each test (list sort-balls/key sort-balls/compare))

{{out}}

(formerly Perl 6)

Here are five ways to do it, all one liners (apart from the test apparatus).

my @colors;

say "Using multiple greps";

{{out}}

<pre>Using functional sort

The REXX solution could've been simplified somewhat by the use of the &nbsp; '''countstr''' &nbsp; BIF &nbsp; (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*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

countWords: procedure; parse arg ?,hay; s=1

'''output''' &nbsp; when using the default input:

<pre>

===colors (as letters)===

/*────────────────────────────────── order of colors on the Dutch flag: red white blue.*/

parse arg N colors /*obtain optional arguments from the CL*/

say

say 'The sorted colored ball list has been confirmed as being sorted correctly.'

'''output''' &nbsp; when using the default input:

<pre>

=={{header|Ring}}==

# Project : Dutch national flag problem

next

next

Output:

<pre>

=={{header|Ruby}}==

FLAG = {red: 1, white: 2, blue: 3}

puts "Random: #{balls}"

puts "Sorted: #{balls.sort}"

{{out}}

<pre>Random: [blue, red, red, red, blue, blue, white, red]

=={{header|Run BASIC}}==

print "Random: |";

end if

next j

<pre>Random: |White |Blue |White |Red |Red |White |Red |Blue |Red |White |

Sorted: |Red |Red |Red |Red |White |White |White |White |Blue |Blue |</pre>

=={{header|Rust}}==

{{libheader|rand}}

use rand::Rng;

println!("Oops, did not sort colors correctly!");

}

=={{header|Scala}}==

type FlagColor = Value

val Red, White, Blue = Value

println(s"Generated balls (${genBalls mkString " "}) are $sorted.")

{{out}}

=={{header|SQL}}==

create table colours (id integer primary key, name varchar(5));

insert into colours (id, name) values ( 1, 'red' );

-- Tidy up

drop table balls;

{{out}}

<pre>COLOUR

=={{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}

} else {

puts "sort failed\n$sorted"

{{out}}

<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.

For x = 0 To s-1

Next

{{Out}}

<pre>RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

=={{header|UNIX Shell}}==

{{works with|Bash}}

# to go from name to number, we make variables out of the color names

done

echo "${a[@]}"

Test code:

balls=()

while (( ${#balls[@]} < len )) || dutch? "${balls[@]}"; do

echo "Initial list: ${balls[@]}"

balls=($(dutch "${balls[@]}"))

{{out}}

=={{header|VBScript}}==

'Solution derived from http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/.

WScript.StdOut.Write "Sorted: " & sort(unsort)

WScript.StdOut.WriteLine

{{Out}}

=={{header|Visual FoxPro}}==

===SQL Version===

CLOSE DATABASES ALL

LOCAL lcCollate As String, i As Integer, n As Integer

RETURN INT(3*RAND()) + 1

ENDFUNC

===Array Version===

LOCAL i As Integer, n As Integer, colours As String, k As Integer

colours = "Red,White,Blue"

RETURN INT(3*RAND()) + 1

ENDFUNC

=={{header|Wren}}==

{{libheader|Wren-sort}}

import "/sort" for Sort

System.print("Before sorting : %(balls)")

Sort.insertion(balls, colorCmp)

{{out}}

=={{header|zkl}}==

fcn colorBalls(balls){ balls.apply(T("red","white","blue").get).concat(", "); }

}while(balls==sortedBalls); // make sure sort does something

println("Original ball order:\n", colorBalls(balls));

{{out}}

<pre>

=={{header|ZX Spectrum Basic}}==

{{trans|Run_BASIC}}

20 LET c$="RWB"

30 DIM b(10)

120 IF b(j)=i THEN PRINT VAL$ (c$(i)+"$");" ";

130 NEXT j