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 に答える