Author Topic: Sort a list using recursion  (Read 260 times)

0 Members and 1 Guest are viewing this topic.

Grrr1337

  • Bull Frog
  • Posts: 354
Sort a list using recursion
« on: July 12, 2017, 02:34:20 am »
Hi dear swampers,
I often play with recursion, but this one thing keeps me wondering:
How do you sort a list, using a recursion?
Lets say its list of numbers. (for a simpliest example).
And for a more complex, how to replicate the (vl-sort) function?
 :roll:

Lee Mac

  • Seagull
  • Posts: 11779
  • AutoCAD 2015 Windows 7 London, England

Mark

  • Custom Title
  • Administrator
  • Seagull
  • Posts: 28150
Re: Sort a list using recursion
« Reply #2 on: July 12, 2017, 08:05:18 am »
I often play with recursion, but this one thing keeps me wondering:
How do you sort a list, using a recursion?
Recursion was one of the hardest things to wrap my head around. I'm still in awe with some of the recursion I see here. ElpanovEvgeniy and MP are a couple that come to mind.
TheSwamp.org  (serving the CAD community since 2003)

MP

  • Seagull
  • Posts: 16985
  • brevity != aggression
Re: Sort a list using recursion
« Reply #3 on: July 12, 2017, 12:03:20 pm »
One way to learn is to translate existing solid code from another language to LISP.

For example, Visual BASIC (props to Randy Birch & VBNET) to LISP.

Quick & Dirty ...

