Bubble Sorting in Scheme

问题:

I am writing a recursive code to Bubble Sort (smallest to largest by swapping)
I have a code to do the bubble sort just once

(define (bubble-up L)  
   (if (null? (cdr L))  
     L   
  (if (< (car L) (cadr L))  
(cons (car L) (bubble-up (cdr L)))  
(cons (cadr L) (bubble-up (cons (car L) (cddr L))))  
  )
 )  

if i put a list into this code, it returns the list with the largest number at the end
EX.. (bubble-up ' (8 9 4 2 6 7)) -> ' (8 4 2 6 7 9)

Now i am trying to write a code to do the (bubble-up L) N times (the number of integers in list)
I have this code:

  (define (bubble-sort-aux N L)   
    (cond ((= N 1) (bubble-up L))  
       (else (bubble-sort-aux (- N 1) L)  
  (bubble-up L))))  
(bubble-sort-aux 6 (list 8 9 4 2 6 7))  -> ' (8 4 2 6 7 9)

But the recursion doesn't seem to happen because it only sorts once!
Any suggestions would be welcome, i'm just stumped!

回答1:

Try this:

(define (bubble-sort-aux N L)   
  (cond ((= N 1) (bubble-up L))  
        (else (bubble-sort-aux (- N 1) (bubble-up L)))))  

If you keep "bubbling-up" the list N times it'll be sorted at the end. The problem with your code is that you weren't using the result of bubble-up for anything - but if we pass the value returned by bubble-up to the next call of the function, it'll eventually be sorted. Now the procedure works as expected:

(bubble-sort-aux 6 (list 8 9 4 2 6 7))
=> '(2 4 6 7 8 9)

回答2:

My implementation:

(define (bubble-swap ls)
  (if (null? (cdr ls))
      ls
      (if (> (car ls) (cadr ls))
          (cons (cadr ls) (bubble-swap (cons (car ls) (cddr ls))))
          (cons (car ls) (bubble-swap (cdr ls))))))

(define (len ls)
  (if (null? ls)
      0
      (+ 1 (len (cdr ls)))))

(define (bubblesort_ ls n)
  (if (= n 1)
      ls
      (bubblesort_ (bubble-swap ls) (- n 1))))

(define (bubblesort ls) (bubblesort_ ls (len ls)))

I implemented a custom len function but you can use standard length function, if available.