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

0 Members and 1 Guest are viewing this topic.

#### Grrr1337

• Bull Frog
• Posts: 333
##### 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?

#### Lee Mac

• Seagull
• Posts: 11704
• AutoCAD 2015 Windows 7 London, England
##### Re: Sort a list using recursion
« Reply #1 on: July 12, 2017, 07:50:21 am »

#### Mark

• Custom Title
• Administrator
• Seagull
• Posts: 28045
##### 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: 16932
• 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: 333
##### 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]
`; _\$ (vl_every (lambda (x) (eq 'STR (type x))) '("A" 1 "B" 2 "C" "D" "E" 3 4 5 6 "F")) -> nil; _\$ (vl_every (lambda (x) (eq 'STR (type x))) '("A" "B" "C" "D" "E" "F")) -> (T T T T T T); _\$ (vl_every numberp '(1 2 3 4 5 6 7 8 9 0)) -> (T T T T T T T T T T); _\$ (vl_every (lambda (x) (if (numberp x) x)) '(1 4 5 1 2 6 3 7)) -> (1 4 5 1 2 6 3 7)(defun vl_every ( f L / rec )  (defun rec ( f L / r )    (cond       ( (not L) L)      ( (not (setq r (f (car L)))) r)      ( (cons r (rec f (cdr L))) )    )  )  (cond     ( (not (listp L)) )    ( (not (member (type f) '(SUBR USUBR))) )    ( (setq r (rec f L)) (if (apply '= (mapcar 'length (list L r))) r) )  )); defun vl_every ; _\$ (_mapcar strcase '("a" "b" "c" "d" "e")) -> ("A" "B" "C" "D" "E"); _\$ (_mapcar (lambda (x) (strcat (strcase x) "1")) '("a" "b" "c" "d" "e")) -> ("A1" "B1" "C1" "D1" "E1")(defun _mapcar ( f L / rec )  (defun rec ( f L / r )    (cond       ( (not L) L)      ( (cons (f (car L)) (rec f (cdr L))) )    )  )  (cond     ( (not (listp L)) )    ( (not (member (type f) '(SUBR USUBR))) )    ( (rec f L) )  )); defun _mapcar ; _\$ (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"); _\$ (vl_remove_if_not numberp '("A" 1 "B" 2 "C" "D" "E" 3 4 5 6 "F")) -> (1 2 3 4 5 6)(defun vl_remove_if_not ( tf L / rec )  (defun rec ( tf L )    (cond       ( (not L) L)      ( (append (if (tf (car L)) (list (car L))) (rec tf (cdr L))) )    )  )  (cond     ( (not (listp L)) )    ( (not (member (type tf) '(SUBR USUBR))) )    ( (rec tf L) )  )); defun vl_remove_if_not ; _\$ (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); _\$ (vl_positions numberp '("A" 1 "B" 2 "C" "D" "E" 3 4 5 6 "F")) -> (1 3 7 8 9 10)(defun vl_positions ( tf L / rec )  (defun rec ( tf L i )    (cond       ( (not L) L)      ( (append (if (tf (car L)) (list i)) (rec tf (cdr L) (1+ i))) )    )  )  (cond     ( (not (listp L)) )    ( (not (member (type tf) '(SUBR USUBR))) )    ( (rec tf L 0) )  )); defun vl_positions  ; _\$ (GetNths '(0 2 5 8) (mapcar 'chr (vl-string->list "ABCDEFGHIJKLMNOPQRSTUVWXYZ"))) -> ("A" "C" "F" "I"); _\$ (GetNths '(0 1 2 5 125) (mapcar 'chr (vl-string->list "ABCDEFGHIJKLMNOPQRSTUVWXYZ"))) -> ("A" "B" "C" "F"); _\$ (GetNths '(0 2 5 8) (mapcar 'chr (vl-string->list "01234567890"))) -> ("0" "2" "5" "8"); _\$ (GetNths '(0 1 2 5 125) (mapcar 'chr (vl-string->list "01234567890"))) -> ("0" "1" "2" "5")(defun GetNths ( nths L / rec )  (defun rec ( nths L i )    (cond       ( (not L) L)      ( (append (if (member i nths) (list (car L))) (rec nths (cdr L) (1+ i))) )    )  )  (cond     ( (not (listp L)) )    ( (not (listp nths)) )    ( (rec nths L 0) )  )); defun GetNths `

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..

#### MP

• Seagull
• Posts: 16932
• 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