LISP中的Quicksort [英] Quicksort in LISP

问题描述

我正在尝试使用LISP进行快速排序，但是我的函数输出遇到了麻烦.

I am trying to do a quicksort using LISP but I am having trouble with my functions output.

(defun qsort (L)
   (cond
   ((null L) nil)
   (t(append
      (qsort (list< (car L) (cdr L)))
      (cons (car L) nil)
      (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
    (cond
    (( or(null a)(null b) nil))
    (( < a (car b)) (list< a (cdr b)))
    (t(cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
    (cond
    (( or( null a)(null b) nil))
    (( >= a (car b)) (list> a (cdr b)))
    (t(cons (car b) (list> a (cdr b))))))   

我的问题是当 list< 和 list> = 完成列表时，总是以.T结尾.例如:

My problem being when list< and list>= finish the list always ends with a .T. For instance:

> (list< '4 '(1 5 3 8 2))
Entering: LIST<, Argument list: (4 (1 5 3 8 2))
 Entering: LIST<, Argument list: (4 (5 3 8 2))
  Entering: LIST<, Argument list: (4 (3 8 2))
   Entering: LIST<, Argument list: (4 (8 2))
    Entering: LIST<, Argument list: (4 (2))
     Entering: LIST<, Argument list: (4 NIL)
     Exiting: LIST<, Value: T
    Exiting: LIST<, Value: (2 . T)
   Exiting: LIST<, Value: (2 . T)
  Exiting: LIST<, Value: (3 2 . T)
 Exiting: LIST<, Value: (3 2 . T)
Exiting: LIST<, Value: (1 3 2 . T)
(1 3 2 . T)

为什么(4 NIL)评估为T?

推荐答案

list<和list>=的问题都在((or ( null a)(null b) nil))上，应该是(( or( null a)(null b)) nil).注意nil已移至条件之外，成为返回值.

Your problem with list<, and also with list>=, lies on ((or ( null a)(null b) nil)), it should be (( or( null a)(null b)) nil). Note nil was moved outside of the condition to be the returned value.

此外，在list>=的定义中，您正在调用list>，但我很肯定是用list>=代替.

Furthermore, on the definition of list>= you are calling list>, but I'm positive you meant list>= instead.

我还建议使用

I would also suggest some indentation to address the legibility of lisp, like follows

(defun qsort (L)
  (cond
    ((null L) nil)
    (t
      (append
        (qsort (list< (car L) (cdr L)))
        (cons (car L) nil) 
        (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
  (cond
    ((or (null a) (null b)) nil)
    ((< a (car b)) (list< a (cdr b)))
    (t (cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
  (cond
    ((or (null a) (null b)) nil)
    ((>= a (car b)) (list>= a (cdr b)))
    (t (cons (car b) (list>= a (cdr b))))))

一些测试如下:

(list< '4 '(1 5 3 8 2))
=> (1 3 2)

(list>= '4 '(1 5 3 8 2))
=> (5 8)

(qsort '(1 5 3 8 2))
=> (1 2 3 5 8)

这篇关于LISP中的Quicksort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！