Dutch national flag problem: Difference between revisions

* [https://www.google.co.uk/search?rlz=1C1DSGK_enGB472GB472&sugexp=chrome,mod=8&sourceid=chrome&ie=UTF-8&q=Dutch+national+flag+problem#hl=en&rlz=1C1DSGK_enGB472GB472&sclient=psy-ab&q=Probabilistic+analysis+of+algorithms+for+the+Dutch+national+flag+problem&oq=Probabilistic+analysis+of+algorithms+for+the+Dutch+national+flag+problem&gs_l=serp.3...60754.61818.1.62736.1.1.0.0.0.0.72.72.1.1.0...0.0.Pw3RGungndU&psj=1&bav=on.2,or.r_gc.r_pw.r_cp.r_qf.,cf.osb&fp=c33d18147f5082cc&biw=1395&bih=951 Probabilistic analysis of algorithms for the Dutch national flag problem] by Wei-Mei Chen. (pdf)

<br><br>

 

=={{header|ABAP}}==

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

 

RRRRRRRRWWWWWWWBBBBB, is sorted? -> X

</pre>

 

=={{header|Ada}}==

 

 

procedure Dutch_National_Flag is

 

Print("After Sorting: ", A);

 

{{out}}

After Sorting: WHITE, WHITE, WHITE, WHITE, BLUE, BLUE, BLUE</pre>

 

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

 

 

DOTIMES 16

PRINT "Unsorted: ", ball$

 

{{out}}

<pre>

</pre>

 

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

Non-sorted: rbwww

Sorted: rwwwb</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|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]

The sequence [Red; Red; White; White; White; White; White; Blue; Blue; Blue] is sorted: true</pre>

 

=={{header|Forth}}==

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>

Is sorted: true

</pre>

 

 

 

=={{header|Julia}}==

 

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

<pre>Start list: white blue red red red white blue red red white

Sorted: red red red red red white white white blue blue</pre>

 

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

{{out}}

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

 

{RED, RED, WHITE, WHITE, WHITE, WHITE, WHITE, WHITE, BLUE, BLUE, BLUE, BLUE}</pre>

 

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

 

{{out}}

 

 

 

 

 

 

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

==> OK

</pre>

 

=={{header|REXX}}==

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>

 

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

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

# ''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|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>

red red red red red red red white white white white white white white white white blue blue blue blue

</pre>

 

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