Schwierigkeit LISP rekursive Funktion für Merge Sort

Question

Hallo Schreiben so Frage, die ich habe, dass ich einige Schwierigkeiten habe und MERGE LISTEN eine rekursive Lisp Funktion msort zu definieren, so dass, wenn L ist eine Liste von reellen Zahlen, dann (MSORT L) ist eine Liste, die aus den Elementen von L in aufsteigender Reihenfolge besteht. In der Definition von MSORT können Sie SPLIT-LIST, , MSORT selbst, MERGE-LISTS, CAR, CDR, CADR und ENDP aufrufen, aber Sie sollten keine andere andere Funktion aufrufen. Achten Sie darauf, LET oder LET * zu verwenden, damit MSORT SPLIT-LIST nur einmal aufruft.

Bis jetzt konnte ich die Funktionen SPLIT-LIST und MERGE-LISTS korrekt schreiben, aber für M-SORT habe ich Probleme beim Schreiben der Funktion. Siehe unten alle drei Definitionen bis jetzt. Jede Hilfe zum korrekten Schreiben der MSORT-Funktion durch Befolgen der Richtlinien in der Frage wäre willkommen.

(defun SPLIT-LIST (L) 
    (if (endp L) 
     '(nil nil) 
    (let ((X (split-list (cdr L)))) 
     (list (cons (car L)(cadr X)) (car X))))) 

(defun MERGE-LISTS (L1 L2) 
    (cond 
    ((and(endp L1)(endp L2)) nil) 
    ((endp L1) (cons (CAR L2) (MERGE-LISTS nil (CDR L2)))) 
    ((endp L2) (cons (CAR L1) (MERGE-LISTS (CDR L1) NIL))) 
    ((< (CAR L1) (CAR L2)) (cons (CAR L1) (MERGE-LISTS (CDR L1) L2 ))) 
    ((>= (CAR L1) (CAR L2)) (cons (CAR L2) (MERGE-LISTS L1 (CDR L2)) )))) 

(defun MSORT (L) 
    (cond ((endp L) nil) 
     ((equal (Length L) 1) L) 
     (T 
     (let* (
       (S (SPLIT-LIST L)) 
       (L1 (CAR S)) 
       (L2 (CADR S)) 
       (X (MSORT (cdr L1))) 
       (Y (MSORT (cdr L2))) 


       ) 
      (MERGE-LISTS 
      (if (and (numberp (car L1)) (numberp (car X))(<= (car L1) (car X))) 
       (list (car L1) (car X)) 
       (list (car X) (car L1)) 
      ) 

      (Cons (car L2) Y)) 

      ))) 
) 

Answer 1

Sie verkomplizieren es. Sie müssen die s der Unterlisten, die von SPLIT-LIST zurückgegeben werden, nicht sortieren, sondern nur die ganzen Listen sortieren und zusammenführen.

(defun MSORT (L) 
    (cond ((endp L) nil) 
     ((endp (cdr L)) L) 
     (t 
     (let* ((S (SPLIT-LIST L)) 
       (L1 (car S)) 
       (L2 (cadr S)) 
       (X (MSORT L1)) 
       (Y (MSORT L2))) 
      (MERGE-LISTS X Y)))))