Algorithmensammlung: Sortierverfahren: Quicksort

Aus Wikibooks

Algorithmensammlung: Sortierverfahren

• Combsort
• Quicksort
• Heapsort
• Selectionsort

[Bearbeiten] Quicksort

Quicksort wird gemeinhin als das beste Sortierverfahren in der Praxis betrachtet. Während seine Laufzeit im schlechtesten Fall beträgt, erreicht es eine mittlere Laufzeit von und ist damit nahezu optimal. Der Algorithmus arbeitet nach dem "Teile und Herrsche"-Prinzip.

Für weitere Informationen siehe Quicksort.

[Bearbeiten] Perl

sub quicksort {
    if(!@_) {
    	return ();
    }
    else {
    	return (quicksort(grep { $_ < $_[0] } @_[1..$#_]),
    		$_[0],
    		quicksort(grep { $_ >= $_[0] } @_[1..$#_]));
    }
}

[Bearbeiten] Python

def quicksort(liste):
    if len(liste) <= 1:
        return liste
    else:
        return quicksort(filter(lambda x: x < liste[0], liste[1:])) + \
               [ liste[0] ] + \
               quicksort(filter(lambda x: x >= liste[0], liste[1:]))