Scheme sorting a list

Question

Okay so I am trying to take in a list and sort it from greatest to smallest.

Example:
> (maxheap (list 5 6 2 1 18 7))
;output:
> (18 7 6 5 2 1)

So here's what I got so far:

(define (mkmaxheap heaplist)
  (let ((max (mymax(heaplist))))
  ;mymax is a func that returns max number, it works

    (let (( head (car heaplist)) (tail (cdr heaplist)))
      (if (null? tail)
         newlist))))

Thats all I could get to compile, all the other code I wrote failed. Any help on solving this would be much appreciated.

Answer 1

You should articulate carefully the strategy that you want to use for producing the sorted list. Is it something like this?

• Find the maximum number in the list.
• Get the rest of the list except for the maximum.
• Sort the rest of the list, and put the maximum on the front of it.

This is not a very fast way to sort it, but it should work. The next step from your code will be to write a function to get the rest of the list except for the maximum (take care to handle it correctly if the list has duplicates.)

Once you have that written, you should be able to write Scheme code that looks more or less just like the outline above.

Answer 2

This is a merge sort algorithm in Common lisp. It's roughly close to implementing the same sort in scheme.

(defun merge-sort( input )
  (labels ((right-half ( input )
             (last input (ceiling (/ (length input) 2))))
           (left-half ( input )
             (ldiff input (right-half input ))))
    (if (or (null input) (null (cdr input))) 
        input 
        (merge 'list (merge-sort (left-half input)) (merge-sort (right-half input)) #'<))))

Answer 3

You need to decide what to use to sort the list. I've been tinkering about with scheme recently, working my way through SICP and the "Schemer" series, and I found it pretty easy to implement a bubble sort, merge sort, and quicksort in scheme.

Answer 4

You didn't specify the implementation you're using. But it may implement either r6rs list-sort or srfi-95 sort or any other built-in sorting. Check out your implementation's documentation.