Scheme：实现快速排序 [英] Scheme: Implementing a Quick-Sort
问题描述
我试图用方案实现一个快速排序，这里有一些帅哥已经帮我修正了我的 split 函数，现在我要求你帮忙把所有东西到一个工作的算法。
这是我的代码到目前为止：
pre $ （定义快速排序（lambda（lst）
（define pivot（lambda（lst）
（if（null？lst）
null
（car lst ））））
（define split（helper）（lambda（lst pivot）ls1（define lst1 null）
（define lst2 null）
lst2）
（if（null？lst）
（list lst1 lst2）
如果（<=（car lst）pivot）
（split-helper（cdr lst）pivot（cons（car lst）lst1）lst2）
（split-helper（cdr lst）pivot lst1 cons（car lst）lst2））））））
（split-helper lst pivot lst1 lst2）））
（if（null？ lst）
null
（append（quick-sort（car（split lst（pivot lst））））（quick-sort（cdr（split lst（pivot lst））））））））
正如你所看到的，我选择了pivot作为列表中的第一个元素，我遇到的问题是，当数据透视表是列表中最小的元素时，程序会进入无限循环，因为它会让程序一遍又一遍地选择相同的透视图。
<另外，它的当前实现方式使得它非常低效，因为使用相同的
lst split 函数两次$ c>在每一次 quick-sort 中的执行情况，但是我没有足够好的控制Scheme来写它。 我在Scheme中看到了一些关于Quick-Sort的帖子，但它们的实现有点不同，我宁愿尝试纠正我自己的实现，而不是复制其他一些老兄的工作。
谢谢。
删除过多的lambdas，别名，绑定，并重新格式化，但没有更改或注释语义（Sylwester已经指出了该错误）：
（define（quick-sort lst）
（define（pivot lst）
（if（null？lst）
'（）
（car lst）））
（define（split lst pivot）
（let split-helper（（lst lst）;命名为let而不是内部
（lst1'（））;定义
（lst2'（） ））
（if（null lst）
（cons lst1 list2）
（if（<=（car lst）pivot）
（split-helper（cdr lst）
（cons（car lst）lst1）
lst2）
（拆分帮手（cdr lst）
lst1
（cons（car lst）lst2））））））
（if（null？ ls）
'（）
（let（（spl（split lst（pivot lst））））; [split]
（append（quick-sort（car spl））
（quick-sort（cdr spl）））））
尝试实现分区：
（定义（分区预测xs）
（让（'ps'（））（ns'（））;初始正值ps和负值ns`
（xs 'xs））
（if（null？xs'）
（cons ps ns）;返回列表
（let（（x（car xs'）））; （部分ps（cons x ns））（cdr xs'）部分（cons x ps）ns（cdr xs'））
（如果（pred x）
））））））
（define（quicksort xs）
（if（null？xs）'（）
（let *（（x（car xs））
（pn（partition; Memoization of`partition`
（lambda（x'）
（< x'x））
（cdr xs））））
（append（quicksort（car pn））;从
（list x）中提取正数; Pivot
（quicksort （cdr pn））））））;负数
（显示
（quicksort（list 4 2 3 5 1）））; （1 2 3 4 5）
部分在Scheme等严格的语言中效率低下;它会为每个递归步骤复制它的所有三个参数。通常，像过滤器和 map 这样基本的 folds 这样简单的公式是最有效的。使用过滤器：
<$ c $ （$ x $）$（$ x $）$（b $ x $）$（b $ x $） b $ b $（b $ b $（$）
（$ x $ b $ $ $ $ $ $ b（quicksort
（filter（lambda（x'）
（> = x'x））
xs'））））））
这个策略在函数式语言中恰好可以简短地表达出来。
在懒惰的Haskell中，单次遍历的
分区实际上比过滤器更有效两次。select ::（a - > Bool） - > （[a]，[a]） - > a - > （[a]，[a]）
select pred（ps，ns）x | pred x =（x：ps，ns）
|否则=（ps，x：ns）
分区::（a - > Bool） - > [a] - > （[a]，[a]）
分区pred = foldl（select pred）（[]，[]）
quicksort :: Ord a => [a] - > [a]
quicksort [] = []
quicksort（x：xs）= let（lt，gt）=分区（< x）xs
在quicksort中lt ++ [x] ++ quicksort gt
I'm trying to implement a quick sort using scheme, some dudes here already helped me fixing my split function and now I'm asking for you help with combining everything into one working algorithm.
Here is my code so far:
(define quick-sort (lambda (lst)
(define pivot (lambda (lst)
(if (null? lst)
null
(car lst))))
(define split (lambda (lst pivot)
(define lst1 null)
(define lst2 null)
(define split-helper (lambda (lst pivot lst1 lst2)
(if (null? lst)
(list lst1 lst2)
(if (<= (car lst) pivot)
(split-helper (cdr lst) pivot (cons (car lst) lst1) lst2)
(split-helper (cdr lst) pivot lst1 (cons (car lst) lst2))))))
(split-helper lst pivot lst1 lst2)))
(if (null? lst)
null
(append (quick-sort (car (split lst (pivot lst)))) (quick-sort (cdr (split lst (pivot lst))))))))
As you can see, I'm choosing the pivot to simply be the first element in the list, the problem I'm facing is that the program ran into an infinite loop when the pivot is the smallest element in the list because it makes the program choose the same pivot over and over.
Also, the way it's currently implemented makes it be really un-efficient because the split function is called twice with the same lst in every ineration of quick-sort but I just don't have good enough control over Scheme to write it any other way.
I saw some posts about Quick-Sort in Scheme but they were implemented a bit different and I rather try and correct my own implementation than copying some other dude's work.
Thank you.
Removed excessive lambdas, aliases, bindings, and reformatted, but didn't change or annotate semantics (Sylwester already pointed out the bug):
(define (quick-sort lst)
(define (pivot lst)
(if (null? lst)
'()
(car lst) ))
(define (split lst pivot)
(let split-helper ((lst lst) ; Named let instead of internal
(lst1 '()) ; definition
(lst2 '()) )
(if (null? lst)
(cons lst1 list2)
(if (<= (car lst) pivot)
(split-helper (cdr lst)
(cons (car lst) lst1)
lst2)
(split-helper (cdr lst)
lst1
(cons (car lst) lst2) )))))
(if (null? lst)
'()
(let ((spl (split lst (pivot lst)))) ; Memoization of the `split`
(append (quick-sort (car spl))
(quick-sort (cdr spl)) ))))
I think you're trying to implement a partition:
(define (partition pred xs)
(let part ((ps '()) (ns '()) ; Initial "positives" `ps`, and "negatives" `ns`
(xs' xs) )
(if (null? xs')
(cons ps ns) ; Returning pair of lists
(let ((x (car xs'))) ; Memoization of `(car lst)`
(if (pred x)
(part (cons x ps) ns (cdr xs'))
(part ps (cons x ns) (cdr xs')) )))))
(define (quicksort xs)
(if (null? xs) '()
(let* ((x (car xs))
(pn (partition ; Memoization of `partition`
(lambda (x')
(< x' x) )
(cdr xs) )))
(append (quicksort (car pn)) ; Extracting positives from pair
(list x) ; Pivot
(quicksort (cdr pn)) )))) ; Negatives
(display
(quicksort (list 4 2 3 5 1)) ) ; (1 2 3 4 5)
part is inefficient in strict languages like Scheme; it copies all three of its arguments for every recursive step. Often, straightforward formulations in terms of basic folds like filter and map are most efficient. A much more efficient implementation using filter:
(define (quicksort xs)
(if (null? xs) '()
(let ((x (car xs))
(xs' (cdr xs)) )
(append (quicksort
(filter (lambda (x')
(< x' x) )
xs'))
(list x)
(quicksort
(filter (lambda (x')
(>= x' x) )
xs'))))))
This strategy famously happens to be very briefly expressible in functional languages.
In lazy Haskell, a single-traversal partition is actually more efficient than filtering twice.
select :: (a -> Bool) -> ([a], [a]) -> a -> ([a], [a])
select pred (ps, ns) x | pred x = (x : ps, ns)
| otherwise = (ps, x : ns)
partition :: (a -> Bool) -> [a] -> ([a], [a])
partition pred = foldl (select pred) ([], [])
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x : xs) = let (lt, gt) = partition (< x) xs
in quicksort lt ++ [x] ++ quicksort gt
这篇关于Scheme：实现快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
