Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung | |||
| faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [03.06.2025 07:05] – [Zentrale Teilaufgabe: Merge] Frank Schiebel | faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [03.06.2025 07:09] (aktuell) – [Zentrale Teilaufgabe: Merge] Frank Schiebel | ||
|---|---|---|---|
| Zeile 57: | Zeile 57: | ||
| ++++ Hinweis 2: | | ++++ Hinweis 2: | | ||
| <code java> | <code java> | ||
| + | |||
| + | merged = new String[a.length + b.length]; | ||
| // Das sind die Indizes für die beiden Teilarrays | // Das sind die Indizes für die beiden Teilarrays | ||
| // Beide beginnen bei 0 | // Beide beginnen bei 0 | ||
| - | int i=0; | + | int ia = 0; // Zeiger auf das Element in Teilarray a |
| - | int j=0; | + | int ib = 0; // Zeiger auf das Element in Teilarray b |
| - | // k läuft von 0 bis merged-length-1 | + | // im läuft von 0 bis merged-length-1 |
| // bei jedem Durchlauf muss ein neues Element eingefügt werden - | // bei jedem Durchlauf muss ein neues Element eingefügt werden - | ||
| // nur welches? | // nur welches? | ||
| // Es müssen 4 Fälle unterschieden werden. Denke an die Länge der Arrays a und b! | // Es müssen 4 Fälle unterschieden werden. Denke an die Länge der Arrays a und b! | ||
| - | for(int | + | for(int |
| // Fall 1: | // Fall 1: | ||
| Zeile 83: | Zeile 86: | ||
| ++++ Hinweis 3: | | ++++ Hinweis 3: | | ||
| <code java> | <code java> | ||
| + | |||
| + | merged = new String[a.length + b.length]; | ||
| // Das sind die Indizes für die beiden Teilarrays | // Das sind die Indizes für die beiden Teilarrays | ||
| // Beide beginnen bei 0 | // Beide beginnen bei 0 | ||
| - | int i=0; | + | int ia = 0; // Zeiger auf das Element in Teilarray a |
| - | int j=0; | + | int ib = 0; // Zeiger auf das Element in Teilarray b |
| - | // k läuft von 0 bis merged-length-1 | + | // im läuft von 0 bis merged-length-1 |
| // bei jedem Durchlauf muss ein neues Element eingefügt werden - | // bei jedem Durchlauf muss ein neues Element eingefügt werden - | ||
| // nur welches? | // nur welches? | ||
| // Es müssen 4 Fälle unterschieden werden. Denke an die Länge der Arrays a und b! | // Es müssen 4 Fälle unterschieden werden. Denke an die Länge der Arrays a und b! | ||
| - | for(int | + | for(int |
| // Fall 1 und 2 müssen überprüfen, | // Fall 1 und 2 müssen überprüfen, | ||
| Zeile 101: | Zeile 105: | ||
| // Was muss dann geschehen? | // Was muss dann geschehen? | ||
| - | // Fall 1: i ist außerhalb der Länge von a | + | // Fall 1: ia ist außerhalb der Länge von a |
| - | if(i >= a.length) { | + | if(ia >= a.length) { |
| - | // Fall 2: | + | // Fall 2: |
| - | } else if(j >= b.length) { | + | } else if(ib >= b.length) { |
| // Fall 3: | // Fall 3: | ||
| Zeile 123: | Zeile 126: | ||
| ++++ Hinweis 4: | | ++++ Hinweis 4: | | ||
| <code java> | <code java> | ||
| - | int i=0; | + | merged = new String[a.length + b.length]; |
| - | int j=0; | + | |
| + | int ia = 0; // Zeiger auf das Element in Teilarray a | ||
| + | int ib = 0; // Zeiger auf das Element in Teilarray b | ||
| - | for(int | + | for(int |
| - | if(i >= a.length) { | + | if(ia >= a.length) { |
| // Das Array a ist abgearbeitet, | // Das Array a ist abgearbeitet, | ||
| // von b ohne weiteres nach merged übertragen werden, weil a und b | // von b ohne weiteres nach merged übertragen werden, weil a und b | ||
| // ja sortiert sind! Der Index von b muss jeweils erhöht werden. | // ja sortiert sind! Der Index von b muss jeweils erhöht werden. | ||
| - | merged[k] = b[j]; | + | merged[im] = b[ib]; |
| - | | + | |
| - | } else if(j >= b.length) { | + | } else if(ib >= b.length) { |
| // Das Array b ist abgearbeitet, | // Das Array b ist abgearbeitet, | ||
| // von b ohne weiteres nach merged übertragen werden, weil a und b | // von b ohne weiteres nach merged übertragen werden, weil a und b | ||
| // ja sortiert sind! | // ja sortiert sind! | ||
| - | merged[k] = a[i]; | + | merged[im] = a[ia]; |
| - | | + | |
| - | } else if(less(b[j], a[i])) { | + | } else if(less(b[ib], a[ia])) { |
| // Was fehlt hier? | // Was fehlt hier? | ||
| } else { | } else { | ||