Forum: Algorithmen, Datenstrukturen und Klassendesign
by Gargoyl,
7. Jul 2011
:oops: ja unglücklich formuliert von mir. Ist mir gar nicht aufgefallen. Ich meinte natürlich dass die Laufzeit immer gleich ist, egal ob die Liste sortiert ist oder nicht. Bei gleicher Listen-Länge natürlich. Danke für die Korrektur.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Gargoyl,
1. Jul 2011
Also Bubblesort1 hat immer eine konstante Laufzeit, egal ob die Liste bereits sortiert ist oder nicht. Also best case = average case = worst case. Und die Laufzeit ist immer in O(n²).
Bubblesort2 durchläuft bei einer bereits sortierten Liste das ganze nur einmal. Also im best case liegt die Laufzeit in O(n). Wenn die Liste komplett falsch herum (absteigend statt aufsteigend) sortiert ist dann...