//
//------------------ DOK FILE --------------------------------------------------
+Header	core.util.quicksort
=pkg	core.util.quicksort
=title	core.util.quicksort
=short	the classical quicksort algorithm
=desc
The quicksort algorithm is provided with two variants:
-	[[quicksort]]: sort the elements and keep duplicated values
-	[[quicksortFusion]]: sort the element and eliminate the duplicated values

	fun makeRandomList (n, res)= if n==0 then res else makeRandomList( n-1, intRand()::res);;
	
	fun quicksortTest (n)=
		let makeRandomList (n, nil) -> src in
		(
			// the following function calls sort the list from the lowest to the highest
			echoLn quicksortFusion (src, lambda (a, b)= a-b);// this one remove the duplicated values
			echoLn quicksort (src, lambda (a, b)= a<b);// this one will always keep all the values
		);;

The simple [[quicksort]] is included in the Bios.
//
//
//------------------ PROTO ----------------------------------------------------- quicksortFusion
+Proto	quicksortFusion
=type	fun list a1 (fun a1 a1 -> Int) -> list a1
=mode	function
=pkg	core.util.quicksort
=impl	mcy
=link	
=desc
This function applies the quicksort algorithm to the list src, removing identical values, and using the lambda function fCompare to compare elements.
The fCompare function is called with two arguments a and b, and returns:
-	a negative value when a is before b
-	a positive value when a is after b
-	zero when a is b, then the algorithm keeps only one value
	> quicksortFusion ("foo"::"bar"::"hello"::"bar"::"world"::nil, #strCmp)
>-> list Str:
>   Str: "bar"
>   Str: "foo"
>   Str: "hello"
>   Str: "world"

	> quicksortFusion (3::2::3::5::2::4::nil, lambda (a, b)= a-b)
>-> list Int:
>   Int: 2 (0x2)
>   Int: 3 (0x3)
>   Int: 4 (0x4)
>   Int: 5 (0x5)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	fCompare
=type	fun a1 a1 -> Int
=desc	A lambda function which compares two elements and returns an integer
//
+arg	result
=type	list a1
=desc	The ordered list
//
//