Anonymous user
Sorting algorithms/Bubble sort: Difference between revisions
efficient CL implementation for vectors and lists
(→Common Lisp: whitespace (parens; don't assume tabs=8); "from 0" unnecessary; use 1+, 1-; while not -> until) |
(efficient CL implementation for vectors and lists) |
||
Line 357:
<lang lisp>(bubble-sort (list 5 4 3 2 1))</lang>
<code>elt</code> has linear access time for lists, making the prior implementation of bubble-sort very expensive (although very clear, and straightforward to code. Here is an implementation that works efficiently for both vectors and lists. For lists it also has the nice property that the input list and the sorted list begin with the same <code>cons</code> cell.
<lang lisp>(defun bubble-sort-vector (vector predicate &aux (len (1- (length vector))))
(do ((swapped t)) ((not swapped) vector)
(setf swapped nil)
(do ((i (min 0 len) (1+ i))) ((eql i len))
(when (funcall predicate (aref vector (1+ i)) (aref vector i))
(rotatef (aref vector i) (aref vector (1+ i)))
(setf swapped t)))))
(defun bubble-sort-list (list predicate)
(do ((swapped t)) ((not swapped) list)
(setf swapped nil)
(do ((list list (rest list))) ((endp (rest list)))
(when (funcall predicate (second list) (first list))
(rotatef (first list) (second list))
(setf swapped t)))))
(defun bubble-sort (sequence predicate)
(etypecase sequence
(list (bubble-sort-list sequence predicate))
(vector (bubble-sort-vector sequence predicate))))</lang>
=={{header|D}}==
| |||