CODEWITHSUNDEEP
insertlisp
anonymous
anonymous

Reputation: 21

Lisp Insert Sorting Problem

Use insert to write a function sort1 which sorts a list of integers into increasing order. [We are done if the list is nil. Otherwise insert the car of the list into the sorted cdr.]

This is what I've managed to do and I'm having trouble to define both function in a single function called sort1:

(defun insert (item lst &optional (key #'<))
  (if (null lst)
    (list item)
  (if (funcall key item (car lst))
          (cons item lst) 
          (cons (car lst) (insert item (cdr lst) key)))))
(defun insertion-sort (lst &optional (key #'<))
  (if (null lst)
    lst
    (insert (car lst) (insertion-sort (cdr lst) key) key)))

Upvotes: 2

Views: 2333

Answers (1)

Gareth Rees
Gareth Rees

Reputation: 65854

The easiest way to get it all into one function definition is to use labels to define the function insert as a local function inside insertion-sort.

There are several other things to say about your code, however:

  • You don't need to respell the variable as lst for fear of a collision with the function list: in Common Lisp functions and variables live in different namespaces.
  • It's common practice to simplify the pattern (if (null list) list (...)) to (and list (...)) since if (null list) is true, then list must be nil!
  • Your argument key is mis-named: a key function is one that takes a list item and returns a key for comparison (see the HyperSpec on sort). What you have here (a function that compares two items) is called a "predicate".
  • When you have the pattern (if ... (if ...)) it's usually clearer if you use cond.
  • No docstring!

Anyway, fixing all those minor niggles, and using labels, here's the result:

(defun insertion-sort (list &optional (predicate #'<))
  "Return a sorted copy of list. Optional argument predicate must be a function
that takes two items and returns true if they are in order."
  (labels ((insert (item list)
                   (cond ((null list) (list item))
                         ((funcall predicate item (car list))
                          (cons item list))
                         (t (cons (car list) (insert item (cdr list)))))))
    (and list (insert (car list) (insertion-sort (cdr list) predicate)))))

Notice that now that insert is local to insertion-sort, I don't have to pass the predicate argument to it, as the inner function picks up the binding from the enclosing context.

Upvotes: 3

Related Questions