How to sort a list of riots in a schema

Question

How can I sort a list with values ​​in a schema? For example, I have values ​​that are not ordered:

x1, x5, x32 .... xn 

or

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

First, I want to increase the number for them and display them in the following order:

 x1, xn, x2, xn-1 

or

 1, 6, 2, 5, 3, 4 

Any help would be helpful.

Answer 1

This is the same question that you posted before , but with a slight twist. As I told you in my comments, you just need to sort the list before rearranging it. Here's the 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 2

This R6RS solution does what Chris Jet-Young offers, and it really is the way it is done badly. BTW Chris and Óscar solutions on the same issue without sorting outperform 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))) 

Answer 3

Here is a simple, tail-recursive approach that uses the slow / fast method to stop recursion when half the list has been 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 4

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

First, we define the select1 function, which receives the minimum (or maximum) element, followed by all other elements. For linked lists, this is probably the easiest 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 weaving:

 (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²), while the sorting and rotation approach recommended by everyone else is O (n log n).