BubbleSort1 vs. BubbleSort2

[Uwe Raabe]

Zitat von Deep-Sea:

Der von Uwe Raabe gepostete Quelltext ist jedoch KEIN InsertSort, da er die innere Schleife immer komplett durchläuft, genau wie BubbleSort.

Das hast du vollkommen richtig erkannt (daher auch meine Bemerkung "einfach aber langsam"). Natürlich kann man da noch einiges optimieren. Z.B. den Vergleichswert AList[J] einmal vor der Schleife in eine lokale Variable packen. Bei einem Exchange würde er für den nächsten Vergleich wieder herangezogen und ohne Exchange ist die Schleife eh am Ende.

Wenn man das Speicherlayout des Arrays kennt, kann man auch die Schleife solange ohne Exchange durchlaufen bis man den Einfügepunkt gefunden hat und dann die entsprechenden Elemente per Move nach hinten schieben. Das entspricht dann schon eher der Metapher des "Karteneinsorierens" nach dem der InsertSort ja angeblich seinen Namen hat.