次のクイックソートを実装する必要があります: (quick-sort pred lst) lst はソートされる数値のリストです pred はリストの順序付けに使用される述語です。この述語の署名は次のとおりです: (lambda (xy) …)
ここのコードは機能していますが、ここでの問題は、同じ番号を何度も取得すると、無限ループに陥り、何時間ものデバッグの後、問題や解決方法を見つけることができないということです。
(define (quick-sort pred lst)
;Pivot is 1st element of the list
(define (pivot lst)
(if (or (null? lst) (= 1 (length lst)))
'done
(car lst)))
partition get the pivot the list and the predicate and splitting it to two lists
(define (partition piv lst pred)
;predPos is the pred it slef and predNeg is the negative of the pred
(let* ((predPos (lambda (x) (pred x piv) ))
(predNeg (lambda (x) (if (pred x piv) #f #t)))
;Filtering the big list in to two lists
(p1 (filter predPos lst))
(p2 (filter predNeg lst)))
;Recursivly doing the qucicksort on each list. and joining them together.
(cond ((and (null? p1) (null? p2)) (cons piv ()))
((null? p1) (quick-sort pred p2))
((null? p2) (quick-sort pred p1))
(else (joiner (quick-sort pred p1) (quick-sort pred p2))))))
;Joining 2 lists together
(define (joiner p1 p2)
(cond ((null? p1) p2)
((null? p2) p1)
(else (cons (car p1) (joiner (cdr p1) p2)))))
;The main quicksort method () and list size one are sorted!
(let ((piv (pivot lst)))
(if (or (null? lst) (= 1 (length lst)))
lst
(partition piv lst pred))))