Bubble Sort from Lab [ pt extra credit]

Note that you are only allowed to use the following LISP functions: defun, cond, car, cdr, list, cons, append, >, <, >=, <=, = and null. (DO NOT USE set or setq.)

To implement a bubble sort we started developing the code in lab. I designed a recursive solution that used two functions: sort and bubbleUp. I implemented the latter in lab (code below). Note I used color to help differentiate the if parts of the conditional from the then parts.

(defun bubbleUp (n)

(cond

((null n) nil)

((null (cdr n)) n)

((> (car n) (car (cdr n)))

(append (list (car (cdr n))) (bubbleUp (cons (car n) (cdr (cdr n))))))

(T (append (list (car n)) (bubbleUp (cdr n))))

)

Your job is to write the sort that uses bubbleUp:

(defun sort (n)

???

)

A call to sort will output the following:

> (sort (5 4 3 2 1)) > (1 2 3 4 5)

> (sort (6 4 3 9 8))

> (3 4 6 8 9)

A hint about what goes in ???. You cannot simply call bubbleUp n number of times since you dont know n (yes it works on the command line but thats because you know how many times to call it). So you likely have to check for an empty list in order to stop. This usually means a cond of the form in bubbleUp that checks for a null list, etc. The meat of the sort will be one of the conditional clauses where you have to call bubbleUp with the list, minus the last item. So in LISP its easy to get the first (car) and all-but-the first (cdr) item but not as easy to get the last item (you have to do a bit of thinking for this).