就地插入排序 LISP

Question

我对正确的 Lisp 还是很陌生，我正在尝试构建一个简单但至少有点高效的插入排序 - 我想就地切换元素，但仍然能够追加到之后我的容器。我采用了旧的 C++ 实现：

template<typename Iter>
void insertionSort(Iter begin, Iter end){
    for (auto i = begin; i != end; ++i){
        for (auto j = i; j != begin && *(std::prev(j)) > *(j); j--){
            std::iter_swap(j, std::prev(j));
        }
    }
}

并创建了以下代码（考虑到 aref 和 rotatef 具有相当的复杂性），但它似乎对输入没有任何影响（UPD：现在它可以正常工作不当），我的解决方案可能有什么问题？我回来进行测试，我是否应该创建一个宏以避免按值传递？

(defparameter testa (make-array 4 :initial-contents '(2 3 1 5)))
(defun insertion-sort (vect)
    (loop for i from 0 to (1- (length vect)) do
        (loop for j from i downto 0
            until (or (= (1- j) -1) (> (aref vect (1- j)) (aref vect j)))
            do (rotatef (aref vect i) (aref vect (1- j))))
    )
    vect
)
(format t "~a~%" (insertion-sort testa))

更新：根据@jkiiski 和@RainerJoswig 的评论更新了代码，输出仍然是错误的。

Answer 1

你的程序有几个问题。

首先，排序不起作用，因为行：

do (rotatef (aref vect i) (aref vect (1- j))))

应该是：

do (rotatef (aref vect j) (aref vect (1- j))))

也就是说，你写了变量i而不是j

如果您进行此更正，您会发现订单正在减少（我假设您想要增加订单）。这取决于使用 until 而不是 while.

终于有冗余代码了。更简单有效的版本如下：

(defparameter testa (make-array 4 :initial-contents '(2 3 1 5)))
(defun insertion-sort (vect)
   (loop for i from 1 below (length vect) 
     do (loop for j from i above 0
          while (> (aref vect (1- j)) (aref vect j))
          do (rotatef (aref vect j) (aref vect (1- j)))))
   vect)
(format t "~a~%" (insertion-sort testa))

这与 Insertion sort 的维基百科页面中的伪代码相似。

如果你想参数化排序谓词，以及向函数添加一个可选的基于关键字的“key”参数，这是一个可能的解决方案：

(defun insertion-sort (vect predicate &key (key #'identity))
  (loop for i from 1 below (length vect) 
        do (loop for j from i above 0
                 while (funcall predicate 
                                (funcall key (aref vect (1- j)))
                                (funcall key (aref vect j)))
                 do (rotatef (aref vect j) (aref vect (1- j)))))
         vect)

CL-USER> (insertion-sort testa #'>)
#(1 2 3 5)
CL-USER> (insertion-sort testa #'<)
#(5 3 2 1)

CL-USER> (defparameter testa (make-array 4 :initial-contents '((c 3) (d 2) (b 1) (a 4))))
TESTA
CL-USER> (insertion-sort testa #'string> :key #'car)
#((A 4) (B 1) (C 3) (D 2))

就地插入排序 LISP

Insertion sort in place LISP

lisp

sorting

algorithm

common-lisp

insertion-sort