Lektion 51:

straight insertion sort

 Das nächste Sortierverfahren heißt straight insertion sort. Es ist recht effizient, wenn es wenige zu sortierende Werte gibt, und wenn diese bereits ungefähr in sortierter Reihenfolge vorliegen.

Nehmen wir an, daß bereits die ersten 6 Werte des Arrays sortiert vorliegen. Die anderen 3 Werte sollen noch einsortiert werden.

1 2 3 5 7 9   4 8 6

In der ersten Schleife wird die 4 einsortiert.

1 2 3 5 7 9 4   8 6
          ^ ^        Austausch
1 2 3 5 7 4 9   8 6
        ^ ^          Austausch
1 2 3 5 4 7 9   8 6
      ^ ^            Austausch
1 2 3 4 5 7 9   8 6
    ^ ^              kein Austausch
1 2 3 4 5 7 9   8 6

Sobald kein Austausch stattfindet, ist der Wert richtig einsortiert!

Jetzt wird die 8 einsortiert.

1 2 3 4 5 7 9 8   6
            ^ ^      Austausch
1 2 3 4 5 7 8 9   6
          ^ ^        kein Austausch
1 2 3 4 5 7 8 9   6

Und zum Schluß wird die 6 einsortiert.

1 2 3 4 5 7 9 8 6
              ^ ^  Austausch
1 2 3 4 5 7 9 6 8
            ^ ^    Austausch
1 2 3 4 5 7 6 9 8
          ^ ^      Austausch
1 2 3 4 5 6 7 9 8
        ^ ^        kein Austausch
1 2 3 4 5 6 7 9 8

Übung:

Programmieren Sie dieses Sortierverfahren.



Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern.
[aktuelle Version] [inhalt] [index]      [Fehlerkorrektur, Verbesserungsvorschlag]

© Volkard Henkel <volkard@normannia.de>, last update: 08/25/00