Схема Вектор с использованием сортировки слиянием - PullRequest
Новая
       30

Схема Вектор с использованием сортировки слиянием

1 голос
/ 22 октября 2011

У меня есть вектор, элементы каждого вектора - это список, я хочу отсортировать элементы по длине списка. Я использую это для сортировки моего вектора, но я получил ошибку 

    (define vector-merge!
   (lambda (newvec vec left group-size vec-size)
      (let* ((top-left (min vec-size (+ left group-size)))
             (right top-left)
             (top-right (min vec-size (+ right group-size))))
         (let mergeloop ((left left) (right right) (i left))
              (cond ((and (< left top-left) (< right top-right))
                        (if (< (vector-ref vec left) (vector-ref vec right))
                       (begin
                          (vector-set! newvec i (vector-ref vec left)) 
                          (mergeloop (add1 left) right (add1 i)))
                       (begin
                          (vector-set! newvec i (vector-ref vec right)) 
                          (mergeloop left (add1 right) (add1 i)))))
                ((< left top-left)
                    (vector-set! newvec i (vector-ref vec left))
                    (mergeloop (add1 left) right (add1 i)))
                ((< right top-right)
                    (vector-set! newvec i (vector-ref vec right))
                    (mergeloop left (add1 right) (add1 i))))))))

  (define vector-mergesort!
   (lambda (orig-vec)
      (let* ((vec-size (vector-length orig-vec))
             (new-vec (make-vector vec-size)))
        ;; merge with successively larger group sizes
        (do ((group-size 1 (* group-size 2))    ;; loop variables
         (twice-size 2 (* twice-size 2))
         (count 1 (add1 count))
         (vec1 orig-vec vec2)
         (vec2 new-vec vec1))
        ((>= group-size vec-size)          ;;; exit condition
            (if (even? count)              ;;; copy to orig-vec, if needed
                    (do ((i 0 (add1 i)))   ;;; this do replaces 
                        ((>= i vec-size))  ;;; vector-change!
                        (vector-set! orig-vec i (vector-ref new-vec i)))))
        ;; successively merge next two groups
        (do ((left 0 (+ left twice-size)))    ;; loop variables
            ((>= left vec-size))              ;; exit when array processed
            (vector-merge! vec2 vec1 left group-size vec-size))))))



Error:
<: expects type <real number> as 1st argument, given: ((length (vector-ref route number))); other arguments were: ((length (vector-ref route number)))

1 Ответ

2 голосов
/ 22 октября 2011

Это выражение, которое сигнализирует об ошибке: 

(< (vector-ref vec left) (vector-ref vec right))

Функция <ожидает действительное число в качестве первого аргумента, но получила список.Поскольку ваш вектор vec содержит списки, выражение (vector-ref vec left) возвращает список (а не число).Поскольку вы хотите сортировать по длине списков, вам нужно написать: </p> 

(< (length (vector-ref vec left)) (length (vector-ref vec right)))

, чтобы сравнить длину списков вместо самих списков.

Примечание.Реализация схемы, скорее всего, имеет функцию векторной сортировки в своей библиотеке.В R6RS процедура называется vector-sort!: 

(vector-sort! proc vector)

, где proc - это процедура, используемая для сравнения двух элементов, а vector - вектор, который нужно отсортировать.

Таким образом, если вы определите: 

(define (compare list1 list2)
    (< (length list1) (length list2)))

Вы можете сортировать его таким образом 

(vector-sort! compare vector)
...