5
\$\begingroup\$

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?

\$\endgroup\$

migrated from stackoverflow.com May 2 '12 at 12:45

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ I think that find-shortest should be named find-smallest. \$\endgroup\$ – Dan D. May 2 '12 at 3:03
6
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ O(n^2) is pretty bad for sorting... \$\endgroup\$ – Matt Ball May 2 '12 at 4:11
  • \$\begingroup\$ It's not bad for short collections, even though insertion sort would be better. \$\endgroup\$ – Quentin Pradet May 2 '12 at 12:49
2
\$\begingroup\$
  • 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)))))))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.