Quicksort (XProc)
From LiteratePrograms
- Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc
Quicksort is a simple sorting algorithm that works by choosing a certain element, called the pivot, and then dividing the list into two parts, those less than the pivot and those greater than or equal to the pivot. Each list is then recursively sorted. For arrays on typical modern architectures, it is one of the fastest sorting algorithms available.
<<quicksort.xpl>>= <p:declare-step xmlns:p="http://www.w3.org/ns/xproc" xmlns:c="http://www.w3.org/ns/xproc-step" xmlns:ix="http://www.innovimax.fr/ns" version="1.0"> <p:input port="source"> <p:inline exclude-inline-prefixes="#all"> <root> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> </root> </p:inline> </p:input> <p:output port="result"/> <p:declare-step type="ix:sort" name="sort"> <p:documentation> <p>XProc QuickSort implementation</p> <p>Copyright (C) 2010 Mohamed ZERGAOUI Innovimax</p> <p>This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.</p> <p>This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.</p> <p>You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.</p> </p:documentation> <p:input port="source" sequence="true"/> <p:output port="result" sequence="true"/> <p:option name="key" required="true"/> <p:count limit="2"/> <p:choose> <p:when test="number(.) le 1"> <p:identity> <p:input port="source"> <p:pipe port="source" step="sort"/> </p:input> </p:identity> </p:when> <p:otherwise> <p:split-sequence test="position() = 1" name="split"> <p:input port="source"> <p:pipe port="source" step="sort"/> </p:input> </p:split-sequence> <p:filter name="filter"> <p:with-option name="select" select="$key"> <p:empty/> </p:with-option> </p:filter> <p:group> <p:variable name="pivot-key" select="."> <p:pipe port="result" step="filter"/> </p:variable> <p:split-sequence name="split-pivot"> <p:input port="source"> <p:pipe port="not-matched" step="split"/> </p:input> <p:with-option name="test" select="concat($key, ' <= ', $pivot-key)"/> </p:split-sequence> <ix:sort name="less"> <p:with-option name="key" select="$key"> <p:empty/> </p:with-option> <p:input port="source"> <p:pipe port="matched" step="split-pivot"/> </p:input> </ix:sort> <ix:sort name="greater"> <p:with-option name="key" select="$key"> <p:empty/> </p:with-option> <p:input port="source"> <p:pipe port="not-matched" step="split-pivot"/> </p:input> </ix:sort> <p:identity> <p:input port="source"> <p:pipe port="result" step="less"/> <p:pipe port="matched" step="split"/> <p:pipe port="result" step="greater"/> </p:input> </p:identity> </p:group> </p:otherwise> </p:choose> </p:declare-step> <p:for-each> <p:iteration-source select="/root/doc"/> <p:identity/> </p:for-each> <ix:sort key="/doc"/> <p:wrap-sequence wrapper="root"/> </p:declare-step>
Download code |