### Author Topic: Sort list of numbers (vl-sort not allowed)  (Read 19778 times)

0 Members and 1 Guest are viewing this topic. ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #15 on: May 15, 2011, 09:25:44 AM »
A vl-sort equivalent which requires a list and a predicate function as arguments (it uses the merge sort algotihm and is optimised for speed performance).

Code: [Select]
`(defun gc:sort (lst fun / merge tmp)  (defun merge (l1 l2)    (cond      ((null l1) l2)      ((null l2) l1)      ((fun (car l1) (car l2)) (cons (car l1) (merge (cdr l1) l2)))      (T (cons (car l2) (merge l1 (cdr l2))))    )  )  (setq fun (eval fun) lst (mapcar 'list lst)  )  (while (cdr lst)    (setq tmp lst   lst nil    )    (while (cdr tmp)      (setq lst (cons (merge (car tmp) (cadr tmp)) lst)     tmp (cddr tmp)      )    )    (and tmp (setq lst (cons (car tmp) lst)))  )  (car lst))`
Speaking English as a French Frog ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #16 on: May 15, 2011, 04:52:29 PM »
Gile,

I've got to say, this is genius:

Code: [Select]
`(bubble (car lst) (bubblesort (cdr lst)))`

I would never have thought of using that construct  ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #17 on: May 16, 2011, 04:59:31 PM »
Thanks Lee,

I'm glad you like it, I was happy and quite proud when I found this construct.

PS: I revised a little the codes of bubblesort and insertsort to make them more different (LISP implementations of both algorithms are very similar)
Speaking English as a French Frog

#### ElpanovEvgeniy ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #18 on: May 17, 2011, 02:57:52 AM »

#### chlh_jd

• Guest ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #19 on: May 18, 2011, 05:21:51 AM »
Excellent Gile !

#### Jeff H ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #20 on: May 18, 2011, 10:52:15 AM »
Thanks for the replies,

Thanks gile for the different sorting implementations

#### Jeff H ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #21 on: May 19, 2011, 04:46:43 AM »
*********************************Edit******************************
Change name from NumberSort to BadNumberSort and did not change recursive cases
*********************************Edit******************************

Okay I know this is not a efficient method but I am new to Lisp and get a pass on posting bad code.

How would I make this keep calling itself until list is sorted?

I have tried
while list not equal to result of calling function
if statements
etc...

Code: [Select]
`(defun BadNumberSort (lst)  (cond    ((null lst) lst)    ((null (cadr lst)) lst)    ((< (car lst) (cadr lst)) (cons (car lst) (BadNumberSort (cdr lst))))    (T (cons (cadr lst) (BadNumberSort (cons (car lst) (cdr (cdr lst))))))  ))`
So how can I make it call itself for example 3 times for the given list below.
Just a list of integers, I have not made it to the chapter with dotted pairs, reals, decimals so I am not worried about that right now.

