sorting a numerical list using basic scheme

Question

I would like some feedback on the appropriate way of ordering a numerical list using the most elementary scheme functions (sorry, i realise that elementary is not well defined).

By way of background: I've been learning a bit of scheme on my ipad, where I have only a basic implementation -- this is a nice challenge as much as a problem, as i have to figure out simple things like sorting a list for myself.

In doing this, i learnt that (append (cdr list) (car list)) is not what you might expect -- which is how i had originally wanted to implement this simple sort.

To hack around it, i discovered list-tail and reverse -- see the else clause below.

(define ra-sort
  (lambda (numList)
    (cond
      ((null? numList) '())
      ((= (car numList) (apply max numList))
       (cons (car numList) (ra-sort (cdr numList))))
      (else (ra-sort (append (list-tail numList (- (length numList) 1))
                             (reverse (list-tail (reverse numList) 1)))))
      )))

(define a '(99 1 6 12 101 2 67 -3))

> (ra-sort a)
(101 99 67 12 6 2 1 -3)

Now this seems to work, but all this repeated calling of reverse seems inefficient -- how should it be done?

Or am i missing something? Is it possible to make things work with the output of (append (cdr a) (car a))?

what does the notation even mean in (1 6 12 101 2 67 -3 . 99)? and how is it useful?

Answer 1

So to answer your specific question, yes you can greatly simplify your algorithm in a couple places:

(list-tail numList (- (length numList) 1))

So you're taking the last n - 1 elements of a list of length n? That's exactly:

(cdr numList)

As for this part:

(reverse (list-tail (reverse numList) 1))

So the list-tail will return a list of size 1, so you can drop the outer-most reverse entirely. Secondly, what are you getting here? Just the first element right? Which is to say...

(car numList)

So putting that together, we end up with this:

(define ra-sort
  (lambda (numList)
    (cond
      ((null? numList) '())
      ((= (car numList) (apply max numList))
          (cons (car numList) (ra-sort (cdr numList))))
          (else (ra-sort (append (cdr numList) (list (car numList))))
      ))))

Ok so now think about this algorithm. At each iteration, we're checking if the head is in the right place, if it is we go to the next element, else we rotate the whole array. Checking if the first element is the max takes O(n) time. We expect to have to do this O(n) times per element, for every element... so we end up with O(n^3).

A simple insertion sort, which is what I think you're trying to implement, should be only O(n^2). So try to redo your algorithm so that instead of just checking if the first element is the maximum one, you actually find it. So your inner clause would be something like:

(cons maxElem                               # largest element
    (ra-sort (remove-elem numList maxElem)) # + rest of list
)

That'll get you to where you want to be. At least for this sorting algorithm.