So, I figured a fun little waste of time would be to write quicksort in scheme. I have my code below, poorly documented. Basically, it takes the first element as the pivot (for simplicity), and then there's a method which returns a pair which is ( (list of everything smaller than pivot) . (list of everything else)), and then lists ( (sorted car of above list) pivot (sorted cdr) )
(define (quicksort L) (if (null? L) L (letrec ((pivot (car L)) ;chooses first element as pivot (split (lambda (piv li return) ;return is the list to be returned ;return will be (<pivot . >=pivot) (cond ((null? li) return) ((< (car li) piv) (split piv (cdr li) (cons (cons (car li) (car return)) (cdr return)))) (else (split piv (cdr li) (cons (car return) (cons (car li) (cdr return))))))) )) `(,@(quicksort (car (split pivot (cdr L) '(() . ())))) ,pivot ,@(quicksort (cdr (split pivot (cdr L) '(() . ()))))) ) ) )
Anyway, my questions:
Is there another simple of choosing the pivot that doesn't require O(n^2) time to "sort" a sorted list?
Does my code actually calculate (split pivot ... ) twice? How can I rewrite this to be a little cleaner?