BubbleSort1 vs. BubbleSort2

[Gargoyl]

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.

[Woyzeck]

Zitat von Gargoyl:

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²).[...]

konstante Laufzeit und O(n²)...


Mir ist klar was du meinst, aber der Begriff ist wohl falsch gewählt an der Stelle.

[Gargoyl]

Zitat von Woyzeck:

Zitat von Gargoyl:

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²).[...]

konstante Laufzeit und O(n²)...


Mir ist klar was du meinst, aber der Begriff ist wohl falsch gewählt an der Stelle.

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.

Zitat von Gargoyl:

Also Bubblesort1 hat immer eine konstante die gleiche Laufzeit (bei gleicher Listenlänge), egal ob die Liste bereits sortiert ist oder nicht. Also best case = average case = worst case. Und die Laufzeit ist immer in O(n²).[...]