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