Как я могу исправить мою реализацию quicksort?

Question

Вот моя попытка реализовать быструю сортировку:

(define (sublist ls start stop middle) 
(cond ((null? ls) ls) 
    ((< middle start) (sublist (cdr ls) start stop (+ middle 1))) 
    ((> middle stop) '()) 
    (else 
     (cons (car ls) (sublist (cdr ls) start stop (+ middle 1)))))) 

(define (split5 ls)          
    (let ((len (length ls))) 
    (cond ((= len 0) (list ls ls)) 
     ((= len 1) (list ls '())) 
     (else 
      (list (sublist ls 1 (/ len 2) 1) 
       (sublist ls (+(/ len 2)1) len 1)))))) 

;this divides the sorted list into two sublists 
(define (dividelist rel? ls) 
(split5 (order rel? ls))) 


(define (quicksort rel? ls) 
(if (null? (cdr ls)) ls 
    (let ((pivot (list-ref (sort rel? ls) (round (/ (length (sort rel? ls)) 2)))) 
     (left (car (dividelist rel? ls))) 
     (right (cdr (dividelist rel? ls)))) 
     (join left pivot right)))) 

Я знаю, что эта реализация очень неэффективно, но я не могу придумать способ сделать это. Во всяком случае, это не работает.

When I input this: 
(quicksort < '(9 3 -5 8 -7 2 9)) 
It gives me this: 
(-7 -5 2 8 (8 9 9)) 
It should give me this: 
(-7 -5 2 3 8 9 9) 

Как это исправить?

EDIT

(define (join ls1 goo ls2) 
    (if (null? ls1) (cons goo ls2) 
     (if (null? ls2) (cons goo ls1) 
      (cons (car ls1) (join (cdr ls1) goo ls2))))) 

Answer 1

Предполагая, что order процедуры такой же, как sort процедуры используется несколько строк ниже в коде (ждать, вы используете сортировочные процедуры для реализации процедуры сортировки ?!) и что join является своего рода append, я могу заключить, что проблема со списком создается в вашей реализации join. Измените его на это исправить:

(define (join left pivot right) 
    (append* left (list pivot) right)) 

Теперь процедура возвращает список , как следует:

(quicksort < '(9 3 -5 8 -7 2 9)) 
=> '(-7 -5 2 8 8 9 9) 

Оп, откуда число 3 идти? В вашем коде есть ошибка, вам придется его найти! Подсказка: код для вычисления стержня ужасно ошибочен.

EDIT

Вот правильно, без проблем реализации QuickSort. Обратите внимание на то, что в простой реализации, как этого достаточно, чтобы выбрать первый элемент в качестве шарнира:

(define (quicksort cmp lst) 
    (if (null? lst) 
     '() 
     (let ((x (car lst)) 
      (xs (cdr lst))) 
     (append (quicksort cmp (filter (lambda (e) (cmp e x)) xs)) 
       (list x) 
       (quicksort cmp (filter (lambda (e) (not (cmp e x))) xs)))))) 

или немного любителя и короче, с использованием процедур высшего порядка ракетки в:

(define (quicksort cmp lst) 
    (if (empty? lst) 
     empty 
     (let ((x (first lst)) 
      (xs (rest lst))) 
     (append (quicksort cmp (filter-not (curry cmp x) xs)) 
       (cons x (quicksort cmp (filter (curry cmp x) xs))))))) 

Еще одна возможности, используя partition, чтобы получить оба раздела (элементы перед стержнем и элементы после поворота) в одну стадию - это более эффективный:

(define (quicksort cmp lst) 
    (if (empty? lst) 
     empty 
     (let-values (((greater-than less-equal) 
        (partition (curry cmp (first lst)) (rest lst)))) 
     (append (quicksort cmp less-equal) 
       (cons (first lst) (quicksort cmp greater-than)))))) 

В любом случае, он работает так, как ожидалось:

(quicksort < '(9 3 -5 8 -7 2 9)) 
=> '(-7 -5 2 3 8 9 9)