Вставка сортируется на месте LISP - PullRequest
Новая
       34

Вставка сортируется на месте LISP

0 голосов
/ 15 сентября 2018

Я все еще довольно новичок в правильном Лиспе и пытаюсь создать простую, но хотя бы немного эффективную сортировку вставок - я бы хотел поменять элементы на месте, но у меня все еще есть возможность добавлять в мой контейнер после этого. Я взял мою старую реализацию 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))

UPD: обновлен код, основанный на комментариях @jkiiski и @RainerJoswig, вывод по-прежнему неправильный.

1 Ответ

0 голосов
/ 15 сентября 2018

В вашей программе есть несколько проблем.

Во-первых, сортировка не работает, так как строка: 

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.

Если вы хотитепараметризовать предикат сортировки, а также добавить в функцию необязательный ключевой параметр «ключ», вот возможное решение: 

(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))
...