From cbmvax!uunet!CUVMA.BITNET!LOJBAN Tue Dec 10 16:29:25 1991
Return-Path: <cbmvax!uunet!CUVMA.BITNET!LOJBAN>
Date: Tue Dec 10 16:29:25 1991
Message-Id: <9112102044.AA00541@relay1.UU.NET>
Reply-To: John Cowan <cbmvax!UUNET.UU.NET!snark.thyrsus.com!cowan>
Sender: Lojban list <cbmvax!uunet!CUVMA.BITNET!pucc.PRINCETON.EDU!LOJBAN>
From: John Cowan <cbmvax!UUNET.UU.NET!snark.thyrsus.com!cowan>
Subject:      Quicksort in Lojban!
X-To:         lojmail@snark.thyrsus.com,
              Lojban List <lojban@cuvmb.cc.columbia.edu>
To: John Cowan <cowan@SNARK.THYRSUS.COM>,
        Eric Raymond <eric@SNARK.THYRSUS.COM>,
        Eric Tiedemann <est@SNARK.THYRSUS.COM>
Status: RO

The following algorithm, expressed in Lojban, describes how to sort a list of
numbers (or anything comparable with "zmadu" and "mleca") into least-first order
using Hoare's quicksort algorithm.  It is a direct translation of a Prolog
equivalent, except that the arguments have been re-ordered to bring results
to the beginning, in conformity with Lojbanic conventions.

ni'o
        roda zo'u
                da poirmi'a la nil. da
        .i roda rode rodi rodixire zo'u
                de ce'o dixire poirmi'a de ce'o di da
ni'o
        .i roda rodaxipa rodaxire rode rodi zo'u
                de ce'o daxipa daxire skamrpartiti de di ce'o da
                .ijanai de mleca di
                        .ijebo daxipa daxire skamrpartiti di da
        .i roda rodaxipa rodaxire rode rodi zo'u
                daxipa de ce'o daxire skamrpartiti de di ce'o da
                .ijanai de zmadu di
                        .ijebo daxipa daxire skamrpartiti di da
        .i roda zo'u
                la nil. la nil. skamrpartiti da la nil.
ni'o
        la nil. poirja'e la nil.
        .i roda rodaxipa rodaxire rode rodexipa rodexire rodi zo'u
                de poirja'e di ce'o da
                .ijanai daxipa daxire skamrpartiti di da
                        .ijebo dexipa poirja'e daxipa
                        .ijebo dexire poirja'e daxire
                        .ijebo de poirmi'a dexipa di ce'o dexire

pau li ci ce'o li pa ce'o li vo ce'o li pa ce'o li mu poirmi'a ma

li ci ce'o li pa ce'o li vo ce'o li pa ce'o li mu poirmi'a
        li pa ce'o li pa ce'o li ci ce'o li vo ce'o li mu

---

Place structures:

        poirmi'a:  x1 is the result of appending x2 to x3
        skamrpartiti:  x1 and x2 are a partition on pivot x3 of list x4
        poirja'e:  x1 is the result of ordering x2

la nil. is the name of the null list.

--
cowan@snark.thyrsus.com         ...!uunet!cbmvax!snark!cowan
                e'osai ko sarji la lojban