Raku 中的快速排序

Sun Jun 23, 2019

今天，我们来看看另一个，也许是最着名的数据排序方法，快速排序。

该算法要求您选择所谓的枢轴，其中一个元素来自数据，并将其余部分分成两部分：小于枢轴的元素，以及大于或等于枢轴的元素。然后再次递归地对每个部分进行排序。在每次迭代中，部件变得越来越小，直到子列表是一个或甚至零个元素的平凡数据集。

一个单独的理论是如何选择正确的枢轴。有几种方法，例如，从列表中间取值，或取第一项，或最后一项，或随机项。还有更复杂的方法，您可以调整它以在您的数据集类型上实现最佳性能。

为简单起见，让我们选择第一个元素作为轴点，这是代码

sub quick-sort(@data) {    
    return @data if @data.elems <= 1;

    my $pivot = @data[0];

    my @left;
    my @right;

    for @data[1..*] -> $x {
        if $x < $pivot {
            push @left, $x;
        }
        else {
            push @right, $x;
        }
    }

    return flat(quick-sort(@left), $pivot, quick-sort(@right));
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
@data = quick-sort @data;
say @data;

与之前的冒泡排序示例不同，此程序不会就地排序，而是返回新列表。

现在是时候将代码转换为更具 Raku 风格代码的时候了。

Multi-subs 再次来救援，在增加代码行数的同时，使整个算法在第一眼更容易捕捉到:

multi sub quick-sort(@data where @data.elems <= 1) {
    return @data;
}

multi sub quick-sort(@data where @data.elems > 1) {
    my $pivot = @data[0];

    . . .
}

现在，看看这两部分：

my $pivot = @data[0];

. . .

for @data[1..*] -> $x {

需要采用第一个元素，算法的其余部分仅处理列表的其余部分。目前，这是通过获取元素和切片来实现的，但是有一种切换方法可以完全满足我们的需要，并从数据中删除元素。所以，让我们使用它

my $pivot = @data.shift;

. . .

for @data -> $x {

接下来是 if-else 选择，可以有效地（尽管可能效率稍差）用两个 grep 替换：一个选择枢轴之前的部分，另一个选择其余部分。

my @left = @data.grep(* < $pivot);
my @right = @data.grep(* >= $pivot);

基本上就是这样。你还可以做的是摆脱临时变量并将过滤器放到 return 语句中

return flat(
    quick-sort(@data.grep(* < $pivot)),
    $pivot,
    quick-sort(@data.grep(* >= $pivot))
);

这一切都在最后一次改变之前发挥作用，但现在已经 broken 了：

$ raku quick-sort.pl 
Cannot call 'pop' on an immutable 'List'
   in sub quick-sort at 3.pl line 6
   in sub quick-sort at 3.pl line 8
   in block <unit> at 3.pl line 12

问题是你需要返回一个数字列表，但每个快速排序子类都返回它自己的列表。

您可以通过在函数参数之前放置*来啜饮元素来轻松解决问题

multi sub quick-sort(*@data where @data.elems > 1) {
    . . .

最终代码如下所示：

multi sub quick-sort(*@data where @data.elems <= 1) {
    return @data;
}

multi sub quick-sort(*@data where @data.elems > 1) {
    my $pivot = @data.shift;

    return flat(
        quick-sort(@data.grep(* < $pivot)),
        $pivot,
        quick-sort(@data.grep(* >= $pivot))
    );
}

您也可以使用 | 来独立平展每个列表，而不是使用 flat 例程：

return
    |quick-sort(@data.grep(* < $pivot)),
    $pivot,
    |quick-sort(@data.grep(* >= $pivot));

但我认为有两个可理解的中间变量以避免标点符号噪音仍然更好：

multi sub quick-sort(@data where @data.elems <= 1) {
    return @data;
}

multi sub quick-sort(@data where @data.elems > 1) {
    my $pivot = @data.shift;

    my @left = @data.grep(* < $pivot);
    my @right = @data.grep(* >= $pivot);

    return flat(quick-sort(@left), $pivot, quick-sort(@right));
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
@data = quick-sort @data;
say @data;

作为家庭作业，创建快速排序算法的实现，该算法可就地对数据进行排序。

该代码可在 GitHub 上获得，欢迎您加入此旅程！

原文：https://raku.online/2019/06/23/101-quick-sort-in-perl-6/