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

0 Members and 1 Guest are viewing this topic.

Jeff H

  • Needs a day job
  • Posts: 6144
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))
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

pBe

  • Bull Frog
  • Posts: 402
Re: Sort list of numbers (vl-sort not allowed)
« Reply #4 on: May 15, 2011, 12:58:15 AM »
what about good 'ol acad_strlsort? would that be considered cheating?  :lol:

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

  • Gator
  • Posts: 2507
  • 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: 402
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

  • Gator
  • Posts: 2507
  • 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: 12906
  • 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: 402
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: 12906
  • 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  ;-)

Perhaps add some tolerance:

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: 402
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: 402
Re: Sort list of numbers (vl-sort not allowed)
« Reply #13 on: May 15, 2011, 08:44:27 AM »

Perhaps add some tolerance:

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 )