Scheme: Implementing a Quick-Sort

Question

I'm trying to implement a quick sort using scheme, some dudes here already helped me fixing my split function and now I'm asking for you help with combining everything into one working algorithm.

Here is my code so far:

(define quick-sort (lambda (lst)

                 (define pivot (lambda (lst)
                                 (if (null? lst)
                                     null
                                     (car lst))))
                 (define split (lambda (lst pivot)
                                 (define lst1 null)
                                 (define lst2 null)
                                 (define split-helper (lambda (lst pivot lst1 lst2)
                                                        (if (null? lst)
                                                            (list lst1 lst2)
                                                            (if (<= (car lst) pivot)
                                                                (split-helper (cdr lst) pivot (cons (car lst) lst1) lst2)
                                                                (split-helper (cdr lst) pivot lst1 (cons (car lst) lst2))))))
                                 (split-helper lst pivot lst1 lst2)))

                 (if (null? lst)
                            null
                            (append (quick-sort (car (split lst (pivot lst)))) (quick-sort (cdr (split lst (pivot lst))))))))

As you can see, I'm choosing the pivot to simply be the first element in the list, the problem I'm facing is that the program ran into an infinite loop when the pivot is the smallest element in the list because it makes the program choose the same pivot over and over.

Also, the way it's currently implemented makes it be really un-efficient because the split function is called twice with the same lst in every ineration of quick-sort but I just don't have good enough control over Scheme to write it any other way.

I saw some posts about Quick-Sort in Scheme but they were implemented a bit different and I rather try and correct my own implementation than copying some other dude's work.

Thank you.

user6428287 · Accepted Answer

Removed excessive lambdas, aliases, bindings, and reformatted, but didn't change or annotate semantics (Sylwester already pointed out the bug):

(define (quick-sort lst)
   (define (pivot lst)
      (if (null? lst)
         '()
         (car lst) ))
   (define (split lst pivot)
      (let split-helper ((lst lst)         ; Named let instead of internal
                         (lst1 '())        ; definition
                         (lst2 '()) )
         (if (null? lst)
            (cons lst1 list2)
            (if (<= (car lst) pivot)
               (split-helper (cdr lst)
                             (cons (car lst) lst1)
                             lst2)
               (split-helper (cdr lst)
                             lst1
                             (cons (car lst) lst2) )))))
   (if (null? lst)
      '()
      (let ((spl (split lst (pivot lst)))) ; Memoization of the `split`
         (append (quick-sort (car spl))
                 (quick-sort (cdr spl)) ))))

I think you're trying to implement a partition:

(define (partition pred xs)
   (let part ((ps '()) (ns '()) ; Initial "positives" `ps`, and "negatives" `ns`
              (xs' xs) )
      (if (null? xs')
         (cons ps ns)             ; Returning pair of lists
         (let ((x (car xs')))     ; Memoization of `(car lst)`
            (if (pred x)
               (part (cons x ps) ns (cdr xs'))
               (part ps (cons x ns) (cdr xs')) )))))

(define (quicksort xs)
   (if (null? xs) '()
      (let* ((x (car xs))
             (pn (partition               ; Memoization of `partition`
                    (lambda (x')
                       (< x' x) )
                    (cdr xs) )))
         (append (quicksort (car pn))      ; Extracting positives from pair
                 (list x)                  ; Pivot
                 (quicksort (cdr pn)) )))) ; Negatives


(display
   (quicksort (list 4 2 3 5 1)) )    ; (1 2 3 4 5)

part is inefficient in strict languages like Scheme; it copies all three of its arguments for every recursive step. Often, straightforward formulations in terms of basic folds like filter and map are most efficient. A much more efficient implementation using filter:

(define (quicksort xs)
   (if (null? xs) '()
      (let ((x (car xs))
            (xs' (cdr xs)) )
         (append (quicksort
                    (filter (lambda (x')
                               (< x' x) )
                            xs'))
                 (list x)
                 (quicksort
                    (filter (lambda (x')
                               (>= x' x) )
                            xs'))))))

This strategy famously happens to be very briefly expressible in functional languages.

In lazy Haskell, a single-traversal partition is actually more efficient than filtering twice.

select :: (a -> Bool) -> ([a], [a]) -> a -> ([a], [a])
select pred (ps, ns) x | pred x    = (x : ps, ns)
                       | otherwise = (ps, x : ns)

partition :: (a -> Bool) -> [a] -> ([a], [a])
partition pred  =  foldl (select pred) ([], [])

quicksort :: Ord a => [a] -> [a]
quicksort []       = []
quicksort (x : xs) = let (lt, gt) = partition (< x) xs
                     in  quicksort lt ++ [x] ++ quicksort gt

Scheme: Implementing a Quick-Sort

Answers (2)

Related Questions