氣泡排序與計劃

我正在努力在Scheme中實現氣泡排序算法，我必須說，編程的功能方式是一個奇怪的概念，我正在努力一點點來掌握它。氣泡排序與計劃

我已經成功地創建了一個函數，它會冒出我們遇到的第一大值，但這就是它所做的一切。

(bubbleH '(5 10 9 8 7)) 
(5 9 8 7 10)

我正在努力完成循環遍歷列表所需的幫助程序功能，直到沒有交換爲止。

這是我到目前爲止的地方，顯然這是不正確的，但我認爲我走在正確的軌道上。我知道我可以自己傳遞列表中的元素數量，但我正在尋找一種與此不同的解決方案。

(define bubbaS 
    (lambda (lst) 
    (cond ((= (length lst) 1) (bubba-help lst)) 
     (else (bubbaS (bubba-help lst))))))

來源

2014-02-17 Talen Kylon

分享到目前爲止已經實施的內容，並呼籲您試圖進一步塑造它。 – J0e3gan

[Bubble Sorting in Scheme]可能的重複（http://stackoverflow.com/questions/19260784/bubble-sorting-in-scheme） – J0e3gan

我的問題與你所鏈接的不同，我不想通過元素的數量作爲參數。我想我應該加入！ –

在possible-duplicate SO question我使用bubble-up和bubble-sort-aux實現參考...

(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))))))) 

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

...，這是簡單的語法糖：

(define (bubbleH L) 
    (bubble-sort-aux (length L) L))

隨着語法糖添加，你應該讓你在你的問題中指定正是最後一位：

(bubbleH '(5 10 9 8 7)) 
=> (5 7 8 9 10)

你可以用上面的東西修補一下repl.it session我保存了&共享。

來源

2014-02-18 00:16:53 J0e3gan

這是我自己的尾遞歸版本。

內部函數會像您的bubbleH程序一樣冒出最大數量。但是，而不是返回一個完整列表，它會返回2個值：

未排序的休息名單
已經冒泡

如最大值：

> (bsort-inner '(5 1 4 2 8)) 
'(5 2 4 1) 
8 
> (bsort-inner '(1 5 4 2 8)) 
'(5 2 4 1) 
8 
> (bsort-inner '(4 8 2 5)) 
'(5 2 4) 
8

現在外循環只需要cons返回的第二個值，並在剩餘列表上進行迭代。

代碼：

(define (bsort-inner lst) 
    (let loop ((lst lst) (res null)) 
    (let ((ca1 (car lst)) (cd1 (cdr lst))) 
     (if (null? cd1) 
      (values res ca1) 
      (let ((ca2 (car cd1)) (cd2 (cdr cd1))) 
      (if (<= ca1 ca2) 
       (loop cd1 (cons ca1 res)) 
       (loop (cons ca1 cd2) (cons ca2 res)))))))) 

(define (bsort lst) 
    (let loop ((lst lst) (res null)) 
    (if (null? lst) 
     res 
     (let-values (((ls mx) (bsort-inner lst))) 
      (loop ls (cons mx res))))))

對於遞歸版本，我更喜歡一個其中最小值氣泡在前面：

(define (bsort-inner lst) 
    ; after one pass, smallest element is in front 
    (let ((ca1 (car lst)) (cd1 (cdr lst))) 
    (if (null? cd1) 
     lst ; just one element => sorted 
     (let ((cd (bsort-inner cd1))) ; cd = sorted tail 
      (let ((ca2 (car cd)) (cd2 (cdr cd))) 
      (if (<= ca1 ca2) 
       (cons ca1 cd) 
       (cons ca2 (cons ca1 cd2)))))))) 

(define (bsort lst) 
    (if (null? lst) 
     null 
     (let ((s (bsort-inner lst))) 
     (cons (car s) (bsort (cdr s))))))

來源

2014-02-18 00:15:05 uselpa

氣泡排序與計劃

回答

相關問題