Code: [Select]
(defun _QSort ( lst / _IndexList _PutNth _Nth _QSortAux )

    (defun _IndexList ( lst )
        (   (lambda ( i )
                (mapcar
                    (function (lambda (v) (cons (setq i (1+ i)) v)))
                    lst
                )
            )
            -1
        )
    )

    (defun _PutNth ( value n lst )
        (subst
            (cons n value)
            (nth n lst)
            lst
        )
    )
   
    (defun _Nth ( n lst )
        (cdr (nth n lst))
    )       

    (defun _QSortAux ( lst inLo inHi / tmpLo tmpHi pivot tmpSwp )
   
        (mapcar 'set '(tmpLo tmpHi) (list inLo inHi))

        (setq pivot (_Nth (/ (+ inLo inHi) 2) lst))
       
        (while (<= tmpLo tmpHi)
       
            (while (and (< (_Nth tmpLo lst) pivot) (< tmpLo inHi))
                (setq tmpLo (1+ tmpLo))
            )

            (while (and (< pivot (_Nth tmpHi lst)) (< inLo tmpHi))
                (setq tmpHi (1- tmpHi))
            )
           
            (if (<= tmpLo tmpHi)
                (setq
                    tmpSwp (_Nth tmpLo lst)
                    lst    (_PutNth (_Nth tmpHi lst) tmpLo lst)
                    lst    (_PutNth tmpSwp tmpHi lst)
                    tmpLo  (1+ tmpLo)
                    tmpHi  (1- tmpHi)
                )
            )
        )
       
        (if (< inLo tmpHi) (setq lst (_QSortAux lst inLo tmpHi)))
        (if (< tmpLo inHi) (setq lst (_QSortAux lst tmpLo inHi)))
       
        lst

    )

    (mapcar 'cdr (_QSortAux (_IndexList lst) 0 (1- (length lst))))

)

Appears to work:

(_QSort '(8 7 4 3 1 9 6 2 5)) >> (1 2 3 4 5 6 7 8 9)

Cheers.


« Last Edit: July 12, 2017, 03:11:24 pm by MP »
\|// Set goal. Experiment tirelessly until
|oo| practice has become expertise.  Loop.
|- | LinkedIn | Dropbox | About

Grrr1337

  • Bull Frog
  • Posts: 354
Re: Sort a list using recursion
« Reply #4 on: July 12, 2017, 03:48:25 pm »
https://www.theswamp.org/index.php?topic=38292

Thanks Lee, I've forgot about that thread.
I relooked at gile's examples of the sorting algorithms and indeed its really confusing (for me),
since at every (example) function theres a sub-defined recursive function and the main function definition also acts recursively!

Recursion was one of the hardest things to wrap my head around. I'm still in awe with some of the recursion I see here. ElpanovEvgeniy and MP are a couple that come to mind.

Hi Mark,
Writing a simple recursion felt fairly easy for me, since when iterating thru the list with car and cdr functions is not so mind-consuming.
And I realised that with recursion one could pretty much simulate any iterator in list (mapcar/vl-some/vl-every/while/repeat/vlax-for/...).
Even its possible to define functions that act similar to the standard ones (above listed), but to have different returns.
Or even define handy subfunctions that make the list manipulation even easier.
But yeah, the hardest thing to figure out is obviously to perform sorting!

Few examples (not related to sorting - just to see what I mean) :
Code - Auto/Visual Lisp: [Select]
  1. ; _$ (vl_every (lambda (x) (eq 'STR (type x))) '("A" 1 "B" 2 "C" "D" "E" 3 4 5 6 "F")) -> nil
  2. ; _$ (vl_every (lambda (x) (eq 'STR (type x))) '("A" "B" "C" "D" "E" "F")) -> (T T T T T T)
  3. ; _$ (vl_every numberp '(1 2 3 4 5 6 7 8 9 0)) -> (T T T T T T T T T T)
  4. ; _$ (vl_every (lambda (x) (if (numberp x) x)) '(1 4 5 1 2 6 3 7)) -> (1 4 5 1 2 6 3 7)
  5. (defun vl_every ( f L / rec )
  6.  (defun rec ( f L / r )
  7.    (cond
  8.      ( (not L) L)
  9.      ( (not (setq r (f (car L)))) r)
  10.      ( (cons r (rec f (cdr L))) )
  11.    )
  12.  )
  13.  (cond
  14.    ( (not (listp L)) )
  15.    ( (not (member (type f) '(SUBR USUBR))) )
  16.    ( (setq r (rec f L)) (if (apply '= (mapcar 'length (list L r))) r) )
  17.  )
  18. ); defun vl_every
  19.  
  20. ; _$ (_mapcar strcase '("a" "b" "c" "d" "e")) -> ("A" "B" "C" "D" "E")
  21. ; _$ (_mapcar (lambda (x) (strcat (strcase x) "1")) '("a" "b" "c" "d" "e")) -> ("A1" "B1" "C1" "D1" "E1")
  22. (defun _mapcar ( f L / rec )
  23.  (defun rec ( f L / r )
  24.    (cond
  25.      ( (not L) L)
  26.      ( (cons (f (car L)) (rec f (cdr L))) )
  27.    )
  28.  )
  29.  (cond
  30.    ( (not (listp L)) )
  31.    ( (not (member (type f) '(SUBR USUBR))) )
  32.    ( (rec f L) )
  33.  )
  34. ); defun _mapcar
  35.  
  36. ; _$ (vl_remove_if_not (lambda (x) (eq 'STR (type x))) '("A" 1 "B" 2 "C" "D" "E" 3 4 5 6 "F")) -> ("A" "B" "C" "D" "E" "F")
  37. ; _$ (vl_remove_if_not numberp '("A" 1 "B" 2 "C" "D" "E" 3 4 5 6 "F")) -> (1 2 3 4 5 6)
  38. (defun vl_remove_if_not ( tf L / rec )
  39.  (defun rec ( tf L )
  40.    (cond
  41.      ( (not L) L)
  42.      ( (append (if (tf (car L)) (list (car L))) (rec tf (cdr L))) )
  43.    )
  44.  )
  45.  (cond
  46.    ( (not (listp L)) )
  47.    ( (not (member (type tf) '(SUBR USUBR))) )
  48.    ( (rec tf L) )
  49.  )
  50. ); defun vl_remove_if_not
  51.  
  52. ; _$ (vl_positions (lambda (x) (eq 'STR (type x))) '("A" 1 "B" 2 "C" "D" "E" 3 4 5 6 "F")) -> (0 2 4 5 6 11)
  53. ; _$ (vl_positions numberp '("A" 1 "B" 2 "C" "D" "E" 3 4 5 6 "F")) -> (1 3 7 8 9 10)
  54. (defun vl_positions ( tf L / rec )
  55.  (defun rec ( tf L i )
  56.    (cond
  57.      ( (not L) L)
  58.      ( (append (if (tf (car L)) (list i)) (rec tf (cdr L) (1+ i))) )
  59.    )
  60.  )
  61.  (cond
  62.    ( (not (listp L)) )
  63.    ( (not (member (type tf) '(SUBR USUBR))) )
  64.    ( (rec tf L 0) )
  65.  )
  66. ); defun vl_positions
  67.  
  68.  
  69. ; _$ (GetNths '(0 2 5 8) (mapcar 'chr (vl-string->list "ABCDEFGHIJKLMNOPQRSTUVWXYZ"))) -> ("A" "C" "F" "I")
  70. ; _$ (GetNths '(0 1 2 5 125) (mapcar 'chr (vl-string->list "ABCDEFGHIJKLMNOPQRSTUVWXYZ"))) -> ("A" "B" "C" "F")
  71. ; _$ (GetNths '(0 2 5 8) (mapcar 'chr (vl-string->list "01234567890"))) -> ("0" "2" "5" "8")
  72. ; _$ (GetNths '(0 1 2 5 125) (mapcar 'chr (vl-string->list "01234567890"))) -> ("0" "1" "2" "5")
  73. (defun GetNths ( nths L / rec )
  74.  (defun rec ( nths L i )
  75.    (cond
  76.      ( (not L) L)
  77.      ( (append (if (member i nths) (list (car L))) (rec nths (cdr L) (1+ i))) )
  78.    )
  79.  )
  80.  (cond
  81.    ( (not (listp L)) )
  82.    ( (not (listp nths)) )
  83.    ( (rec nths L 0) )
  84.  )
  85. ); defun GetNths
  86.  

Ofcourse some people say that recursion is really slow, but its not neccessary to use it everywhere (in some cases the user-delay is unnoticeable).


One way to learn is to translate existing solid code from another language to LISP.

For example, Visual BASIC (props to Randy Birch & VBNET) to LISP.


I thought about doing this, but I don't speak that many languages like you do! :)
And I suck at implementing algorithms... (time will tell about that).

Quick & Dirty ...

Appears to work:

(_QSort '(8 7 4 3 1 9 6 2 5)) >> (1 2 3 4 5 6 7 8 9)

Cheers.

Works perfect, and its retaining the duplicates like its supposed, I did a small comparsion from some of gile's examples:
Code: [Select]
_$ (_QSort '(8 0 7 11 4 3 1 15 9 0 6 11 14 2)) >> (0 0 1 2 3 4 6 7 8 9 11 11 14 15)
_$ (BubbleSort '(8 0 7 11 4 3 1 15 9 0 6 11 14 2)) >> (0 1 2 3 4 6 7 8 9 11 14 15)
_$ (InsertSort '(8 0 7 11 4 3 1 15 9 0 6 11 14 2)) >> (0 0 1 2 3 4 6 7 8 9 11 11 14 15)

The thing I really like is that your example is not so messed up:
-Define the required subfunctions for the task
-Execute
But I know thats your style of coding - very clean and readable. So thanks for that code! I'm gonna chew it for the next days.

BTW I'm a monkey mimic'ing such details like this - about maintaining the overall code (learing from you, learining from Lee Mac..). Revising as much as I can..  :police:


MP

  • Seagull
  • Posts: 16985
  • brevity != aggression
Re: Sort a list using recursion
« Reply #5 on: July 12, 2017, 04:34:08 pm »
Thank you for the kind words -- algorithmic thanks go to Randy Birch who did the heavy lifting -- code translation is a parlor trick in comparison.
\|// Set goal. Experiment tirelessly until
|oo| practice has become expertise.  Loop.
|- | LinkedIn | Dropbox | About