# 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

\$
```