Can I implement quicksort efficiently with Scheme?

Question

This is what I've done:

(define qsort
  (lambda (l)
    (let ((lesser '()))
      (let ((greater '()))
        (cond
          ((null? l) '())
          (else (map (lambda (ele)
                       (if (> (car l) ele)
                           (set! lesser (cons ele lesser))
                           (set! greater (cons ele greater)))) (cdr l))
                (append (qsort lesser) (cons (car l) (qsort greater))))
        )))))

I noticed that when provided with an already sorted list, it becomes extremely sluggish. After some searching, I found that if the "pivot" is selected in a random manner, the performance can be improved. However the only way I know to achieve this is by list-ref, and it seems to be O(n). To make matters even worse, I have to implement a cdr-like function to remove n-th element in the list, which might also be extremely inefficient.

Maybe I'm in the wrong direction. Could you give me some advice?

Answer 1

true quicksort runs on random-access arrays, with in-place partitioning. e.g. see this.

you can start by converting your list to vector with list->vector, then implementing the quicksort by partitioning the vector with mutating swaps, in C fashion.

Randomizing it is easy: just pick a position randomly, and swap its contents with the first element in range being sorted, before each partition step. When you're done, convert it back with vector->list.

Efficient implementation of quicksort may run without recursion, in a loop, maintaining a stack of bigger parts boundaries, always descending on the smaller ones (then, when at the bottom, switching to the first part in the stack). Three-way partitioning is always preferable, dealing with equals in one blow.

Your list-based algorithm is actually an unraveled treesort.

see also:

• http://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell
• Pseudo-quicksort time complexity

Answer 2

Although there's already an accepted answer, I thought you might appreciate a Scheme translation of the Sheep Trick from The Pitmanual. Your code is actually quite similar to it already. Scheme does support do loops, but they're not particularly idiomatic, whereas named lets are much more common, so I've used the latter in this code. As you've noted, choosing the first element as the pivot cause perfomance problems if the list is already sorted. Since you have to traverse the list on each iteration, there might be some clever thing you could do to pick the pivots for the left and right sides for the recursive calls in advance.

(define (nconc l1 l2)
  ;; Destructively concatenate l1 and l2. If l1 is empty,
  ;; return l2.  Otherwise, set the cdr of the last pair
  ;; of l1 to l2 and return l1. 
  (cond
    ((null? l1)
     l2)
    (else 
     (let loop ((l1 l1))
        (if (null? (cdr l1))
            (set-cdr! l1 l2)
            (loop (cdr l1))))
     l1)))

(define (quicksort lst)
  (if (null? lst) lst
      (let ((pivot (car lst))
            (left '())
            (right '()))
        (let loop ((lst (cdr lst))) ; rebind to (cdr lst) since pivot wasn't popped
          (if (null? lst)
              (nconc (quicksort left)
                     (cons pivot
                           (quicksort right)))
              (let ((tail (cdr lst)))
                (cond
                  ((< (car lst) pivot)
                   (set-cdr! lst left)
                   (set! left lst))
                  (else
                   (set-cdr! lst right)
                   (set! right lst)))
                (loop tail)))))))

(quicksort (list 9 1 8 2 7 3 6 4 5))
;=> (1 2 3 4 5 6 7 8 9)

Scheme does support do, so if you are interested in that (it does make the Common Lisp and Scheme version very similar), it looks like this:

(define (quicksort lst)
  (if (null? lst) lst
      (do ((pivot (car lst))
           (lst (cdr lst))   ; bind lst to (cdr lst) since pivot wasn't popped
           (left '())
           (right '()))
        ((null? lst)
         (nconc (quicksort left)
                (cons pivot
                      (quicksort right))))
        (let ((tail (cdr lst)))
          (cond
            ((< (car lst) pivot)
             (set-cdr! lst left)
             (set! left lst))
            (else
             (set-cdr! lst right)
             (set! right lst)))
          (set! lst tail)))))

(display (quicksort (list 9 1 8 2 7 3 6 4 5)))
;=> (1 2 3 4 5 6 7 8 9)

Answer 3

A truly efficient implementation of Quicksort should be in-place and implemented using a data structure that can be accessed efficiently by index - and that makes immutable linked lists a poor choice.

The question asks whether Quicksort can be efficiently implemented with Scheme - the answer is yes, as long as you don't use lists. Switch to using a vector, which is mutable and has O(1) index-based access over its elements, like an array in C-like programming languages.

If your input data comes in a linked list, you can always do something like this, it'll probably be faster than directly sorting the list:

(define (list-quicksort lst)
  (vector->list
   (vector-quicksort ; ToDo: implement this procedure
    (list->vector lst))))