Merge-Sort

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Merge-Sort

Beitrag von 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?
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Merge-Sort

Beitrag von 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)

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Merge-Sort

Beitrag von 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 ;)

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Merge-Sort

Beitrag von 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!
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Merge-Sort

Beitrag von 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
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Merge-Sort

Beitrag von 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

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Merge-Sort

Beitrag von Krümelmonster »

Das merge von Merge-sort hat mir heute sehr weitergeholfen ;)
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Merge-Sort

Beitrag von s!mon »

Und beim Codeverständis kam Extract vor :P

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Merge-Sort

Beitrag von Krümelmonster »

Stimmt, das sogar auch.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Antworten

Zurück zu „Archiv“