Bub­ble­Sort

Eines der be­kann­tes­ten Sor­tier­ver­fah­ren ist der BubbleSort-​Algorithmus.

Das Prin­zip hin­ter die­sem Al­go­rith­mus ist, dass eine Folge von Zah­len immer wie­der durch­lau­fen wird. Bei jedem Durch­lauf wer­den die be­nach­bar­ten Ele­men­te ver­gli­chen und ggf. ver­tauscht.



Ins­ge­samt muss die Folge so häu­fig durch­lau­fen wer­den, dass das letz­te Ele­ment an die erste Stel­le wan­dern kann. Die­ser Fall tritt ein, wenn das letz­te Ele­ment das kleins­te in der Folge ist.



An­ders aus­ge­drückt: Eine Folge mit n Ele­men­ten muss im schlech­tes­ten Fall n-1 mal durch­lau­fen wer­den. Dies macht den Al­go­rith­mus nicht be­son­ders ef­fek­tiv.