何度目かのquicksortのお勉強

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)

topcoderの問題を解く時に「とりあえずソートして〜」とか思ったことがあったのだけどバブルソートしか書けない自分に絶望したので勉強がてら『定本 Cプログラマのためのアルゴリズムとデータ構造』に載っていたクイックソートのコードを自分がかじった事がある言語で書直してみた。

Perl

#!perl
use strict;
use warnings;

sub qsort {
    my ($a, $l, $r) = @_;
    $l = 0                unless defined $l; 
    $r = scalar @{$a} - 1 unless defined $r;

    return if $l >= $r; 

    my $i = $l - 1;
    my $j = $r;
    my $pivot = $a->[$r];

    my $t;
    while (1) {
        while ($a->[++$i] < $pivot) {}
        while ($i < --$j && $a->[$j] > $pivot) {}
        last if $i >= $j;

        $t = $a->[$i];
        $a->[$i] = $a->[$j];
        $a->[$j] = $t;
    }
    $t = $a->[$i];
    $a->[$i] = $a->[$r];
    $a->[$r] = $t;
 
    qsort( $a, $l, $i-1 );
    qsort( $a, $i+1, $r ); 
}

sub main {
    my @a = (10, 2, 34, 11, 13, 5, 55, 11);
    qsort( \@a );
    print "@a", $/;
}

main() unless caller;

Python

def qsort(a, l, r):
    if l >= r:
        return

    i = l
    j = r - 1
    pivot = a[r]
    while 1:
        while a[i] < pivot:
            i += 1 
        while i < j and a[j] > pivot:
            j -= 1
        if i >= j:
            break

        t = a[i]
        a[i] = a[j]
        a[j] = t

    t = a[i];
    a[i] = a[r];
    a[r] = t;
 
    qsort( a, l, i-1 );
    qsort( a, i+1, r ); 


def main():
    a = [10, 2, 34, 11, 13, 5, 55, 11];
    qsort( a, 0, len(a) - 1 )
    for x in a:
        print x

if __name__ == '__main__':
    main()

JavaScript

function qsort(a, l, r) {
    if (l >= r) {
        return; 
    }

    var i = l - 1;
    var j = r;
    var pivot = a[r];

    var $t;
    while (1) {
        while (a[++i] < pivot) {}
        while (i < --j && a[j] > pivot) {}
        if (i >= j) {
            break;
        }

        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    t = a[i];
    a[i] = a[r];
    a[r] = t;
 
    qsort( a, l, i-1 );
    qsort( a, i+1, r ); 
}

function main() {
    var a = [10, 2, 34, 11, 13, 5, 55, 11];
    qsort(a, 0, a.length - 1);

    for (var i = 0; i < a.length; i++) {
        console.log("%d", a[i]);
    } 
}

main();