Montag, Dezember 24, 2007

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...

Votes	P-M JTC1 (41)	P-M SC34 (36)	Others	Total
yes	7	8	1	11
no	13	9	1	15
abstain	5	5	2	9
unclear	16	14	0	20

Montag, Dezember 24, 2007

C

Python

Haskell

Perl

Ruby

Freitag, September 28, 2007

Ubuntu 7.10 Beta Review

Einleitung

Cons

Pros

Fazit

Montag, September 24, 2007

Sonntag, September 23, 2007

Donnerstag, September 06, 2007

Mittwoch, September 05, 2007

Dienstag, September 04, 2007

Montag, September 03, 2007

Freitag, August 31, 2007

Mittwoch, August 29, 2007

Dienstag, August 28, 2007

Montag, August 27, 2007

Sonntag, August 26, 2007

Über mich

Currently playing

Recently Played Tracks

Blog-Archiv

Labels

Links

Software

Kontakt