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

0 Members and 1 Guest are viewing this topic.

gile

  • Water Moccasin
  • Posts: 2234
  • Marseille, France
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

Lee Mac

  • Seagull
  • Posts: 12313
  • London, England
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  :-o

gile

  • Water Moccasin
  • Posts: 2234
  • Marseille, France
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

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: Sort list of numbers (vl-sort not allowed)
« Reply #18 on: May 17, 2011, 02:57:52 AM »
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

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

  • Needs a day job
  • Posts: 6055
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

  • Needs a day job
  • Posts: 6055
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

  • Needs a day job
  • Posts: 6055
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)

gile

  • Water Moccasin
  • Posts: 2234
  • Marseille, France
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)))
  7.       (T (list (car tree) (cadr tree) (insert ele (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)
  19.     (append
  20.       (if (cadr tree)
  21.         (traversal (cadr tree))
  22.       )
  23.       (list (car tree))
  24.       (if (caddr tree)
  25.         (traversal (caddr tree))
  26.       )
  27.     )
  28.   )
  29.  
  30.   (traversal (fill lst nil))
  31. )

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

  • Bull Frog
  • Posts: 415
  • Later equals never.
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

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
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. )
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
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. )
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

Lee Mac

  • Seagull
  • Posts: 12313
  • London, England
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

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
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...  :-D
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
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. )
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/