Kannst du mir Zeile 7 erklären auf deutsch?
Bis Zeile 6 verstehe ich. Danach wird mir schwindelig. Sagen wir i ist größer als j. Dann rückt i eins vor. Dann ist die zweite Stelle jetzt i.
Direkt danach wird in Zeile 7 aber gesagt i = i - 1
Also wäre wieder die erste Stelle i und dann steht da dass die zweite Stelle also i+1 der neue key wäre. Aber ich habe den doch schon kontrolliert!
5 Antworten
Das Array A soll durch wiederholtes Einfügen des nächsten Elements sortiert werden, und ist jeweils bis zum Index j bereits sortiert.
Die innere Schleife läuft so lange, bis die richtige Einfügeposition gefunden wurde.
Dazu startet i mit dem höchsten Wert/Position (also dem Ende des bereit sortierten Teils) und wird nach jedem Schleifendurchlauf einmal dekrementiert. (Zeile 7)
Sie stoppt, wenn das erste Element gefunden wurde, das <= key ist, und an dieser Position kann dann eingefügt werden.
Danach ist das Array A komplett aufsteigend sortiert.
In Zeile 7 wird i um 1 verringert.
Du hast am Anfang im Code i definiert, in Zeile 7 definierst du sie neu. Der alte Wert aus i wird mit 1 subtrahiert (im Code: i - 1) und danach wird i überschrieben mit diesem Wert.
z.B: Wenn i vorher 7 war: i = 7 - 1 = 6 -> i = 6
:D
Hallo,
Diesen Algorithmus nennt man auch Bubblesort, weil die großen Werte wie Seifenblasen nach oben steigen
Du durchsuchst den Bestand von n Elementen und vergleichst immer eins mit dem daneben. Solange das ELement größer ist wird es nach oben vertauscht. Am ende(n=2) stehn die goßen werte oben und darunter die kleinen.
Bubblesort ist nicht sehr schnell. Der eigentlich verbreitete ist Quicksort. Dabei wird die Menge der Elemente in 2 Hälften geteilt und hat den Dantenbestandin maximal 8 Schritten sortiert, weil sich die Routine immer wieder selbt aufruft.
LG
Harry
Sieht aber verdächtig danach aus und wird von Anfängern gerne benutzt, die Rekursion nicht verstehen. die sortierten Elemente steigen im Heap wie Blasen nachh oben. aber wirklich können muß man den Quicksort.
Zeile 7: i wird bei jedem Durchlauf um 1 verringert.
Im übrigen bin ich mir nicht sicher, ob das Ergebnis auch das Ergebnis ist, was du erwartest.
i kann nicht größer als j sein, da i stets auf j-1 initialisiert wird.
Die Schleife läuft rückwärts durch die ersten (bis zu) j-1 Elemente. In dem Moment wo keine Inversion mehr gefunden wird, stoppt das Rückwärtslaufen natürlich.
Genau das hat mir gefehlt, dass jemand mir sagt dass die schleife rückwärts läuft! Wo erkenne ich das oder ist das immer so? Ich dachte die läuft vorwärts weil j=2 war. Habe gedacht die schleife läuft vorwärts von j=2 bis n !
Direkt vor der inneren Schleife:
i=j-1 #ü wird auf j-1 initialisiert
while i>0 (.....) # solange i noch nicht Null
...
i=i-1 # reduziere i um 1.
Das i=i-1 ist die Laufrichtung entgegen der Indizierung.
Ich denke, der Algorithmus heißt "Insertionsort". "Bubblesort" funktioniert nämlich anders.