How to sort disorder list of numbers in scheme

Question

What it the proper way to sort a list with values in Scheme? For example I have the values which are not ordered:

x1, x5, x32 .... xn

or

3, 4, 1, 3, 4, .. 9

First I want to for them by increase number and display them in this order:

x1, xn, x2, xn-1

or

1, 6, 2, 5, 3, 4

Any help will be valuable.

Answer 1

So, you don't mind slow and just want a selection-based approach, eh? Here we go....

First, we define a select1 function that gets the minimum (or maximum) element, followed by all the other elements. For linked lists, this is probably the simplest approach, easier than trying to implement (say) quickselect.

(define (select1 lst cmp?)
  (let loop ((seen '())
             (rest lst)
             (ext #f)
             (extseen '()))
    (cond ((null? rest)
           (cons (car ext) (append-reverse (cdr extseen) (cdr ext))))
          ((or (not ext) (cmp? (car rest) (car ext)))
           (let ((newseen (cons (car rest) seen)))
             (loop newseen (cdr rest) rest newseen)))
          (else
           (loop (cons (car rest) seen) (cdr rest) ext extseen)))))

Now actually do the interweaving:

(define (zippy lst)
  (let recur ((lst lst)
              (left? #t))
    (if (null? lst)
        '()
        (let ((selected (select1 lst (if left? < >))))
          (cons (car selected) (recur (cdr selected) (not left?)))))))

This approach is O(n²), whereas the sort-and-interleave approach recommended by everybody else here is O(n log n).

Answer 2

Here is a simple, tail-recursive approach that uses a 'slow/fast' technique to stop the recursion when half the list is traversed:

(define (interleave l)
  (let ((l (list-sort < l)))
    (let merging ((slow l) (fast l) (revl (reverse l)) (rslt '()))
      (cond ((null? fast)
             (reverse rslt))

            ((null? (cdr fast)) 
             (reverse (cons (car slow) rslt)))

            (else
             (merging (cdr slow) (cddr fast) (cdr revl)
                      (cons (car revl) (cons (car slow) rslt))))))))

Answer 3

This is the same question you posted before, but with a small twist. As I told you in the comments of my answer, you just have to sort the list before rearranging it. Here's a Racket solution:

(define (interleave l1 l2)
  (cond ((empty? l1) l2)
        ((empty? l2) l1)
        (else (cons (first l1)
                    (interleave l2 (rest l1))))))

(define (zippy lst)
  (let-values (((head tail) (split-at
                             (sort lst <) ; this is the new part
                             (quotient (length lst) 2))))
    (interleave head (reverse tail))))

It works as expected:

(zippy '(4 2 6 3 5 1))
=> '(1 6 2 5 3 4)

Answer 4

This R6RS solution does what Chris Jester-Young proposes and it really is how to do it the bad way. BTW Chris' and Óscar's solutions on the same question without sorting is superior to this zippy procedure.

    #!r6rs
    (import (rnrs base)
            (rnrs sorting)) ; list-sort

    (define (zippy lis)
      (let loop ((count-down (- (length lis) 1))
                 (count-up 0))
        (cond ((> count-up count-down) '())
              ((= count-up count-down) (cons (list-ref lis count-down) '()))
              (else (cons (list-ref lis count-down)
                          (cons (list-ref lis count-up)
                                (loop (- count-down 1)
                                      (+ count-up 1))))))))
    (define (sort-rearrange lis)
      (zippy (list-sort < lis)))