クイックソート

数学的基礎とデータ構造 (アルゴリズムイントロダクション)のp140付近。

• クイックソートも分割統治のアルゴリズム
• A[q]で配列を2つの部分配列に分解、A[q]より大きいか小さいかで分解する
• 部分配列の中でもクイックソートする
• 全ての部分配列の中でソートされていて、部分配列間でもソートされていることが保証されているので、結合する必要がない

use strict;
use warnings;

sub quick_sort {
    my ($a, $p, $r) = @_;
    if ($p < $r) {
        my $q = &partition($a, $p, $r);
	&quick_sort($a, $p, $q -1);
	&quick_sort($a, $q + 1, $r);
    }
}

sub partition {
    my ($a, $p, $r) = @_;
    my $x = @$a[$r-1];
    my $i = $p - 1;
    foreach my $j (($p..$r-1)){
	if (@$a[$j-1] <= $x) {
	    $i++;
	    # swap
	    my $tmp = @$a[$i-1];
	    @$a[$i-1] = @$a[$j-1];
	    @$a[$j-1] = $tmp;
	}
    }
    # swap
    my $tmp = @$a[$i+1-1];
    @$a[$i+1-1] = @$a[$r-1];
    @$a[$r-1] = $tmp;
    return $i+1;
}

my @a = (1,5,1,7,2,6,9,2,1,4,5);
print "=" x 35, "\n";
print "before : [", join(",",@a), "]\n";
&quick_sort(\@a, 1, 11);
print "=" x 35, "\n";
print "after : [", join(",",@a), "]\n";

実行結果。

/tmp% perl quick_sort.pl
===================================
before : [1,5,1,7,2,6,9,2,1,4,5]
===================================
after : [1,1,1,2,2,4,5,5,6,7,9]