On 29/08/2013, Sean B. Durkin <sean(_at_)seanbdurkin(_dot_)id(_dot_)au> wrote:
Hi Roger,
You can perform a quick sort in XPath 3 of strings with this expression ...
function( $s as xs:string, $sort-2 as function(xs:string, function()) as
xs:string*
{ if (count($s) lt 2 then $s
else $sort-2( $s[. lt $s[1]]) , $s[1] , $sort-2( $s[( . ge $s[1])
and (position() ne 1))}
A functional implementation of quicksort is bound to lose, more or
less, as compared to the procedural in-place algorithm as proposed by
Hoare. The division of a sequence by comparison to the pivot element
appears to require O(2n) comparisons, and there are 2O(log n)
constructions of sequences for passing the sequences to the function
and for combining the results of the calls. Memory consumption may
also be substantially higher as this is no longer in-place. Certainly,
shuffling just references will keep this within reasonable limits, and
the overall complexity should still be O(n.log n).
Given the same data, an XSLT implementation of sort could be
considerably better than any hand-written algorithm: it isn't bound by
paradigm.
-W
The same technique can be applied to any other atomic data type. To use
a different collation, supply a comparison function as an additional
argument.
For example this xpath expression ....
let $quick-sort := function( $s as xs:string, $sort-2 as
function(xs:string, function()) as xs:string*
{ if (count($s) lt 2 then $s
else $sort-2( $s[. lt $s[1]]) , $s[1] , $sort-2( $s[( . ge $s[1])
and (position() ne 1))}
return $quick-sort( ('def', 'abc', 'ghi'), $quick=sort())
should return ('abc','def','ghi') . This is untested
You can't sort a map, as your question suggestion. That doesn't make any
sense, because a map is just a single item. You can't sort the map's
internal store of item, because maps are by definition an unsorted list
of associations between a key and a value. But you can sort the
print-out of a map's keys.
For example: This function prints out the contents of a map in
alphabetical order of the keys. Is that better than non-deterministic
order? It probably is if the output is intended for human readership.
<xsl:function name="f:print-map" as="xs:string*">
<xsl:param name="m" as="map(xs:anyAtomicType, item()*)" />
<xsl:value-of select="
let $quick-sort := function( $s as xs:string, $sort-2 as
function(xs:string, function()) as xs:string*
{ if (count($s) lt 2 then $s
else $sort-2( $s[. lt $s[1]]) , $s[1] , $sort-2( $s[( . ge $s[1]) and
(position() ne 1))}
return $quick-sort( map:keys($m), $quick=sort()) ! (., '-',
map:get($m, .))"/>
</xsl:function>
I don't have any facility to test this, except the XPath processor of my
imagination. So there is probably some errors. Even so, the technique is
will still be valid.
In XPath 2, you could also sort, but it was painful. I am not sure that
XPath sort will ever be popular. I suspect that most developers will
prefer the direct simplicity of XSLT sort. I don't know. It remains to
be seen.
Faithfully,
Sean B. Durkin
For example to sort
On 29/08/2013 7:51 PM, Costello, Roger L. wrote:
Sean Durkin wrote:
XPath 3 can now implement QuickSort in 3 lines of code.
Sean (or anyone) would you show how to implement the QuickSort please?
That is, would you replace the ??? in the below function with the code
please?
---------------------------------------------------------------------
<xsl:function name="f:sort-map" as="map(xs:anyAtomicType, item()*)">
<xsl:param name="m" as="map(xs:anyAtomicType, item()*)" />
???
</xsl:function>
---------------------------------------------------------------------
/Roger
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--