|
Registriert seit: 11. Mär 2007
69 Beiträge
|
AW: BubbleSort1 vs. BubbleSort2
1. Jul 2011, 22:21
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 ist die Laufzeit wieder in O(n²). Und im average case liegt sie dann irgendwo dazwischen.
Im worst case sind also beide gleich. Im best case und average case ist Variante 2 schneller.
|