0

我需要实现以下快速排序： (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))))
4

1 回答 1

0

如果您在分区之前删除了枢轴，则可以保证在每个递归步骤中都取得进展。如果没有这种措施，枢轴将粘在其分区的前面，您将无处可去。

于 2013-10-31T11:03:35.733 回答