0

クイックソートを実装する私の試みは次のとおりです。

(define (sublist ls start stop middle)
 (cond ( (null? ls) ls)
     ( (< middle start) (sublist (cdr ls) start stop (+ middle 1)))
     ( (> middle stop) '() )
     (else
        (cons (car ls) (sublist (cdr ls) start stop (+ middle 1))))))

(define (split5 ls)                                      
  (let ((len (length ls)))
   (cond ((= len 0) (list ls ls) )
         ((= len 1) (list ls '() ))
         (else 
          (list (sublist ls 1 (/ len 2) 1)
                (sublist ls (+(/ len 2)1) len 1))))))

;this divides the sorted list into two sublists 
(define (dividelist rel? ls)
 (split5 (order rel? ls)))


(define (quicksort rel? ls)
 (if (null? (cdr ls)) ls
  (let ((pivot (list-ref (sort rel? ls) (round (/ (length (sort rel? ls)) 2))))
        (left (car (dividelist rel? ls)))
        (right (cdr (dividelist rel? ls))))
        (join left pivot right))))

この実装が非常に非効率的であることはわかっていますが、それを行う方法が思いつきません。とにかく、それは本当にうまくいきません。

When I input this:
(quicksort < '(9 3 -5 8 -7 2 9))
It gives me this:
(-7 -5 2 8 (8 9 9))
It should give me this:
(-7 -5 2 3 8 9 9)

どうすればこれを修正できますか?

編集

(define (join ls1 goo ls2)
  (if (null? ls1) (cons goo ls2)
      (if (null? ls2) (cons goo ls1)
          (cons (car ls1) (join (cdr ls1) goo ls2)))))
4

1 に答える 1

1

手順がコードの数行下で使用さorderれている手順と同じであると仮定すると(待ってください、並べ替え手順を実装するために並べ替え手順を使用していますか?!)、それはある種の です。リストの作成は問題は の実装にあります。これを修正するには、次のように変更します。sortjoinappendjoin

(define (join left pivot right)
  (append* left (list pivot) right))

これで、プロシージャは次のようにlistを返します。

(quicksort < '(9 3 -5 8 -7 2 9))
=> '(-7 -5 2 8 8 9 9)

おっと、番号はどこに行ったの3ですか？コードにバグがあります。見つける必要があります。ヒント: ピボットを計算するコードはひどく間違っています。

編集

これは、QuickSort の正確で手間のかからない実装です。このような単純な実装では、最初の要素をピボットとして選択するだけで十分であることに注意してください。

(define (quicksort cmp lst)
  (if (null? lst)
      '()
      (let ((x  (car lst))
            (xs (cdr lst)))
        (append (quicksort cmp (filter (lambda (e) (cmp e x)) xs))
                (list x)
                (quicksort cmp (filter (lambda (e) (not (cmp e x))) xs))))))

または、Racket の高次の手順を使用して、少し凝った短いものにします。

(define (quicksort cmp lst)
  (if (empty? lst)
      empty
      (let ((x  (first lst))
            (xs (rest  lst)))
        (append (quicksort cmp (filter-not (curry cmp x) xs))
                (cons x (quicksort cmp (filter (curry cmp x) xs)))))))

さらに別の可能性としてpartition、単一のステップで両方のパーティション (ピボットの前の要素とピボットの後の要素) を取得するために使用すると、より効率的です。

(define (quicksort cmp lst)
  (if (empty? lst)
      empty
      (let-values (((greater-than less-equal)
                    (partition (curry cmp (first lst)) (rest lst))))
        (append (quicksort cmp less-equal)
                (cons (first lst) (quicksort cmp greater-than))))))

とにかく、期待どおりに動作します：

(quicksort < '(9 3 -5 8 -7 2 9))
=> '(-7 -5 2 3 8 9 9)
于 2013-04-01T22:03:51.140 に答える