1
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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 (+/- missing parens)

(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 elem 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.

\$\endgroup\$
  • \$\begingroup\$ +1, thanks. I had realised that i wanted to switch the cdr of the list and the car of the list, but couldn't figure out how to do it. I had not realised that it failed as (list? (car numList)) is #f, and that i could fix it with (list (car numList)). I do not have a remove-elem function, so i'll have to write that. \$\endgroup\$ – ricardo Oct 29 '13 at 20:38
  • \$\begingroup\$ i made a crude remove-elem function -- and asked a follow up question about it. thanks for your help. \$\endgroup\$ – ricardo Oct 29 '13 at 22:19

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.