CODEWITHSUNDEEP
sortinglisp
Danny S
Danny S

Reputation: 193

Non-destructive sort in lisp?

I have been tasked to create a program, and within it I require a function to return a sorted list (in alphabetical order). However, I am unable to use and "non-functional" functions eg "set, setq" etc... And that includes the built in sort function (because it is destructive). So, I was wondering if there is a way to build a non-destructive sort in lisp?

Upvotes: 7

Views: 2251

Answers (2)

Paul Richter
Paul Richter

Reputation: 6311

If your destructive sort does something like swap two neighboring elements which are surrounded by elements which you leave intact, then a non-destructive way is to create a new list consisting of those two elements swapped, surrounded by the other elements. Then you use that new list as the base for the succeeding sort actions.

Destructively, your working list is the same from start to finish, and you modify it by replacing the value in one "place" by that in another "place". Non-destructively, at each step you create a new list that becomes the working list.

I will leave the implementation to you.

Upvotes: 0

Daniel Jour
Daniel Jour

Reputation: 16156

The easiest way would be to make a copy before sorting:

(sort (copy-seq input) predicate)

Or you write a sort function yourself, e.g. quicksort:

(defun qsort (input predicate)
  (if input
    (let* ((pivot (first input))
           (rest (rest input))
           (lesser (remove-if-not #'(lambda (x)
                                      (funcall predicate x pivot))
                                  rest))
           (greater (remove-if-not #'(lambda (x)
                                       (not (funcall predicate x pivot)))
                                   rest)))
      (append (qsort lesser predicate)
              (list pivot)
              (qsort greater predicate)))
    nil))

(Demo)

Note that one could optimize this to detect already sorted rests of a list, enabling structure sharing between the unsorted and sorted list.

Upvotes: 8

Related Questions