diminishing gap sort


Write a function accepting an integer list l and returning pl, a permutation of l. The ith element in pl has the ith largest gap among the elements in pl.

 $ cat dgs.rkt 
 #lang racket 
  
 (require rnrs/sorting-6 rackunit "utl.rkt") 
   
 (define (dgs l) 
  
   ; Return a premutation pl of the integer list l.  The integers 
   ; in pl are sorted by decreasing gap size.  The gap of the ith 
   ; element e in pl is the difference between e and e's successor 
   ; when l is sorted in decreasing order.  The last element in pl 
   ; has gap 0. 
   
   (define (deltas v) 
  
     ; Return vector d.  d[i] = v[i] - v[i + 1] but 
     ; d[n - 1] = 0, n = |v|. |v| > 0 assumed. 
  
     (let* 
  
       ((n (vector-length v)) 
        (d (make-vector n))) 
        
       (vector-set! d (- n 1) 0) 
       (do ((i (- n 2) (- i 1))) ((< i 0) d) 
         (vector-set! d i 
           (- (vector-ref v i) (vector-ref v (+ i 1))))))) 
  
   (let* 
  
     ((v (vector-sort > (list->vector l)))) 
         
     (vector->list 
       (vector-map car 
        (vector-sort 
          (lambda (a b) (> (cdr a) (cdr b))) 
          (vector-map cons v (deltas v))))))) 
  
  
 (let ((l '(5 12 14 15 80 121 134 144 256)) 
       (gs '(256 80 121 134 144 12 14 15 5))) 
   (check-equal? (dgs l) gs)) 
  
 (do ((i 1 (+ i 1))) ((> i 10)) 
   (let ((f (fibonacci i))) 
     (check-equal? (dgs (permute-list f)) (reverse f)))) 
  
 $ mzscheme dgs.rkt 
  
 $