Algorithmen - Teil 1: Quicksort

Neulich hab ich versucht, den Unterschied zwischen funktionalen und imperativen Programmiersprachen zu erklären und dabei festgestellt, dass man das am besten anhand von Beispielcode machen kann. Darum habe ich angefangen Quicksort in drei Programmiersprachen (C, Python, Haskell) zu implementieren. Da Perl und Ruby populäre Sprachen sind, die mich schon länger interessieren, sind die heute auch gleich dazugekommen - eine willkommene Gelegenheit für mich, diese beiden Sprachen näher kennenzulernen und gleichzeitig die Unterschiede und Gemeinsamkeiten der einzelnen Sprachen aufzuzeigen.

Bevor's losgeht noch ein paar kurze Bemerkungen:
Die Aufgabe ist mit Hilfe von Quicksort ein Integer-Array aufsteigend zu sortieren. Dabei habe ich nur in C eine In-Place Sortierung implementiert.
Als Pivot-Element wird das erste Element gewählt und mit 'p' bezeichnet. 'a' bezeichnet das Array und 'l' und 'r' stehen für den "linken" (kleineren) sowie den "rechten" (größeren) Teil des Arrays.
Die gezählten verwendeten Codezeilen beziehen sich nur auf die Funktion selber - zusätzliche Zeilen, die zur Ausführung benötigt werden (main()-Funktion, etc.) werden nicht gezählt.
Also, los gehts:

C

• LOC: 16
• Bemerkungen: In-Place Sortierung, längste Implementierung

#include <stdio.h>
void qsort(int a[], int len) {
    if (len == 0) return;
    int p = a[0];
    int l = 0;
    int r = len-1;
    while (l < r) {
        if (a[l] > a[r]) {
            int tmp = a[l];
            a[l] = a[r];
            a[r] = tmp;
        }
        (a[l] == p) ? r-- : l++;
    }
    qsort(a, l);
    qsort(&a[l+1], len-l-1);
}

int main(int argc, char** argv) {
    int i = 0;
    int test[10] = {6, 4, 9, 1, 2, 5, 3, 8, 7, 0};
    qsort(test, 10);
    printf("[");
    for (i = 0; i < 9; i++) {
        printf("%d, ", test[i]);
    }
    printf("%d]\n", test[9]);
}

Python

• LOC: 9
• Bemerkungen: Verständlicher Ternary-Operator

def qsort(a):
    if (a == []):
        return []
    p = a.pop()
    l = []
    r = []
    for e in a:
        l.append(e) if (e < p) else r.append(e)
    return qsort(l) + [p] + qsort(r)

Haskell

• LOC: 3
• Bemerkungen: Kürzeste Implementierung

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (p:xs) = qsort([l | l <- xs, l < p]) \\
  ++ [p] ++ qsort([r | r <- xs, r > p])

(letzte Zeile zur Lesbarkeit umgebrochen)

Perl

• LOC: 11
• Bemerkungen: Abgefahrenste Syntax

#!/usr/bin/env perl
sub qsort {
    my @l = ();
    my @r = ();
    my @a = @_;
    return () if (@a == 0);
    my $p = shift @a;
    foreach (@a) {
        ($_ < $p) ? (@l[++$#l] = $_) : (@r[++$#r] = $_);
    }
    return (qsort(@l), $p, qsort(@r));
}

print qsort(1, 4, 3, 5, 2, 9, 8, 0, 6, 7);
print "\n"

Ruby

• LOC: 13
• Bemerkungen: Python nicht unähnlich

#!/usr/bin/env ruby
def qsort(a)
    if !a.empty?
        p = a.shift
        l = Array.new
        r = Array.new
        a.each do |e|
            e < p ? l.push(e) : r.push(e)
        end
        (qsort(l) << p) + qsort(r)
    else
        Array.new
    end
end

puts qsort([4, 1, 6, 3, 8, 7, 2, 5, 9, 0])

Die Python- und Haskell-Module habe ich im jeweiligen Interpreter (Hugs bzw. die Python-Konsole) geladen.
Bemerkenswert: C hat die längste Implementierung, ist aber dafür In-Place. Haskell schießt dafür am entgegengesetzten Ende den Vogel ab, mit nur drei Zeilen (von denen die erste noch nicht einmal dringend nötig ist). Und das Perl-Statement

($_ < $p) ? (@l[++$#l] = $_) : (@r[++$#r] = $_);

finde ich dermaßen abgefahren, dass ich mir überlege das auszudrucken und an die Wand zu hängen. Ich habe selten dermaßen viele Sonderzeichen in einer Codezeile gesehen!
Wenn ich Zeit habe, werd ich auch noch Java-Code schreiben. Ansonsten überleg ich mir, was der nächste Algorithmus wird. Dijkstra vielleicht...