title: modifying quicksort in lisp to use an intermediate valuator filter
body: <p>I'm working on implementing quicksort that uses an intermediate valuator function;  not a test function, but a valuator which substitutes the indirect values the numbers otherwise represent in another context.</p>
  
  <p>I'm having some trouble getting it to work in all cases and feel like I've hit a brick wall.  My main intention for this is sorting 3D triangles in a set by distance from camera (the array being one of indices to unique faces, and the valuator function does a lookup up of the mesh face of the given index and then returns the distance from camera), but for the sake of brevity I will use a much simpler example below.  Here is the quicksort-* code in Common Lisp:</p>
  
  <pre><code>(defun quicksort-* (arr lo hi &amp;key (valuator #'identity))
    (declare (type (simple-array fixnum (*)) arr)
             (type fixnum lo hi)
             (type function valuator))
    (flet ((%partition (arr p r)
             (declare (type (simple-array fixnum (*)) arr)
                      (type fixnum p r))
             (let ((x (funcall valuator (aref arr p)))
                   (i (1- p))
                   (j (1+ r)))
               (loop do
                     (loop do
                           (decf j)
                           until (&lt;= (funcall valuator (aref arr j)) x))
                     (loop do
                           (incf i)
                           until (&gt;= (funcall valuator (aref arr i)) x))
                     (if (&lt; i j)
                         (rotatef (aref arr i) (aref arr j))
                       (return-from %partition j))))))
      (when (&lt; lo hi)
        (let ((p (%partition arr lo hi)))
          (quicksort arr lo p)
          (quicksort arr (1+ p) hi))))
    arr)
  </code></pre>
  
  <p>So what exactly would this do?</p>
  
  <p>Given</p>
  
  <pre><code>(defparameter *names* #("Earl" "Dudley" "Chuck" "Bob" "Alice"))
  </code></pre>
  
  <p>and a list we want sorted, currently randomly scrambled as</p>
  
  <pre><code>(defparameter *nameindices* '(2 4 0 1 3))
  </code></pre>
  
  <p>Running quicksort-* on <em>nameindices</em> with a predicate function 'namevaluator':</p>
  
  <pre><code>(defun namevaluator (nameindex)
     (let ((sortednames (sort (copy-seq *names*) #'string&gt;)))
        (position (aref *names* nameindex) sortednames :test #'string=)))
  </code></pre>
  
  <p>as such should yield #(4 3 2 1 0) to reflect the descendingly-sorted names, right?</p>
  
  <pre><code>CL-USER&gt; (quicksort
             *nameindices*
              0 (1- (length *nameindices*))
              :valuator
              #'namevaluator)
  #(0 1 2 3 4)
  </code></pre>
  
  <p>Hmm, nope.  But hey, at least it's still sorted, even if in reverse.</p>
  
  <p>Well, certainly, changing #'string> to #'string&lt; in the namevaluator function should yield #(4 3 2 1 0) then, right?  Well... no, this becomes the answer:</p>
  
  <pre><code>#(1 2 3 4 0)
  </code></pre>
  
  <p>Flipping the >= and &lt;= signs around in the %partition function doesn't yield any better (and that's probably not too hot an idea anyway);  it still results in a case of one result being sorted, and the other being out-of-sequence.</p>
  
  <p>I figured plugging in a funcall-predicate test in %partition where it originally simply evaluated the plain integer values for comparisons would have simply 'Just Worked'.  Indeed, with the default #'IDENTITY function as the valuator, it does:</p>
  
  <pre><code>(let ((random-numbers (coerce (loop repeat 30 collect (random 1000)) 'vector)))
     (quicksort-* random-numbers 0 (1- (length random-numbers))))
  
  &gt; #(29 91 121 130 191 228 250 382 392 406 443 468 468 480 535 555 576 597 598 604 635 646 646 685 712 721 724 764 849 860)
  </code></pre>
  
  <p>Maybe the answer is right under my nose but I'm just not seeing it?</p>