recursion - 用函数式语言实现快速排序

Question

我需要在 SML 中实现快速排序来完成家庭作业，但我迷失了。我以前不熟悉快速排序是如何实现的，所以我阅读了它，但我读到的每一个实现都是命令式的。这些看起来并不太难，但我不知道如何在功能上实现快速排序。

维基百科恰好有标准机器学习(这是我的作业所需的语言)的快速排序代码，但我不明白它是如何工作的。

维基百科代码:

val filt = List.filter
fun quicksort << xs = let
fun qs [] = []
 | qs [x] = [x]
 | qs (p::xs) = let
     val lessThanP = (fn x => << (x, p))
     in
       qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs))
     end
in
  qs xs
end

特别是，我不理解这一行:qs (filt lessThanP xs) @ p::(qs (filt (not o lessThanP) xs))。 filt 将返回 xs 中小于 p* 的所有内容的列表，该列表与 p 连接，后者对所有 >= p.* 进行 cons 编辑

*假设当 x < p 时 << (x, p) 函数返回 true。当然，不一定是这样。

实际上，输入这些内容可以帮助我理解正在发生的事情。不管怎样，我试图将该 SML 函数与 wiki 的快速排序伪代码进行比较，如下所示。

函数快速排序(数组, '左', '右')

  // If the list has 2 or more items
  if 'left' < 'right'

      // See "Choice of pivot" section below for possible choices
      choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'

      // Get lists of bigger and smaller items and final position of pivot
      'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')

      // Recursively sort elements smaller than the pivot
      quicksort(array, 'left', 'pivotNewIndex' - 1)

      // Recursively sort elements at least as big as the pivot
      quicksort(array, 'pivotNewIndex' + 1, 'right')

其中分区定义为

// left is the index of the leftmost element of the array
// right is the index of the rightmost element of the array (inclusive)
//   number of elements in subarray = right-left+1
function partition(array, 'left', 'right', 'pivotIndex')
  'pivotValue' := array['pivotIndex']
  swap array['pivotIndex'] and array['right']  // Move pivot to end
  'storeIndex' := 'left'
  for 'i' from 'left' to 'right' - 1  // left ≤ i < right
      if array['i'] < 'pivotValue'
          swap array['i'] and array['storeIndex']
          'storeIndex' := 'storeIndex' + 1
  swap array['storeIndex'] and array['right']  // Move pivot to its final place
  return 'storeIndex'

那么，分区到底发生在哪里？或者我是否错误地考虑了 SML 快速排序？

Answer 1

So, where exactly is the partitioning happening? Or am I thinking about SMLs quicksort wrongly?

快速排序的纯功能实现通过输入列表上的结构递归来工作(IMO，这值得一提)。此外，如您所见，对“filt”的两次调用允许您将输入列表划分为两个子列表(例如 A 和 B)，然后可以单独处理这两个子列表。这里重要的是:

• A 的所有元素都小于或等于主元元素(代码中的“p”)
• B 的所有元素都大于主元元素

命令式实现通过交换同一数组中的元素就地工作。在您提供的伪代码中，“partition”函数的后不变式是您有两个子数组，一个从输入数组的“left”开始(并以“pivotIndex”结束)，另一个从“pivotIndex”之后开始”并以“右”结尾。这里重要的是两个子数组可以看作子列表 A 和 B 的表示。

我认为现在您已经了解了分区步骤发生的位置(或者相反，命令式和函数式是如何相关的)。