Merge-Sort

[Krümelmonster]

Folie: T6-25
Die Funktion extract scheint es nicht vorgefertigt zu geben.

Ich habe mir daher die Funktionsweise erraten, aber es werden einige Elemente der Liste vergessen.

Code: Alles auswählen

;; MERGE SORT
(define (merge-sort alon)
  (local (
          (define (extract alon left right)
            (local (
                    (define (extract-accu alon accu position)
                      (cond
                        [(= position right) accu]
                        [(< position left) (extract-accu (rest alon) accu (add1 position))]
                        [else (extract-accu (rest alon) (cons (first alon) accu) (add1 position))])))
              (extract-accu alon empty 0)))
          (define (merge alon1 alon2)
            (cond
              [(null? alon1) alon2]
              [(null? alon2) alon1]
              [(< (first alon1) (first alon2))
               (cons (first alon1)
                     (merge (rest alon1) alon2))]
              [else (cons (first alon2)
                          (merge alon1 (rest alon2)))]))
          (define (merge-step left right)
            (cond
              [(>= left right) alon]
              [else
               (local (
                       (define mid (floor (/ (+ left right) 2)))
                       (define left-list (merge-sort (extract alon left mid)))
                       (define right-list (merge-sort (extract alon (add1 mid) right))))
                 (merge left-list right-list))])))
    (merge-step 1 (length alon))))

(define lst (build-list 10 (lambda(n) (random 1000))))
lst
(merge-sort lst)

Die Ausgabe ist:

Code: Alles auswählen

(list 459 946 872 715 256 410 339 344 296 70)
(list 296 339 715 946)

In der sortierten Liste erscheinen immer nur die Elemente mit den Positionen:
2, 4, 7 und 9. (Von 1 an gezählt)

Findet jemand den Fehler?

[s!mon]

Code: Alles auswählen

(define alon '(a b c d e))

(define mid (floor (/ (+ 1 5) 2)))

(extract alon 1 mid)
(extract alon (add1 mid) 5)

ergibt

(list 'c 'b)
(list 'e)

Du vergisst also beim extract immer dein erstes Listenelement (bzw weil du die "falsch" rum dran klebst das letzte)

[s!mon]

Code: Alles auswählen

(define (extract alon left right)
            (local (
                    (define (extract-accu alon position)
                      (cond
                        [(> position right) empty]
                        [(< position left) (extract-accu (rest alon) (add1 position))]
                        [else (cons (first alon) (extract-accu (rest alon) (add1 position)))])))
              (extract-accu alon 1)))

So hätte ich das gemacht, ohne Test obs funktioniert.

edit: scheint zu funktionieren

[Krümelmonster]

Funktioniert.
Da ich die Liste noch umgedreht hatte, habe ich auch den Akkumulator gebraucht.

So sieht der korrekte Code aus:

Code: Alles auswählen

;; MERGE SORT
(define (merge-sort alon)
  (local (
          (define (extract alon left right)
            (local (
                    (define (extract-accu alon position)
                      (cond
                        [(> position right) empty]
                        [(< position left) (extract-accu (rest alon) (add1 position))]
                        [else (cons (first alon) (extract-accu (rest alon) (add1 position)))])))
              (extract-accu alon 1)))
          (define (merge alon1 alon2)
            (cond
              [(null? alon1) alon2]
              [(null? alon2) alon1]
              [(< (first alon1) (first alon2))
               (cons (first alon1)
                     (merge (rest alon1) alon2))]
              [else (cons (first alon2)
                          (merge alon1 (rest alon2)))]))
          (define (merge-step left right)
            (cond
              [(>= left right) alon]
              [else
               (local (
                       (define mid (floor (/ (+ left right) 2)))
                       (define left-list (merge-sort (extract alon left mid)))
                       (define right-list (merge-sort (extract alon (add1 mid) right))))
                 (merge left-list right-list))])))
    (merge-step 1 (length alon))))

Danke!

[Krümelmonster]

Also quick-sort gefällt mir.
Habe mal einen Vergleich der drei Sortieralgorithmen insertion-sort, quick-sort und merge-sort erstellt.

Evtl. liegt merge-sort deshalb weiter hinten, da er durch die Indizierungen besser für Arrays geeignet ist, da sie Zugriff auf die Elemente in konstanter Zeit erstatten.

Code: Alles auswählen

;; INSERTION SORT
(define (sort alon)
  (local (
          (define (insert n alon)
            (cond
              [(empty? alon) (cons n empty)]
              [(< (first alon) n) (cons (first alon) (insert n (rest alon)))]
              [else (cons n alon)])))
    (cond
      [(empty? alon) empty]
      [else (insert (first alon) (sort (rest alon)))])))

;; QUICK SORT
(define (quick-sort alon)
  (cond
    [(empty? alon) empty]
    [else (append
           (quick-sort (filter (lambda(n) (<= n (first alon))) (rest alon)))
           (list (first alon))
           (quick-sort (filter (lambda(n) (> n (first alon))) (rest alon))))]))

;; MERGE SORT
(define (merge-sort alon)
  (local (
          (define (extract alon left right)
            (local (
                    (define (extract-accu alon position)
                      (cond
                        [(> position right) empty]
                        [(< position left) (extract-accu (rest alon) (add1 position))]
                        [else (cons (first alon) (extract-accu (rest alon) (add1 position)))])))
              (extract-accu alon 1)))
          (define (merge alon1 alon2)
            (cond
              [(null? alon1) alon2]
              [(null? alon2) alon1]
              [(< (first alon1) (first alon2))
               (cons (first alon1)
                     (merge (rest alon1) alon2))]
              [else (cons (first alon2)
                          (merge alon1 (rest alon2)))]))
          (define (merge-step left right)
            (cond
              [(>= left right) alon]
              [else
               (local (
                       (define mid (floor (/ (+ left right) 2)))
                       (define left-list (merge-sort (extract alon left mid)))
                       (define right-list (merge-sort (extract alon (add1 mid) right))))
                 (merge left-list right-list))])))
    (merge-step 1 (length alon))))

(define lst (build-list 10000 (lambda(n) (random 1000))))
(time (begin (merge-sort lst) 0))
(time (begin (sort lst) 0))
(time (begin (quick-sort lst) 0))

Ausgabe:

Code: Alles auswählen

cpu time: 2373 real time: 2434 gc time: 56
0
cpu time: 140284 real time: 148622 gc time: 500
0
cpu time: 472 real time: 656 gc time: 28
0

[s!mon]

Joa ich denk mal das liegt an dem extract das einfach nicht sehr effektiv ist. Außerdem steht ja auch im Skript, dass quick-sort oft schneller ist als andere n*logn Algorithmen.

bin pennen.. ciao

[Krümelmonster]

Das merge von Merge-sort hat mir heute sehr weitergeholfen

[s!mon]

Und beim Codeverständis kam Extract vor

[Krümelmonster]

Stimmt, das sogar auch.