メメメモモ

プログラミング、筋トレ、ゲーム、etc

クイックソート

クイックソートを行なうプログラムをperlで書きました。

use strict;
use warnings;

{
    my @a = qw/3 2 0 5 8 3 4 1 3 2/;
    print join(',',@a) . "\n";
    print "===================\n";
    print join(',',sort(@a)) . "\n";
}


sub pivot {
    my ($ar, $i, $j) = @_;
    my @a = @$ar;
    my $k = $i + 1;
    while ($k <= $j && $a[$i] == $a[$k]) { $k++; }
    return -1 if($k > $j);
    return $i if($a[$i] >= $a[$k]);
    return $k;
}


sub partition {
    my ($ar, $i, $j, $x) = @_;
    my @a = @$ar;

    my $l = $i;
    my $r = $j;

    while ($l <= $r) {
        while ($l <= $j && $a[$l] < $x) { $l++; }
        while ($r >= $i && $a[$r] >= $x) { $r--; }

        last if($l > $r);
        my $t = $a[$l];
        $a[$l] = $a[$r];
        $a[$r] = $t;
        $l++; $r--;
    }
    return ($l,\@a);
}


sub quick_sort {
    my ($a, $i, $j) = @_;
    return if($i == $j);
    my $p = pivot($a, $i, $j);
    if ($p != -1) {
        my $k;
        ($k,$a) = partition($a, $i, $j, $a->[$p]);
        $a = quick_sort($a, $i, $k-1);
        $a = quick_sort($a, $k, $j);
    }

    return $a;
}


sub sort {
    my @a = @_;
    my $length = @a;
    my $new_a = quick_sort(\@a,0,$length);
    return @$new_a;
}


クイックソートは最も高速なソートアルゴリズムと言われています。(O(NlogN))
ただし、安定していないアルゴリズムなので、データによっては高速ではない場合があります(最悪O(N^2))


アルゴリズムとしては、まず基準となる値を配列の中から選びます(pivot())。
基準となった値をピボットと呼びます。
ピボットを基準にして配列を2つに分割します(partition())。
分割した配列それぞれに再帰的に同じ処理をしていきます(quick_sort())。
最終的にソートされた配列が出来上がります。