Hi, - Thanks in advance for any help.
I am new to lisp, and have been spending all day debugging this small number
sorting program with only minor success. I would use the sort function, but
this is an assignment for school, so I am writing a simple bubblesort type
thing - just to sort numbers.
The sorting actually works, but it crashes after it is done and does not
return anything. I hope to an experienced lisp programmer that my error
will be obvious.
Here is the code. First is a simple swap function. Then the sortme
function.
(defun swap (L p1 p2)
(rotatef (elt L p1) (elt L p2))
L)
(defun sortem (L) ;define the
function
((setq i 0) ;set
the big iterator to 0
(while (< i (- (length L) 2)) ;while number
of times through whole list
(setq ii 0) ;set
the small iterator to 0
(while (< ii (- (length L) 1)) ;while
number of items in list
(if (> (nth ii L) (nth (+ ii 1) L)) ;if item 1
is bigger than item 2,
(swap L ii (+ ii 1)) ;swap
them
)
;else do nothing
(setq ii (+ ii 1)))
;increment small counter
(setq i (+ i 1))))
;increment big counter
L
;return the list
)
It seems to have a problem with the line (setq i 0) as I have to reset this
each time I run it, or else the sort will not happen. If I do a (setq i 0)
and (setq ii 0) before I run the (sortem a) command, it sorts, but returns
with an error. But even if I pull out those lines it still crashes.
Here is the eror I get after setting i and ii before running the function.
It sorted the list fine and here is what it said:
[1] CG-USER(166): a
(2 8 3 9 4 7 5 6)
[1] CG-USER(167): i
7
[1] CG-USER(168): ii
7
[1] CG-USER(169): (setq i 0)
0
[1] CG-USER(170): (setq ii 0)
0
[1] CG-USER(171): (sortem a)
1[1]: (SORTEM (2 8 3 9 4 7 5 6))
Error: Illegal function object: (SETQ I 0).
[condition type: PROGRAM-ERROR]
1[1]: returned-by-throwing :POP 0
[1] CG-USER(172): a
(2 3 4 5 6 7 8 9)
Any ideas?
Thanks for your help!
Shane
"Shane" <················@zaft.com> writes:
> Hi, - Thanks in advance for any help.
>
> I am new to lisp, and have been spending all day debugging this small number
> sorting program with only minor success. I would use the sort function, but
> this is an assignment for school, so I am writing a simple bubblesort type
> thing - just to sort numbers.
>
> The sorting actually works, but it crashes after it is done and does not
> return anything. I hope to an experienced lisp programmer that my error
> will be obvious.
>
> Here is the code. First is a simple swap function. Then the sortme
> function.
>
>
> (defun swap (L p1 p2)
> (rotatef (elt L p1) (elt L p2))
> L)
>
> (defun sortem (L) ;define the function
> ((setq i 0) ;set the big iterator to 0
> (while (< i (- (length L) 2)) ;while number of times through whole list
> (setq ii 0) ;set the small iterator to 0
> (while (< ii (- (length L) 1)) ;while number of items in list
> (if (> (nth ii L) (nth (+ ii 1) L)) ;if item 1 is bigger than item 2,
> (swap L ii (+ ii 1)) ;swap them
> ) ;else do nothing
> (setq ii (+ ii 1))) ;increment small counter
> (setq i (+ i 1))));increment big counter
> L ;return the list
> )
In addition to jan's comments, you have to take care of the data
structures you're using and choose matching operations.
If you really want to sort lists, use CAR and CDR, not NTH.
If you want to use NTH (or rather ELT), use arrays.
So, assuming you really want to implement bubble-sort:
(defun nbubble-sort (list-of-num)
(do ((head list-of-num (cdr head)))
((null head) list-of-num)
(do ((tail (cdr head) (cdr tail)))
((null tail))
(when (> (car head) (car tail))
(rotatef (car head) (car tail))))))
NBUBBLE-SORT
(let ((x (copy-seq '(5 3 4 2 1 6))))
(nbubble-sort x)
(print x))
(1 2 3 4 5 6)
Otherwise, of course it's much better to use the quick-sort algorithm
on an array. Note that you can easily convert between list and arrays,
with map or coerce:
(defun quick-sort-list (list-of-number)
(map 'list (function identity)
(quick-sort-array
(map 'vector (function identity) list-of-number))))
(defun quick-sort-list (list-of-number)
(coerce (quick-sort-array (coerce list-of-number 'vector)) 'list))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
Pascal Bourguignon <····@mouse-potato.com> wrote
> So, assuming you really want to implement bubble-sort:
That's not bubble sort, is it? In a bubble sort, you would repeatedly
compare FIRST and SECOND elements (and conditionally swap) in
progressive sublists until no swaps occur during a pass. Your code
looks more like a selection sort except you could possibly swap
multiple times to the same location.
Just to be loopy, this also implements your algorithm:
(defun n-not-bubble-sort (list-of-num)
(loop for head on list-of-num
while head
do (loop for tail on (rest head)
while tail
when (> (first head) (first tail))
do (rotatef (first head) (first tail)))
finally return list-of-num))
and this, I think, is a bubble sort:
(defun nbubble-sort2 (list-of-num)
(let ((sorted nil))
(loop until sorted
do (setf sorted t)
do (loop for list on list-of-num
while (second list)
when (> (first list) (second list))
do (progn
(setf sorted nil)
(rotatef (first list) (second list))))
finally return list-of-num)))
and so is this:
(defun nbubble-sort3 (list-of-num)
(let ((sorted nil))
(do ()
(sorted list-of-num)
(setf sorted t)
(do ((list list-of-num (rest list)))
((null (second list)))
(when (> (first list) (second list))
(setf sorted nil)
(rotatef (first list) (second list)))))))
> Otherwise, of course it's much better to use the quick-sort algorithm
> on an array.
Yep.
·············@swipnet.se (Peter Lewerin) writes:
> Pascal Bourguignon <····@mouse-potato.com> wrote
>
> > So, assuming you really want to implement bubble-sort:
>
> That's not bubble sort, is it? In a bubble sort, you would repeatedly
> compare FIRST and SECOND elements (and conditionally swap) in
> progressive sublists until no swaps occur during a pass. Your code
> looks more like a selection sort except you could possibly swap
> multiple times to the same location.
You're right, sorry for the confusion. (Actually, bubblesort is better
when the items are already almost sorted).
http://www.nist.gov/dads/HTML/bubblesort.html
http://www.nist.gov/dads/HTML/selectionsrt.html
> and this, I think, is a bubble sort:
>
> (defun nbubble-sort2 (list-of-num)
> (let ((sorted nil))
> (loop until sorted
> do (setf sorted t)
> do (loop for list on list-of-num
> while (second list)
> when (> (first list) (second list))
> do (progn
> (setf sorted nil)
> (rotatef (first list) (second list))))
> finally return list-of-num)))
>
> and so is this:
>
> (defun nbubble-sort3 (list-of-num)
> (let ((sorted nil))
> (do ()
> (sorted list-of-num)
> (setf sorted t)
> (do ((list list-of-num (rest list)))
> ((null (second list)))
> (when (> (first list) (second list))
> (setf sorted nil)
> (rotatef (first list) (second list)))))))
>
> > Otherwise, of course it's much better to use the quick-sort algorithm
> > on an array.
>
> Yep.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
"Shane" <················@zaft.com> writes:
> (defun sortem (L) ;define the function
> ((setq i 0) ;set the big iterator to 0
> (while (< i (- (length L) 2)) ;while number of times through whole list
> (setq ii 0) ;set the small iterator to 0
> (while (< ii (- (length L) 1)) ;while number of items in list
> (if (> (nth ii L) (nth (+ ii 1) L)) ;if item 1 is bigger than item 2,
> (swap L ii (+ ii 1)) ;swap them
> ) ;else do nothing
> (setq ii (+ ii 1))) ;increment small counter
> (setq i (+ i 1))));increment big counter
> L ;return the list
> )
> [1] CG-USER(171): (sortem a)
> 1[1]: (SORTEM (2 8 3 9 4 7 5 6))
> Error: Illegal function object: (SETQ I 0).
> [condition type: PROGRAM-ERROR]
> 1[1]: returned-by-throwing :POP 0
You have an extra open parenthesis before the first setq, the compiler
is trying to call (setq i 0) as a function.
A few tips:
- use a lisp aware editor, eg. emacs.
- your comments are completely redundant, use comments for things that
can't be expressed in code.
- don't use capitals in names, L is the same as l, especially bad
considering all the i's and 1's in your function.
- use meaningful names, eg. list inner outer.
- introduce variables with `let' rather than `setq'.
- which dialect are you using? Common Lisp doesn't have a while
operater (although the loop macro has a while clause you could use).
- be specific, use `when' rather than `if' when there is no else form.
- use `incf' to increment.
- don't leave closing parenthesis hanging on their own line.
--
jan