Quicksort in Scheme using a partition

Question

I have a partition for a quicksort:

(define (partition pivot lst)
  ((lambda (s) (s s lst list))
   (lambda (s l* c)
     (if (null? l*)
         (c '() '())
         (let ((x (car l*)))
           (s s (cdr l*)
              (lambda (a b)
                (if (< x pivot)
                    (c (cons x a) b)
                    (c a (cons x b))))))))))

partition code source

Testing:

 =>(partition '5 '(1 3 5 7 9 8 6 4 2))
;Value: ((1 3 4 2) (5 7 9 8 6))

How can I implement this partition in a quicksort? I've tried this so far:

(define (quicksort lst)
  (if (null? lst) '()
    (let* ((y (car lst))
           (pn (partition y (cdr lst))))
      (append (quicksort (car pn))      
              (list y)                  
              (quicksort (cdr pn))))))

Answer 1

First, your code is trivially fixed by changing one cdr to cadr:

(define (partition pivot lst)
  ((lambda (s) (s s lst list))
   ......))           ; ^^^^  `list` the top continuation

(define (quicksort lst)
  (if (null? lst) '()
    (let* ((y (car lst))
           (pn (partition y (cdr lst))))
      (append 
        (quicksort (car pn))      
        (list y)                  
        (quicksort (cadr pn))))))
               ;;   ^^^^  cdr --> cadr

because the top continuation used in partition is list, and so the call

  (partition pivot lst)

is equivalent to the call

  (list { x IN lst SUCH THAT x < pivot }
        { x IN lst SUCH THAT x >= pivot } )

