Sorting a List in a Schema

Question

I want to create a function that sorts a list. For example, I have this list:

x1, x2, x3 .... xn 

or

1, 2, 3, 4, 5, 6

I want to display numbers in the following order:

 x1, xn, x2, xn-1 

or

 1, 6, 2, 5, 3, 4 

Can you help me write this example?

Answer 1

Usually, when we talk about sorting, we refer to the ordering of elements according to some characteristic of the contents of the element, and not according to the position of the position in the list. I would call your situation a permutation, but perhaps some people may dispute this use. :-)

Here you can approach the problem:

• Divide the list in the middle (you can do this with the help of a turtle and a hare if you want to go through the list only once); call these lists head and tail if you want.
• Turn the tail list over and move it to the head list.

Another approach:

• Flip the original pairs (let it be called rev ).
• Move the source list with rev , keeping track of each item passed. When they meet in the middle, stop.

Here's a second approach (you need to load SRFI 1 ):

 (define (zippy lst) (if (null? lst) '() (let recur ((lst lst) (rev (pair-fold cons '() lst))) (cond ((eq? lst (car rev)) (list (car lst))) ((eq? (cdr lst) (car rev)) (list (car lst) (caar rev))) (else (cons* (car lst) (caar rev) (recur (cdr lst) (cdr rev)))))))) 

Answer 2

This is not a sort operation, more like a shuffle; here is another way to solve it. First, define an interleave procedure that alternates between two lists, returning a single list:

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

Now we take the initial list and split-at in the middle (this is the procedure corresponding to Racket); finally, we alternate the two resulting lists, reversing the tail:

 (define (zippy lst) (let-values (((head tail) (split-at lst (quotient (length lst) 2)))) (interleave head (reverse tail)))) 

The above IMHO implementation is a little intuitive, and if you work with Racket, it does not require external libraries. It works as expected:

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