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

0 Members and 1 Guest are viewing this topic.

#### Jeff H

• Needs a day job
• Posts: 6055
##### Sort list of numbers (vl-sort not allowed)
« on: May 14, 2011, 09:22:04 PM »
Trying to pick up some Lisp and thought this would be good thing to try.

I have messed with it a little but not yet there.

Sorting a list of numbers with just AutoLisp.

(8 5 2 7 4 3)
==========
(2 3 4 5 7 8 )

I did not see a example without vl-sort used.

#### Peter Jamtgaard

• Guest
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #1 on: May 14, 2011, 10:57:34 PM »
Its been a few years since I wrote my last bubble sort function.

(bubblesort '(8 5 2 7 4 3))  returns '(2 3 4 5 7 8 )

Code: [Select]
`(defun BubbleSort (lstItems / blnFlag item1 item2 lstItems2) (setq item1 (car lstItems)) (foreach item2 (cdr lstItems)  (if (<= item1 item2)   (setq lstItems2 (cons item1 lstItems2)         item1     item2   )   (setq lstItems2 (cons item2 lstItems2)         blnFlag   T   )  ) ) (if blnFlag   (BubbleSort (reverse (cons item1 lstItems2)))  (reverse (cons item1 lstItems2)) ))`
« Last Edit: May 15, 2011, 09:18:45 AM by peterj »

#### Kerry

• Mesozoic relic
• Seagull
• Posts: 11654
• class keyThumper<T>:ILazy<T>
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #2 on: May 14, 2011, 11:18:44 PM »
Its been a few years since I wrote my last bubble sort function.

(bubblesort '(8 5 2 7 4 3))  returns '(2 3 4 5 7 8 )

Code: [Select]
`(defun BubbleSort (lstItems / blnFlag item1 item2 lstItems2) (setq item1 (car lstItems)) (foreach item2 (cdr lstItems)  (if (< item1 item2)   (setq lstItems2 (cons item1 lstItems2)         item1     item2   )   (setq lstItems2 (cons item2 lstItems2)         blnFlag   T   )  ) ) (if blnFlag   (BubbleSort (reverse (cons item1 lstItems2)))  (reverse (cons item1 lstItems2)) ))`

Hello Peter,

What does this give you ??
(bubblesort '(8 6 5 2 7 4 6 3))
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

#### Kerry

• Mesozoic relic
• Seagull
• Posts: 11654
• class keyThumper<T>:ILazy<T>
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #3 on: May 14, 2011, 11:21:31 PM »
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

#### pBe

• Bull Frog
• Posts: 377
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #4 on: May 15, 2011, 12:58:15 AM »

Code: [Select]
`(mapcar '(lambda (y)               (ascii y))        (acad_strlsort              (mapcar '(lambda (x)                             (chr x))                      '(8 6 5 2 7 4 6 3))))`(2 3 4 5 6 6 7 8 )

works only for single digit integers though

as you can see here

Code: [Select]
`(mapcar '(lambda (y)               (ascii y))        (acad_strlsort              (mapcar '(lambda (x)                             (chr x))                      '(8 227 101 6 5 2 12 37 7 28 4 6 3 105 10 13))))`
(2 3 4 5 6 6 7 8 28 10 12 13 37 227 101 105)

bummer
« Last Edit: May 15, 2011, 01:16:25 AM by pBe »

#### gile

• Water Moccasin
• Posts: 2234
• Marseille, France
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #5 on: May 15, 2011, 05:06:46 AM »
Hi,

Here're some of the most famous sorting algorithms implementation examples (using 'functional style' rather than looking for 'brute performance'):

EDIT: revised codes

Bubble sort
Code: [Select]
`(defun bubblesort (lst / bubble)    (defun bubble (ele lst)    (cond      ((null lst) ele)      ((< (car lst) ele) (bubble (car lst) (cdr lst)))      ((bubble ele (cdr lst)))    )  )    ((lambda (b)     (if lst       (cons b (bubblesort (vl-remove b lst)))     )   )    (bubble (car lst) (cdr lst))  ))`
Insertion sort
Code: [Select]
`(defun insertsort (lst / insert)    (defun insert (ele lst)    (cond      ((null lst) (list ele))      ((< ele (car lst)) (cons ele lst))      ((cons (car lst) (insert ele (cdr lst))))    )  )    (if lst    (insert (car lst) (insertsort (cdr lst)))  ))`
Quick sort
Code: [Select]
`(defun quicksort (lst / left right)  (defun left (ele lst)    (cond      ((null lst) nil)      ((< ele (car lst)) (left ele (cdr lst)))      (T (cons (car lst) (left ele (cdr lst))))    )  )  (defun right (ele lst)    (cond      ((null lst) nil)      ((< (car lst) ele) (right ele (cdr lst)))      (T (cons (car lst) (right ele (cdr lst))))    )  )  (if lst    (append (quicksort (left (car lst) (cdr lst)))     (cons (car lst)   (quicksort (right (car lst) (cdr lst)))     )    )  ))`
Merge sort
Code: [Select]
`(defun mergesort (lst / merge brklst)  (defun merge (l1 l2)    (cond      ((null l1) l2)      ((null l2) l1)      ((if (< (car l1) (car l2)) (cons (car l1) (merge (cdr l1) l2)) (cons (car l2) (merge l1 (cdr l2)))       )      )    )  )  (defun brklst (lst acc n)    (if (= 0 n)      (list acc lst)      (brklst (cdr lst) (cons (car lst) acc) (1- n))    )  )  (if (cdr lst)    (progn      (setq lst (brklst lst nil (/ (length lst) 2)))      (merge (mergesort (car lst))      (mergesort (cadr lst))      )    )    lst  ))`
« Last Edit: May 22, 2011, 04:02:45 PM 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 #6 on: May 15, 2011, 05:28:40 AM »
Hi,Here're some of the most famous sorting algorithms implementation examples (using 'functional style' rather than looking for 'brute performance'):

Really wonderful code. I like it.
I am a bilingualist,Chinese and Chinglish.

#### pBe

• Bull Frog
• Posts: 377
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #7 on: May 15, 2011, 06:07:10 AM »
Code: [Select]
`(defun BubbleSort  (nlst / loopnum lownum next sorted nlst)(defun loopnum  (low lst /  )    (if (setq a low              b (cdr lst))          (if (minusp (- (car b) a))                (loopnum (car b) b)                (if b (loopnum a b)))          )    a    )      (while (setq Lownum (car nlst))            (setq next (cdr nlst))            (setq Sorted (cons (loopnum Lownum nlst) Sorted))            (setq nlst (vl-remove (car sorted) nlst))            (if (member Lownum sorted)                  (setq nlst (vl-remove lownum nlst))                  ))      (reverse sorted)      )`
(BUBBLESORT '(8 5 2 7 4 3))
(2 3 4 5 7 8 )

(BUBBLESORT '(6 5 3 8 10 25 712 13 37 4 105 ))
(3 4 5 6 8 10 13 25 37 105 712)

(BUBBLESORT '(-1 6 5 3 6 -34  111 3  3 4 1  5 1258 10 23 52.3 6 2015 712 8 13 37 4 105 ))
(-34 -1 1 3 4 5 6 8 10 13 23 37 52.3 105 111 712 1258 2015)

Removes duplicates as well
Still brute force though

should've use (< (car b) a) instead of  (minusp (- (car b) a)), what was i thinking!!! it just shows variety i guess

EDIT: (> (car b) a)<------- retarded (no need for reverse)  :loco:
« Last Edit: May 15, 2011, 08:33:18 AM by pBe »

#### gile

• Water Moccasin
• Posts: 2234
• Marseille, France
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #8 on: May 15, 2011, 06:29:22 AM »
Thanks highflybird ,

We had a funny challenge with this task on a French Web site.
« Last Edit: July 12, 2017, 03:17:54 PM by gile »
Speaking English as a French Frog

#### Lee Mac

• Seagull
• Posts: 12313
• London, England
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #9 on: May 15, 2011, 08:15:28 AM »
Great code Gile - I shall certainly be taking some time to study it

#### pBe

• Bull Frog
• Posts: 377
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #10 on: May 15, 2011, 08:25:41 AM »
Another....

Code: [Select]
`(defun MinSort (lst / sortedlist) (while lst       (setq SortedList (cons (apply 'min lst) SortedList))               (setq lst (vl-remove (car SortedList) lst))              )(reverse SortedList))`
for some reason this somehow crash when you use floating numbers

(MINSORT'(-1 6 5 3 6 -34  111 3  3 4 1  5 1258 10 23 52 6 2015 712 8 13 37 4 105 ))

(-34 -1 1 3 4 5 6 8 10 13 23 37 52 105 111 712 1258 2015)

(MINSORT'(8 5 3.36 2 7 4 3 1 12))<--------

Why do you think that happens?

EDIT: Shouldve been this way.. no need to reverse the list

Code: [Select]
`(defun MinSort (lst / sortedlist) (while lst      (setq SortedList (cons (apply 'max lst) SortedList))              (setq lst (vl-remove (car SortedList) lst))              )SortedList)`
« Last Edit: May 15, 2011, 08:30:02 AM by pBe »

#### Lee Mac

• Seagull
• Posts: 12313
• London, England
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #11 on: May 15, 2011, 08:32:26 AM »
Why do you think that happens?

Because when you use:

Code: [Select]
`(apply 'min <list>)`
All numbers within the list are converted to the same datatype with accuracy preserved, hence, if you have any doubles in the list, all the other integers are converted to a double:

Code: [Select]
`(apply 'min '(4 2 3.36 1))Returns:  1.0`
From this result I'm sure you can work out why your code loops continuously

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))    )  ))`
« Last Edit: May 15, 2011, 08:35:44 AM by Lee Mac »

#### pBe

• Bull Frog
• Posts: 377
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #12 on: May 15, 2011, 08:40:36 AM »
(apply 'min '(4 2 3.36 1))..

lst will never be nil as the result is nowhere on the list

Thanks for the heads up Lee

#### pBe

• Bull Frog
• Posts: 377
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #13 on: May 15, 2011, 08:44:27 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))    )  ))`

Will comply
Thanks my friend

#### Peter Jamtgaard

• Guest
##### Re: Sort list of numbers (vl-sort not allowed)
« Reply #14 on: May 15, 2011, 09:20:37 AM »
Quote
What does this give you ??
(bubblesort '(8 6 5 2 7 4 6 3))

I changed the < to <= in the code above.

returns

'(2 3 4 5 6 6 7 8 )