qsort( a, lo, hi ) int a[], hi, lo; { int h, l, p, t; if (lo < hi) { l = lo; h = hi; p = a[hi]; do { while ((l < h) && (a[l] <= p)) l = l+1; while ((h > 1) && (a[l] >= p)) h = h-1; if (l < h) { t = a[l]; a[l] = a[h]; a[h] = t; } } while (l < h); t = a[l]; a[l] = a[hi] a[hi = t qsort( a, lo, l-1 ); qsort( a, l+1, hi ); } }Und jetzt das ganze in Haskell:
qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x where elts_lt_x = [ y | y <- xs, y < x ] elts_greq_x = [ y | y <- xs, y >= x ]
Zur Erklärung:
Die erste Zeile legt den Typ der Funktion qsort fest: ``Falls a ordbar ist, wandelt qsort eine Liste von a's in eine Liste von a's um.'' In der zweiten Zeile steht: ``Falls die Liste von a eine leere Liste ist, ist das Ergebnis wieder eine leere Liste.'' Und der Rest sagt vereinfacht (wäre zu aufwendig alles durchzugehen, Informatiker sind faul): das Ergebnis ist eine Liste, in der vorne alle sortierten Elemente kleiner , dann
selbst und am Ende alle sortierten Elemente größer
drinstehen. Es ist also offensichtlich, In Haskell wird wirklich nur das aufgeschrieben, was der Mensch auch braucht um das Programm zu verstehen und genau das ist es ja, was eine Sprache tun soll: sie soll eine Verbindung zwischen dem Menschen und der Maschiene schaffen.