Hello.
I'm implementing (in a newbie fashion to learn Lisp) the sorting
algorithms
you can find in "The Art of Computer Programming", volume 3, by D.
Knuth.
I'm posting the implementation of the two counting sort algorithms.
For a newbie as me I found very useful to play with let, let*, loop,
progn and vectors.
Thanks for your comments,
Alberto Santini
;;; DOCUMENTATION
;;; The code is the implementation of the algorithms contained
;;; in The Art of Computer Programming (TAOCP) for integer numbers.
;;;
;;; ROADMAP
;;; a- implement the algorithm
;;; b- create unit tests: check the sorting, test with zeroes and neg
values
;;; c- comment the code (and write the documentation)
;;; d- review the style
;;; e- profile the code
;;; f- optimize the algorithm
;;; g- extend implementation for other type of objects (using macros?)
;;; h- integrate the framework with cl-muproc to distribute the
computing
;;; counting sort by comparison
(defun counting-sort-by-comparison (vec)
"Counting sort by comparison as TAOCP, vol. 3, page 76"
(let ((counting (make-array (length vec)))
(sorted-vec (make-array (length vec))))
(loop for i from (1- (length vec)) downto 1 do
(loop for j from (1- i) downto 0 do
(if (< (svref vec j) (svref vec i))
(incf (svref counting i))
(incf (svref counting j))))
finally (return counting))
(loop for i from 0 to (1- (length counting)) do
(setf (svref sorted-vec (svref counting i)) (svref vec i))
finally (return sorted-vec))))
;;; counting sort by distribution
(defun counting-sort-by-distribution (vec)
"Counting sort by distribution as TAOCP, vol. 3, page 78"
(let* ((min (reduce #'min vec))
(max (reduce #'max vec))
(counting (make-array (+ max 1 (abs min))))
(sorted-vec (make-array (length vec))))
(loop for i from 0 to (1- (length vec)) do
(progn
(setf (svref vec i) (+ (svref vec i) (abs min)))
(incf (svref counting (svref vec i)))))
(loop for i from 1 to (1- (length counting)) do
(incf (svref counting i) (svref counting (1- i))))
(loop for i from (1- (length vec)) downto 0 do
(progn
(setf (svref sorted-vec (1- (svref counting (svref vec i))))
(- (svref vec i) (abs min)))
(setf (svref counting (svref vec i))
(1- (svref counting (svref vec i)))))
finally (return sorted-vec))))
(counting-sort-by-distribution #(10 7 0 1 8 0 7 2 -1 -12))
(defparameter *test-vec*
#(503 87 512 61 908 170 897 275 653 426 154 509 612 677 765 703))
(counting-sort-by-comparison *test-vec*)
(counting-sort-by-distribution *test-vec*)
Thanks Pascal for the comments.
Pascal Bourguignon wrote:
> (defun counting-sort-by-comparison (vec)
> "Counting sort by comparison as TAOCP, vol. 3, page 76
> VEC: A vector of REAL numbers.
> RETURN: A new vector of same length as vec containing the same elements as vec,
> ordered in increasing order. vec is not modified."
> (assert (and (vectorp VEC) (every (function realp) vec)))
> (let ((counting (make-array (length vec)))
> (sorted-vec (make-array (length vec))))
> (loop for i from (1- (length vec)) downto 1 do
> (loop for j from (1- i) downto 0 do
> (incf (svref counting (max (aref vec i) (aref vec j))))))
I think this line is not correct for
(if (< (svref vec j) (svref vec i))
(incf (svref counting i))
(incf (svref counting j)))
>
> There are at least two obvious bugs:
>
> [6]> (counting-sort-by-distribution (vector -10 -7 -8 -12))
>
> *** - +: NIL is not a number
I have not this bug with OpenMCL 1.1-pre-060705.
>
>
> And there's something not obvious that should be clearly written in
> the documentation string (instead of a useless comment above the
> function): this function _destructs_ the input vector, so we cannot
> call it with a literal vector like:
>
> (counting-sort-by-distribution #(-10 -7 -8 -12))
>
This a great insight.
I will try to modify that and to use a not destructive approach.
>
> (defun counting-sort-by-distribution (vec)
> "Counting sort by distribution as TAOCP, vol. 3, page 78
> VEC: A vector of REAL numbers.
> WARNING: Destruct VEC during the processing, it must be a mutable vector.
> RETURN: A new vector of same length as vec containing the same elements as vec,
> ordered in increasing order. vec is not modified."
> (assert (and (vectorp VEC) (every (function realp) vec)))
> (let* ((min (reduce (function min) vec))
> (max (reduce (function max) vec))
> (counting (make-array (- max min -1) :initial-element 0
> :element-type 'integer))
> (sorted-vec (make-array (length vec) :element-type 'real)))
> (loop
> :for i :from 0 :below (length vec)
> :do (decf (svref vec i) min)
> (assert (<= 0 (svref vec i) (- max min -1)))
> (incf (svref counting (svref vec i))))
> (loop
> :for i :from 1 :below (length counting)
> :do (incf (svref counting i) (svref counting (1- i)))
> (assert (not (minusp (svref counting i)))))
> (loop
> :for i :from (1- (length vec)) :downto 0
> :do (setf (svref sorted-vec (decf (svref counting (svref vec i))))
> (+ (svref vec i) min)))
> (assert (and (vectorp sorted-vec)
> (= (length sorted-vec) (length vec))
> (every (function <=) sorted-vec (subseq sorted-vec 1))))
> sorted-vec))
What is the difference between "for" and ":for"?
Alberto Santini
"Alberto Santini" <··············@gmail.com> writes:
> Thanks Pascal for the comments.
>
> Pascal Bourguignon wrote:
>
>> (defun counting-sort-by-comparison (vec)
>> "Counting sort by comparison as TAOCP, vol. 3, page 76
>> VEC: A vector of REAL numbers.
>> RETURN: A new vector of same length as vec containing the same elements as vec,
>> ordered in increasing order. vec is not modified."
>> (assert (and (vectorp VEC) (every (function realp) vec)))
>> (let ((counting (make-array (length vec)))
>> (sorted-vec (make-array (length vec))))
>> (loop for i from (1- (length vec)) downto 1 do
>> (loop for j from (1- i) downto 0 do
>> (incf (svref counting (max (aref vec i) (aref vec j))))))
>
> I think this line is not correct for
>
> (if (< (svref vec j) (svref vec i))
> (incf (svref counting i))
> (incf (svref counting j)))
Right, I went too far. Sorry.
>> There are at least two obvious bugs:
>>
>> [6]> (counting-sort-by-distribution (vector -10 -7 -8 -12))
>>
>> *** - +: NIL is not a number
>
> I have not this bug with OpenMCL 1.1-pre-060705.
Yes, this is because the actual value used to initialize the slots of
a new array is implementation dependant. Some implementations use 0,
some NIL, some whatever else.
> [...]
> What is the difference between "for" and ":for"?
Not much. It only matters if you happen to import a symbol named
"FOR" from another package later on. You can ignore it for now.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.