Sortieren: Quicksort

sortiere (Folge a) = 
  wenn Länge (a) <= 1, 
    dann gib a aus, 
    sonst 
      Zahl  p = (ungefähr) der Median von a
      Folge b = Elemente von a, die kleiner als p sind
      Folge c = Elemente von a, die größer als p sind
      Folge b' = sortiere (b)
      Folge c' = sortiere (c)
      gib aus: b', dann p, dann c'

Laufzeit hängt davon ab, wie gut man den Median trifft.

Mehrere Varianten!



Johannes Waldmann 2008-01-28