Re: [xsl] How to QuickSort a map?

[Wolfgang Laun <wolfgang.laun@xxxxxxxxx>]

On 29/08/2013, Sean B. Durkin <sean@xxxxxxxxxxxxxxxxx> 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