Quote
_\$ (BADNUMBERSORT '(5 3 4 1 2))
(3 4 1 2 5)
_\$ (BADNUMBERSORT '(3 4 1 2 5))
(3 1 2 4 5)
_\$ (BADNUMBERSORT '(3 1 2 4 5))
(1 2 3 4 5)
« Last Edit: May 19, 2011, 04:59:13 AM by Jeff H »

#### Jeff H ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #22 on: May 19, 2011, 06:25:33 PM »
I do not know how bad this is and on no sleep and spent 8 hours digging a trench in the hot sun.

Code: [Select]
`(defun NumberSort (lst / nlst)  (defun SortNums (slst)    (cond      ((null slst) slst)      ((null (cadr slst)) slst)      ((< (car slst) (cadr slst)) (cons (car slst) (SortNums (cdr slst))))      (T (cons (cadr slst) (SortNums (cons (car slst) (cdr (cdr slst))))))    )  )  (setq nlst (SortNums lst))    (cond    ((equal nlst (SortNums nlst)) nlst)    (T (NumberSort nlst))  ))  `
Quote
NUMBERSORT
_\$ (NUMBERSORT '(5 3 4 1 2))
(1 2 3 4 5)
_\$ (NUMBERSORT '(5 34 4 11 2 8 ))
(2 4 5 8 11 34)
_\$ (NUMBERSORT '(4 3 80 134 4 12 1 10 17))
(1 3 4 4 10 12 17 80 134)
_\$ (NUMBERSORT '(6 -4 7 12 -2 4))
(-4 -2 4 6 7 12) ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #23 on: May 29, 2011, 01:03:31 PM »
Another one implementing the binary tree sort algorithm:

LISP
Code - Auto/Visual Lisp: [Select]
1. (defun treeSort (lst / insert fill traversal)
2.
3.   (defun insert (ele tree)
4.     (cond
5.       ((null tree) (list ele) )
6.       ((< ele (car tree)) (list (car tree) (insert ele (cadr tree)) (caddr tree)))
8.     )
9.   )
10.
11.   (defun fill (lst tree)
12.     (if lst
13.       (fill (cdr lst) (insert (car lst) tree))
14.       tree
15.     )
16.   )
17.
18.   (defun traversal (tree)
21.       )
22.       (list (car tree))
25.       )
26.     )
27.   )
28.
29.   (traversal (fill lst nil))
30. )

F#
Code - F#: [Select]
1. type Tree<'a> =
2.    | Tree of 'a * Tree<'a> * Tree<'a>
3.     | Empty
4.
5. let rec insert x = function
6.     | Tree(n,l,r) -> if x < n
7.                      then Tree(n, insert x l, r)
8.                      else Tree(n, l, insert x r)
9.     | Empty -> Tree(x, Empty, Empty)
10.
11. let rec traversal = function
12.     | Tree(n,l,r) -> traversal l @ [n] @ traversal r
13.     | Empty -> []
14.
15. let treesort lst =
16.     traversal (List.fold (fun t a -> insert a t) Empty lst)
« Last Edit: July 25, 2013, 07:19:20 AM by gile »
Speaking English as a French Frog

#### highflyingbird ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #24 on: June 19, 2012, 02:29:10 PM »
gile's  recursion is very beatiful!

This is my Merge Sort, I tested it,it's longer than gile's,but a little faster .
Code - Auto/Visual Lisp: [Select]
1. (defun H:Merge( L R / a b s)
2.   (setq a (car L))
3.   (setq b (car R))
4.   (while (and a b)
5.     (if (< a b)
6.       (setq s (cons a s)
7.             L (cdr L)
8.             a (car L)
9.       )
10.       (setq s (cons b s)
11.             R (cdr R)
12.             b (car R)
13.       )
14.     )
15.   )
16.   (if L
17.     (while L
18.       (setq s (cons (car L) s))
19.       (setq L (cdr L))
20.     )
21.     (while R
22.       (setq s (cons (car R) s))
23.       (setq R (cdr R))
24.     )
25.   )
26.   (reverse S)
27. )
28.
29. (defun MSort (lst / L R)
30.   (cond
31.     ( (cddr lst)
32.       (setq R lst)
33.       (repeat (/ (length lst) 2)
34.         (setq L (cons (car R) L))
35.         (setq R (cdr R))
36.       )
37.       (H:Merge (msort (reverse L)) (msort R))
38.     )
39.     ( (and (cdr lst) (> (car lst) (cadr lst)))
40.       (reverse lst)
41.     )
42.     ( t
43.       lst
44.     )
45.   )
46. )
47.

example:
(msort '(3 43 2 35 23 4 53 21 32 123 12))
I am a bilingualist,Chinese and Chinglish.

#### ElpanovEvgeniy ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #25 on: June 20, 2012, 07:26:45 AM »
other way:
Code - Auto/Visual Lisp: [Select]
1. (defun eea-sort (l / i)
2.   (cond ((not l) nil)
3.         ((cons (setq i (apply (function min) l)) (eea-sort (vl-remove i l))))
4.   )
5. )

#### ElpanovEvgeniy ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #26 on: June 20, 2012, 07:29:27 AM »
if you use repetitions:
Code - Auto/Visual Lisp: [Select]
1. (defun f1 (i l)
2.   (cond ((not l) nil)
3.         ((equal (car l) i) (cdr l))
4.         ((cons (car l) (f1 i (cdr l))))
5.   )
6. )
7. (defun eea-sort (l / i)
8.   (cond ((not l) nil)
9.         ((cons (setq i (apply (function min) l)) (eea-sort (f1 i l))))
10.   )
11. ) ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #27 on: June 20, 2012, 07:43:12 AM »
other way:
Code - Auto/Visual Lisp: [Select]
1. (defun eea-sort (l / i)
2.   (cond ((not l) nil)
3.         ((cons (setq i (apply (function min) l)) (eea-sort (vl-remove i l))))
4.   )
5. )

Careful...

Code - Auto/Visual Lisp: [Select]
1. (eea-sort '(5 2 4 3.0))

http://www.theswamp.org/index.php?topic=38292.msg433727#msg433727

#### ElpanovEvgeniy ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #28 on: June 20, 2012, 07:47:48 AM »
...
Code: [Select]
`(defun MinSort ( lst / m )  (if lst    (cons (setq m (apply 'min lst))      (MinSort (vl-remove-if '(lambda ( x ) (equal x m 1e-8)) lst))    )  ))`

Yes, you wrote me soon!  The whole year... #### ElpanovEvgeniy ##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #29 on: June 20, 2012, 07:55:28 AM »
more complex version of...
Code - Auto/Visual Lisp: [Select]
1. (defun eea-sort (l / f)
2.   (defun f (a b c i)
3.     (cond ((not c) (append (eea-sort a) (list i) (eea-sort b)))
4.           ((<= (car c) i) (f (cons (car c) a) b (cdr c) i))
5.           ((f a (cons (car c) b) (cdr c) i))
6.     )
7.   )
8.   (if l (f nil nil (cdr l) (car l)))
9. )