(the parts in {...} are pseudocode, where we don't care about the implementation, just the results)

And so to access the two parts of that list built by partition you need to use car and cadr.

Or you could keep the cdr in the accessing part of your code in quicksort if you'd change that top continuation to cons:

(define (partition pivot lst)
  ((lambda (s) (s s lst cons))
   ......))           ; ^^^^  `cons` the top continuation

(define (quicksort lst)
  (if (null? lst) 
    '()
    (let* ((y (car lst))
           (pn (partition y (cdr lst))))
      (append 
        (quicksort (car pn))      
        (list y)                  
        (quicksort (cdr pn))))))
               ;;   ^^^^  `cdr` works fine with `cons`

This because of the general principle in programming, where the functions used to build our data dictate which functions are to be used to access that data:

    (list   <A>   <B>  )
            car   cadr

    (cons   <A>   <B>  )
            car   cdr

( this particular correspondence is because (list <A> <B>) is the same as (cons <A> (cons <B> '())) and (cadr <C>) is the same as (car (cdr <C>)): )

    (list  <A>         <B>     )
 =
    (cons  <A>   (cons <B> '()))
           car   cdr
                       car

And conversely, the functions we use to access our data dictate the implementation of the function which must be used to build that data.

Of course that way of coding in your question is considered unnecessarily convoluted by modern standards since it emulates recursion through argument passing and reuse, -- just like in the famous Y combinator, -- but any Scheme worthy of its name already supports recursion.

So this partition would normally be written as the fully equivalent yet more readable code using the "named let" construct,

(define (partition pivot lst)
  (let s ( (l*   lst)      ; first `l*` is `lst`
           (c    cons) )   ; top   `c`  is `cons`
     (if (null? l*)
         (c '() '())
         (let ((x (car l*)))
           (s (cdr l*)
              (lambda (a b)
                (if (< x pivot)
                    (c  (cons x a)  b)
                    (c  a   (cons x b)))))))))

except the name loop is conventionally used in place of s here (which itself most probably is intended as the shortening of "self").

But the true trouble with your quicksort/partition pair is algorithmic.

Yes I say pair (in non-cons sense of course) since the two go together -- just as with the data access/creation functions which must work together too.

Implementation of one dictates the implementation of the other -- in both directions, too. partition's code dictates quicksort's, or if we'd written quicksort first, we'd need to implement the partition in the corresponding way -- so that the two work together. Which means quicksort indeed producing the correct results, turning any input list into a sorted one:

(quicksort lst) --->  

      { xs SUCH THAT
             FOR ANY splitting xs = { ..., x, ...ys }
             AND ANY splitting ys = { ..., y, ...   }
             IT HOLDS THAT x <= y
           AND ALSO xs is a permutation of lst 
             (which implies (length lst) == (length xs))
      }

So then, what is that trouble? It is that the true quicksort does no work whatsoever after the partitioning. None:

(define (quicksort! lst)
  (if (null? lst) 
    '()
    (let* ((y (car lst))
           (pn (partition! y lst)))
      (quicksort! (car pn))         ; no `append`, NB!
      (quicksort! (cdr pn)))))      ; no (list y) either

How is that even possible? What kind of partition! implementation would make that work? Well, most certainly not a functional one.

Instead it must be changing (i.e. mutating) the very lst itself somehow:

     { a, b, c, ....., k, l, m, ..... }
   -->
     { d, e, ....,   p,   n, o, ..... }  
       ~~~~~~~~~~~        ~~~~~~~~~~~

where we denote with p the partition point -- so that indeed all that's left to do after this kind of partitioning "in-place" is to sort the first part, and then to sort the second part, -- and then there's nothing more left to be done, after that! Which was the key insight in the original Tony Hoare's formulation of it:

  TO SORT
     { a, b, c, ....., k, l, m, ..... }  DO:
  PARTITION it into
     { d, e, ....,   p,   n, o, ..... }  AND THEN:
       ~~~~~~~~~~~        ~~~~~~~~~~~
        SORT!               SORT!
                 DONE.

This partitioning is usually implemented with swap! which actually swaps two elements in the underlying data structure. Most usually that data structure is an array with its facilities to change the value stored in it at any given index.

But it can also be a list, where the change i.e. mutation can be done with the set-car! primitive.

Looks like we'd need to build a list of cdrs out of the input list, and another one in reverse, -- to be able to iterate over them in both directions, back and forth, -- to make that happen.

I'll leave that for another day, for now.

Answer 2

Once you have the partition, there is still a small step to do.

Take care, you need to be sure partition splits the input in smaller sets all the time. In other word, partition not to return some empty set. The pivot can go in any of the sets and use this fact to check that you do not return an empty set, in case your comparison operator does not really decrease the size of the input. This is why I inserted the equality operator -- to be able to check if I insert the pivot in the first returned set or in the second one.

(define (partition pivot lst ret)
  ((lambda (s)
     (s s lst
        (lambda (a b p*)
          (if (and (null? a) (null? b))
              (ret (list pivot) (cdr p*))
              (if (null? a)
                  (ret p* b)
                  (if (null? b)
                      (ret a p*)
                      (if (< (car b) pivot)
                          (ret a (append p* b))
                          (if (< (car a) pivot)
                              (ret (append a p*) b)
                              (error "never here")))))))))
   (lambda (s l* c)
     (if (null? l*)
         (c '() '() '())
         (let ((x (car l*)))
           (s s (cdr l*)
              (lambda (a b p*)
                (if (= x pivot)
                    (c a b (cons pivot p*))
                    (if (< x pivot)
                        (c (cons x a) b p*)
                        (c a (cons x b) p*))))))))))

    
(define choose-pivot car)

In a real implementation, you will all the time use vectors and this is why the append will not be present, as, sorting on the place, at the end of partition, both sides will be sorted relatively one to the other. Here, we need to reassemble the 2 sides using append:

(define (quicksort lst)
  (if (null? lst) '()
      (if (null? (cdr lst))
          lst
          (let* ((pivot (choose-pivot lst)))
            (partition pivot lst
                       (lambda (p< p>)
                         (append
                           (quicksort p<)
                           (quicksort p>))))))))

A test:

1 ]=> (quicksort '(1 3 5 7 9 8 6 4 2))
;Value: (1 2 3 4 5 6 7 8 9)

1 ]=> (quicksort '(1 9 3 8 5 7 7 6 9 5 8 4 6 3 4 2 2 1))
;Value: (1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9)

I used as pivot the first element of the input to split, but you can redefine the choose-pivot to select other element.

In practice, this algorithm is used in combination with other sorts -- when the input has fewer than 4-8 elements, the quicksort is not recurred any more, but other sorting is used for the lowest cases of recurrence relation.

I used directly < in the code -- you can insert it as a parameter in case you prefer a more generic procedure... In any case, the operator that you use needs to simulate the equality and different of in the same time.

UPDATE I have updated the partition, such that to consider duplicated elements. In my first version, it ignored duplicated elements.