[racket] Partion

From: Jens Axel Søgaard (jensaxel at soegaard.net)
Date: Fri Mar 16 15:49:36 EDT 2012

Hi All,

I am looking for a list based algorithm, that solves this problem:

Input:    A list xs of numbers.
Output: Two lists of numbers ys and zs whose
             lengths differ at most by one, and:

                for all y in yz and z in zs:    y<=z

A simple solution using sort is

     (split-at (sort xs <) (half (length xs))

but using sort must be inefficient.

Another try (that doesn't work):

    (let ([m (median xs)])
        (partition (λ (x) (<= x m)) xs))

To see the bug here,  try   xs = (1 2 2 2 2 2 2).
Since the median in this case is 2, partion will return
two values, one is xs and one is the empty list.

Jens Axel Søgaard

Posted on the users mailing list.