Sorting a list of numbers in increasing order

Question

Here's a program I wrote to sort a list of numbers in increasing order (without using inbuilt sort function).

(define (sort-list l)
 (define first-element (if (not (null? l)) (car l) 0))
 (cond ((null? l) (quote ()))
 (else (cons (find-shortest l first-element) (sort-list (remove-member l (find-shortest l first-element)))))))
(define find-shortest
 (lambda (tl b)
 (cond ((null? tl) b)
 ((< (car tl) b) (set! b (car tl)) (find-shortest (cdr tl) b))
 (else (find-shortest (cdr tl) b)))))
(define remove-member
 (lambda (tl2 a)
 (cond ((null? tl2) (quote ()))
 ((= a (car tl2)) (cdr tl2))
 (else (cons (car tl2) (remove-member (cdr tl2) a))))))

It works, but I know it's very badly written. It has way too many recursions than what's necessary. Can someone suggest ways to make this code better?

• Dan D.: I think that find-shortest should be named find-smallest.

Answer 1

What you've written is called "selection sort", and it works fine. It's not the best sort, but it's not bad, either. It's one of a class called "n^2" sorts, because it generally runs in time proportional to the square of the length of the list.

Selection sort is a somewhat painful sort to write in a recursive style, because removing an element from a list is not so natural.

You can make it look a smidgen more natural if you rebuild the list on the way back out after removing it. However, the second pass over the list (as you've written it) does not change the asymptotic running time; it's still "order n-squared".

One note: you gain nothing by mutating "b" in the body of "find-shortest." Instead, replace

(set! b (car tl)) (find-shortest (cdr tl) b)

with

(find-shortest (cdr tl) (car tl))

... to make your code shorter and cleaner.

Also, If you were in my class, I would ask you for purpose statements and test cases. :)

• Matt Ball: O(n^2) is pretty bad for sorting...
• Quentin Pradet: It's not bad for short collections, even though insertion sort would be better.

Answer 2

• Within the sort-list function, you can just use (car l) in-place of first-element because your first cond clause ensures that in the remaining clauses, l is not null

• Also in sort-list You call (find-shortest l first-element) twice. You could bind the result of this call once and save one call into find-shortest

Taking those two points and @Dan D.'s point about renaming find-shortest to find-smallest this is how my sort-list would look

(define (sort-list l)
 (cond ((null? l) '()) ; or (quote ()) - whichever you prefer
 (else (let ((smallest (find-smallest l (car l))))
 (cons smallest
 (sort-list (remove-member l smallest)))))))