Mergesort Processing

Scheint ein bissel komisch zu sein, grad no time will pennen gehen schaus mir morgen mal an. Ausserdem wirst du nicht mehr als:

1. den code
2. das ergebnis sehen

verstehen wirst du es dadurch nicht mehr...

@roadricus
ich hatte grade eine unterhaltung mit den user lufton der mir versuchte die einzelnen schritte zu erklären

mehr oder wenig nützlich. es ist eben kompliziert.

schade ich hätte es trotzdem gerne gesehen.

@kisa
Geht es dir primär um das allgemeine Verständnis des Mergesort-Algorythmus oder eher darum, wie man diesen Algorythmus in Programmiercode umsetzt?

@magiroth
beides natürlich^^

was nützt mir das verständnis wenn ich es nicht umsetzen kann

@kisa
Ich habe gestern abend noch einmal darüber nachgedacht. Wie ich dir schon sagte, du hast dir da ein Stück Code rausgesucht, das schon deutlich im Fortgeschrittenenbereich anzusiedeln ist. Denn zum vollen Verständnis musst du nicht nur wissen was Array sind, sondern auch wie die Inlinenotationen (wie z.B. j++) zu lesen und / oder zu verstehen sind und natürlich was Zählschleifen sind und wie sie funktionieren. Dann musst du verstehen, was Rekursion bedeutet und welchen Unterschied eine Variablenübergabe „by reference“ oder „by value“ macht. (Damit du verstehst, warum jede Instanz von mergesort zwar auf das gleiche Array aber nicht auf das gleiche l und r zugreift.)

Für den Anfang lassen wir mal die technischen Details weg und versuchen die Grundidee des mergesort zu verstehen. (Nimm’s nicht persönlich, ich mache das jetzt mal ganz trivial.)

Stelle dir vor, jemand kommt zu dir und sagt: hey, ich habe hier 100 Karteikarten. Die sind mir leider runtergefallen. Kannst du dir bitte mal eben nach der Kundennummer sortieren. Dann stehst du vor dem Problem, dass du jetzt jede einzelne Karte irgendwie wieder an ihren Platz bringen müsstest. Aber wie? Da hast du dir rettende Idee: wenn mir jemand je eine Hälfte des Stapelst abnimmt und mir dann wieder sortiert zurückgibt (immer die kleinsten des Stapels oben), dann kann ich die ganz leicht sortieren, weil ich dann ja nur zwei Stapel habe und schauen muss, auf welchem Stapel liegt die im Moment kleinste Kundennummer. Links? Also nehme ich die linke Karte. Und wieder schauen, wo ist jetzt die kleinere Nummer? Immer noch links? Also nehme ich noch mal vom linken Stapel. Und zwar so lange, bis die kleinere Nummer auf dem rechten Stapel ist. Auf diese Art und Weise schrumpfen beide Stapel nacheinander (immer abhängig davon, auf welcher Seite gerade die kleinste Nummer zu sehen ist), bis sie beide leer sind und alle sortiert auf einem Stapel liegen. Das ist die Grundidee. (Das passiert in der K-Schleife)

Du hast jetzt also jemanden gefunden, dem du die erste Hälfte des Stapels gegeben hast. Der steht nun auch wieder vor dem Problem, dass er zwar nur 50 Karten, aber auch die wild durcheinander, zu sortieren hat. Der sagt sich: hey, die Idee mit den zwei Stapeln ist gut. Das mache ich auch so. Also sucht er sich wieder zwei Leute, denen er jeweils 25 der Karten in die Hand drückt. Der hat das gleiche Problem, teil den Stapel wieder und gibt den nächsten beiden einmal 12 und einmal 13 Karten. Die verteilen die Stapel wieder an je zwei Helfer (einmal 6 zu 6, einmal 6 zu 7), die machen das gleiche Spiel, und zwar so lange, bis irgendwer nur noch eine Karte in die Hand bekommt. (Im echten Leben würde der zwar wohl komisch gucken, aber Computer gucken nicht doof (oder wenn merkt es keiner ;) )) Dieser letzte Helfer würde dann sagen: ja, diese eine Karte ist in der richtigen Reihenfolge. Damit gibt er sie dem Helfer von dem er sie bekommen hat zurück. Der bekommt auch die zweite Karte von dem andern Helfer mit der Meldung „ist sortiert“ zurück. Jetzt hat er also da zwei Stapel (mit je einer Karte!). Also vergleicht er die beiden Stapel, nimmt erst die kleinere, dann die größere und gibt sie in der richtigen Reihenfolge an seinen Auftraggeber zurück. Der wiederum hat jetzt wieder zwei Stapel mit je zwei (oder auch nur einer auf dem einen und zwei auf dem anderen) sortiert zurückerhalten, vergleicht also wieder die Karten und macht daraus einen Stapel, denn er dann wieder an seinen Auftraggeber zurückgibt. Und das geht dann wieder die ganze Kette zurück, bis bei dir zwei in sich sortierte Stapel mit je 50 Karten ankommen. Jetzt kannst du sie ganz einfach vergleichen und zusammenführen. Die 100 Karten sind sortiert.

Damit solltest du die Grundidee, wie der mergesort funktioniert, verstanden haben. Was die programmtechnische Umsetzung angeht (und warum man zwei Arrays braucht (a[] und b[]), das ist etwas komplexer und nicht mal eben beschrieben…

Das Prinzip, sich einen Helfer zu suchen, der das gleiche macht wie man selber, lediglich für eine Untermenge, ist letztlich genau das, was sich Rekursion nennt. Wenn die Funktion mergesort selber die Funktion mergesort aufruft (was hier eben immer für den ersten und den zweiten Teil des Stapels passiert), dann heißt das eben, starte eine neue Instanz (einen neuen Helfer) mit den gleichen Arbeitsanweisungen. Wichtig dabei ist, dass jede Instanz eben ihre eigenen Variablen hat. (Noch wieder so ein Stück zum Verständnis: die Sichtbarkeit von Variablen…)

Zusammenfassend möchte ich sagen: wenn du diesen Code verstanden hast, dann brauchst du nur noch vor Pointern Angst zu haben (obwohl die implizit hier auch schon verwendet werden…). Alles andere ist dann nur noch Spielkram…

Ach ja, eines noch: vergiss bitte den Sourcecode, den ich dir gestern geschickt habe. Ich sagte dir ja, ich bin kein Freund dieser ganzen Inlinenotationen. Und habe auch prompt einen kleinen, aber entscheidenden Fehler gemacht:

a[k] = b[j--] ist eben nicht

j=j-1;
a[k]=b[j];

sondern

a[k]=b[j];
j=j-1;

sprich, das nachgestellte -- zeigt an, dass erst j verwendet wird und dann dekrementiert. Ansonsten hätte es a[k]=b[--j] heißen müssen.

Ich hoffe, dass ich jetzt bei aller Verwirrung auch ein wenig Klarheit reinbringen konnte.

Bis auf die allgemeine Erklärung eines mergeSorts bringt eine erklärung des Programms nichts, wenn die basics fehlen. Man kann nicht über ein Buch auf Deutsch, ohne Deutschkentnisse diskutieren. So ist das auch hier.


p.s. @tommy: bei dem processing ist der eintrittspunkt direkt das sketch in dem man arbeitet.

@kisa

Also zunächst einmal:
1) Die Funktion ist "plain vanilla" C
2) Das was Du gepostet hast ist verstümmelt
3) Die Formatierung ist ein absoluter Horror
4) So wie sie im Original auf der verlinkten Seite steht funktioniert sie nicht.

Ich hab die Funktion in ein kleines Programm eingebaut:
(Leider schluckt die Forensoftware die führenden Leerzeichen :( ich habe daher statt Tabstops Punkte an den Zeilenanfamng gesetzt - ein Tabstop pro Punkt)

Schau es Dir an und versuch herauszufinden wie es funktioniert. Du kannst von Microsoft eine kostenlose Version des Entwicklungssystems Visual Studio herunterladen und damit das Programm kompilieren und schrittweise ausführen, wobei Du Dir jederzeit die Werte in den Variablen anzeigen lassen kannst.

// MergeSortRekursiv.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//

#include "stdafx.h"

void MergeSort(char[], int, int);
/*Vorwärtsdeklaration, damit der Compiler überprüfen kann ob die übergebenen Argumente vom richtigen Typ sind.*/


int _tmain(int argc, _TCHAR* argv[]) //Die Programmausführung startet hier
{
.char name[] = "Caroline";

.MergeSort(name, 0, sizeof name - 1);
.return 0;
}

void MergeSort(char a[], int l, int r) //l=linker Rand, r=rechter Rand
{
.char b[1024];
.int tst = 0;

.if(r > l)
.{
..int i;
..int j;
..int k;
..int m; //Variablen deklarieren

..m = (r + l) / 2; //Mitte ermitteln

//in den folgenden beiden Befehlen liegt das Problem. Wer erkennt es?

..MergeSort(a, l, m); //linke Teildatei
..MergeSort(a, m + 1, r); //rechte Teildatei

..for(i = m + 1; i > l; i--)
..{
...b[i - 1] = a[i - 1];
..}//linke Teildatei in Hilfsarray

..for(j = m; j < r; j++)
..{
...b[r + m - j] = a[j + 1];
..}//rechte Teildatei umgedreht in Hilfsarray

..for(k = l; k <= r; k++)
..{
...a[k] = (b < b[j]) ? b[i++] : b[j--];
..}//füge sortiert in a ein
.}
}

@OpenEyes
Wenn Du das char-array b nicht innerhalb von MergeSort definiert hättest, würdest Du nicht mit jeder Instanz von MergeSort 1024 Byte reservieren. Hier würde eine globale Definition reichen. (Ich würde sogar so weit gehen und das Array b mit als Parameter referenzieren.)

Mir fehlt ja noch eine Ausgabe:

int i;
for (i=0;i<sizeof(name);i++)
{
print(name);
}

argh.... wo sind meine eckigen Klammern geblieben...

ich Depp... i in [ ] macht kursiv.... und mein sizeof mag er auch nicht...

OK, also zweiter Anlauf:

int z;
for (z=0; z < sizeof( name ); z++)
{
print(name[z]);
}

@Lufton

Die Klammern bei sizeof sind überflüssig :)

Ernsthaft - natürlich gehört eine Ausgabe auch dazu - ich wollte aber so wenig wie möglich am Originalcode ändern um den Threadersteller nicht durcheinander zu bringen.

Das Problem mit der Rekursion ist, dass der zweite rekursive Aufruf für die rechte Teildatei erst erreicht wird wenn die linke Teildatei komplett abgearbeitet ist und bereits das "stack - unwinding" stattfindet.

Eine rekursive Funktion aus sich heraus mehrmals aufzurufen ist selten eine gute Idee.

Mit dem Einwand bezüglich b[] hast Du recht. Allerdings würde ich keine globale Variable verwenden sondern
static char b[was -auch -immer];

Ich hab eine tief verwurzelte Abneigung gegen globale Variable.

Klingt zumindest ein bisschen umständlich. Ein Bubblesort hätte es auch getan - und der sieht viel hübscher aus :).

Hast Du denn noch Fragen, Kisa?

@moredread
nein, ich verfolge die entwicklung des programms, fragen ergeben sich nicht da ich den zusammenhang der einzelnen elemente nicht verstehe.

aber es ist interessant zu sehen wieviel arbeit hinter so einen sortieralgorhythmus steckt!

ich habe mergesort genommen weil ich nur das kannte ;)

@kisa
Naja, steht die Idee einmal, ist die Arbeit dann nichtmal mehr so gross. Aber es setzt eben fortgeschrittene Programmierkenntnisse voraus, das auch zu verstehen. Wenn du es wirklich auf Programmebene verstehen willst, wäre es für dich wohl am einfachsten, irgendwelche C Tutorials durchzulesen. Davon gibt es im Netz massig.

Für uns wäre es auch etwas beschämend, wenn du das alles innert kürzester Zeit verstehen würdest ^^

@kisa

Schauen wir uns einmal an, was die Funktion machen soll:

Aufgerufen wird sie mit den Parametern:

"caroline", 0, 8

******Aufteilen******

"caroline" soll jetzt auf 2 Helfer verteilt werden, ich nenne sie H1 und H2
H1 bekommt "caro", H2 bekommt "line"
Jetzt brauchen wir vier weitere Helfer, H3, H4, H5, H6
H3 bekommt "ca", H4 "ro", H5 "li" und H6 "ne"
und schließlich noch 8 weitere Helfer, H7, H8, H9, H10, H11, H12, H13, H14
H7 bekommt "c", H8 "a", H9 "r", H10 "o", H11 "l", H12 "i", H13 "n" und H14 "e"

Damit haben wir die Aufteilung erledigt. Jetzt müssen wir nur noch die auf 8 Helfer aufgeteilten Buchstaben in der richtigen Reihenfolge zusammensetzen:

******Mischen******

H3 schaut an, was H7 und H8 haben. (die Buchstaben werden im Computer als Zahlen dargestellt, wobei "a" die kleinste und "z" die größte Zahl ist)

"c" ist größer als "a", also kommt zuerst das "a" -->H3 hat nun "ac"
H4 schaut an, was H9 und H10 haben
"o" ist kleiner als "r", also kommt zuerst das "o" -->H4 hat nun "or"
H5 nimmt H11 und H12
"i" ist kleiner als "l", also kommt zuerst das "i" --> H5 hat nun "il"
und H6 schließlich nimmt, was H13 und H14 haben
"e" ist kleiner als "n", also kommt zuerst das "e" --> H6 hat nun "en"

Jetzt haben wir es gleich:

H1 setzt das zusammen was H3 und H4 haben:

H3 hat "ac", H4 hat "or"
"a" ist kleiner als "o", "c" ebenfalls, also nimmt H2 zuerst "ac" und dann "or"
H1 hat nun "acor"

H2 setzt zusammen was H5 und H6 haben:
H5 hat "il", H6 hat "en"
"e" ist der kleinste Wert, kommt also als erstes. Der nächst größere Wert ist "i", dann kommt "l" und schließlich "n"
H2 hat also nun "eiln"

Nun müssen wir noch die beiden Buchstabengruppen ineinander verschachteln
Wir nehmen also "a" von H1, dann "c" von H1 dann "e", "i", "l", und "n" von H2 und schließlich "o" und "r" vo H1 und haben damit das sortierte Ergebnis:
"aceilnor"

Ist doch nicht schwer zu verstehen, oder?
Schau jetzt zunächst, dass Du diesen Vorgang ganz genau verstehst, ich überleg inzwischen wie ich den Code (nicht den, welchen Du gepostet hast, der funktioniert nicht) so aufbereiten kann, dass Du ihn ebenfalls verstehen kannst.

@OpenEyes
ja das ist sehr gut geschrieben, das versteh ich, ich weiß auch was die einzelnen elemente machen.

das problem ist dann wenn es implementiert wurde es zu verstehen, aufgrund der variablen etc. das ist irgendwie ziemlich viel zum verstehen <,<

Ich würde Bubblesort vorschlagen. Ist einfacher.

Nehmen wir wieder das Beispiel "caroline".

Bubblesort vergleicht jetzt die Buchstaben der Reihe nach. Also erst den ersten Buchstaben mit dem zweiten, den zweiten mit dem dritten usw. Ist die Reihenfolge falsch, werden die Buchstaben umsortiert. Das sieht bei caroline dann so aus:

c a r o l i n e

a c r o l i n e (a und c werden vertauscht, da a vor c kommt)

a c r o l i n e (c und r bleiben stehen, da die Reihenfolge korrekt ist)

a c o r l i n e (r und o werden vertauscht, da o vor r kommt)

a c o l r i n e (l und r werden vertauscht, da l vor r kommt)

a c o l i r n e (i und r werden vertauscht, da i vor r kommt)

a c o l i n r e (n und r werden vertauscht, da n vor r kommt)

a c o l i n e r (e und r werden vertauscht, da e vor r kommt)


An diesem Punkt hat der Sortieralgorithmus das Wort einmal durchgearbeitet. Jetzt greift eine Regel, die besagt: Wenn beim Durchlauf ein Buchstabe vertauscht wurde, muss das Programm noch einmal durchlaufen. Das Programm beginnt also erneut, diesmal mit dem Begriff "acoliner"

a c o l i n e r (a und c bleiben stehen, da die Reihenfolge stimmt)

a c o l i n e r (c und o bleiben stehen, da die Reihenfolge stimmt)

a c l o i n e r (l und o werden vertauscht, da l vor o kommt)

a c l i o n e r (i und o werden vertauscht, da i vor o kommt)

a c l i n o e r (n und o werden vertauscht, da n vor o kommt)

a c l i n e o r (e und o werden vertauscht, da e vor o kommt)

a c l i n e o r (o und r bleiben stehen, da die Reihenfolge stimmt)


Es wurden Buchstaben vertauscht, als startet der Algorithmus erneut:

a c l i n e o r (a und c bleiben stehen, da die Reihenfolge stimmt)

a c l i n e o r (c und l bleiben stehen, da die Reihenfolge stimmt)

a c i l n e o r (i und l werden vertauscht, da die vor l kommt)

a c i l n e o r (l und n bleiben stehen, da die Reihenfolge stimmt)

a c i l e n o r (e und n werden vertauscht, da e vor n kommt)

a c i l e n o r (n, o und r stehen in der richtigen Reihenfolge)


Der Algorithmus startet erneut, da Buchstaben vertauscht wurden:

a c i l e n o r (a, c, i und l bleiben stehen, da die Reihenfolge stimmt)

a c i e l n o r (e und l werden vertauscht, da e vor l kommt)

a c i e l n o r (l, n, o und r bleiben stehen, da die Reihenfolge stimmt)


Der Algorithmus startet erneut, da Buchstaben vertauscht wurden:

a c i e l n o r (a, c und i bleiben stehen, da die Reihenfolge stimmt)

a c e i l n o r (e und i werden vertauscht, da e vor i kommt)


Der Algorithmus startet erneut. Er findet nun keine Buchstaben mehr, deren Reihenfolge nicht passt. Das Ergebnis lautet also:

a c e i l n o r



Die Art und Weise, wie sortiert wurde, sollte jetzt klar sein. Bleibt nur noch die Frage, wie Du das ganze in Software realisierst.

Deine Programmiersprache steht mir natürlich nicht zur Verfügung. Falls nötig, kann ich mal schauen, ob ich dran komme. Bis dahin wirst Du mit C++ leben müssen, das aber offensichtlich Deiner Programmiersprache recht ähnlich ist.

Fangen wir an mit Variablen. Ich brauche irgendwas, um Kram abzuspeichern. Zum einen wäre da der Name, den ich sortieren will. Zum anderen brauche ich eine Variable, in die ich den Buchstaben zwischenspeichern kann, den ich austausche. Und ich muss mir merken, ob der Algorithmus sich Wiederholt. Ich schlage also mal vor

Name ----> Hierdrin speichern wir den zu sortierenden Namen
Buchstabe ----> Hierdrin speichern wir den Buchstaben
Wiederholung ----> Hierdrin speichern wir ab, ob sich der Vorgang wiederholt

Damit hätten wir schonmal etwas wichtiges. Wir wissen, was sich das Programm merken muss. Jetzt müssen wir uns nur noch überlegen, wie man das ganze programmiert. Mir steht hier nur C++ zur Verfügung. Die simpelste Methode, so ein Programm zu starten, dürfte wohl DevCPP sein. Ziemlich klein, lässt sich ruckzuck installieren. Solltest Du inzwischen tatsächlich das Microsoft Visual Studio heruntergeladen haben, kannst Du es auch damit realisieren (vorausgesetzt, Du kannst damit umgehen). Bei Problemen - frag!

Ich erkäre dir jetzt Stück für Stück, wie ich die Software realisieren. Als erstes würde ich vorschlagen, das wir eine sogenannte Schleife bauen. Eine Schleife wiederholt etwas so lange, bis irgend etwas passiert. Ich würde folgendes vorschlagen

Schleife: Wiederhole das folgende sieben mal.

Wenn der Name (Schleife) größer ist als der Name (Schleife+1), dann vertausche sie und rechne + 1 auf die Wiederholung.

Das ist schon alles. Das (Schleife), das hinter Buchstabe steht, zählt lediglich mit, die wievielte Schleife gerade gedreht wird. Beim ersten Durchlauf wird jetzt überprüft, ob der erste Buchstabe des Namens größer ist als der zweite. Ist das der Fall, werden die beiden vertauscht. Außerdem wird auf "Wiederholung" eins drauf gerechnet. Du erinnerst Dich - wir müssen diese Schleife ja so oft wiederholen, bis ALLE Buchstaben sortiert sind. Das erreiche ich so


Mache das nun folgende so lange, bis...

........
........ Setze Wiederholung auf Null
........
........ Schleife: Wiederhole das folgende sieben mal.
........
........ Wenn der Name (Schleife) größer ist als der Name (Schleife+1), dann vertausche
........ sie und rechne + 1 auf die Wiederholung.
........

... der Wert "Wiederholung" auf Null steht.


Und das ist der ganze Programmcode, mehr braucht es nicht. Wie ich sagte - er muss so lange eine Schleife machen, bis keine Wiederholung mehr nötig war. Als C++ Programmcode sieht das ganze dann so aus:

Original anzeigen (0,2 MB)

@OpenEyes

OpenEyes schrieb:"caroline", 0, 8

Ich biete "caroline", 0, 7... (aber um 04:27 will ich das verzeihen ;) )

Und nein, ich bin auch kein Freund von globalen Variablen. Deswegen sagte ich ja, ich würde das Hilfarray ebenfalls als Referenz mit übergeben. Denn als Aufrufender weiß ich ja, wie groß das gebraucht wird und kann es entsprechend allozieren.

Und ja, die Klammer bei sizeof sind überflüssig, aber die gelebte Erfahrung hat gezeigt, dass es sich einfach besser liest...

Das Problem mit dem doppelten Aufruf sehe ich übrigens nicht als so gravierend an. (Zumindest nicht in Zeiten einer (@kisa: weglesen ;) )automatischen Garbage collection.)

@moredread: Und ja, ein Bublesort ist viel einfacher zu verstehen und zu realisieren, kommt er doch völlig ohne Hilfarray und ohne Rekursion aus. Er ist nur bei völlig unsortierten Element elendslangsam, dafür beim einsortieren einzelner Elemente gnadenlos schnell.

@moredread
Super erklärt! Und dein Algorithmus funktioniert auch. Ich würde ihn aber an zwei Stellen optimieren:

Die Idee des Bubblesort (und deswegen heißt er auch so) ist, dass nach dem ersten Durchlauf das größte Element ganz hinten steht (oder das kleinste ganz vorn, je nachdem, wie man es umsetzt), d.h. in jedem Durchlauf steigt ein Element wie eine Blase in einer Flüssigkeit nach oben an ihren Platz. Damit braucht das letzte Element des Durchlaufes nicht jedesmal wieder geprüft zu werden, d.h. mein Suchlauf auf einzusortierende Elemente kann mit jedem Durchlauf um ein Feld kleiner werden. Ist aber zugegebenermaße nur eine Laufzeitoptimierung, funktionieren tut deine Variante genau so (und ist im Zweifelsfall auch einfacher zu verstehen).

Der zweite Punkt aber ist wesentlich: durch feste "Verdrahtung" der 8 in deiner FOR-Schleife funktioniert das nur für exakt 8 Elemente. Hier würde ich die Größe des zu sortierenden Arrays entweder selber ermitteln ( sizeof ) oder als Variable mitgeben.

@kisa
Was Moredread hier eingebaut hat ist übrigens ein sogenannter Ringtausch. Warum macht er das?
Gegeben seien zwei Variablen a und b mit den Werten a=5 und b=7. Wenn ich dir nun die Aufgabe stelle, die beiden Variablen zu tauschn, so das a=b ist und b=a, dann kannst du im Kopf sofort nachvollziehen, dass nun a=7 und b=5 sein soll. Nicht so der Rechner. Sagst du ihm, das a=b sein soll, erhält a sofort den Wert 7. Wenn du in einer zweiten Zeile dann b=a schreiben würdest, erhielte b nunmehr den Wert 7 aus der Variable a, sprich beide hätten den gleichen Wert.

Deshalb hat e hier eine Hilfsvariable c (in seinen Beispiel Buchstabe) eingeführt, um den Wert zu sichern. Also c erhält den Wert aus a (c=a; => c ist jetzt 5), dann erhält a den Wert aus b (a=b; => a ist jetzt 7), anschließend wird der in c gesicherte Wert b zugewiesen (b=c; => b ist jetzt 5). Weil die 5 hier von a über c nach b wandert, nennt sich das ganze Ringtausch. (Die einzige Möglichkeit in der IT Variableninhalte auszutauschen, ohne sich ins Knie zu schießen...)

@moredread
Ich sehe übrigens gerade, du hast den gleichen (ganz typischen und oft gemachten) Fehler eingebaut wie OpenEyes.

Wenn du mit C arbeitest und die Arrays mit 0 beginnen und wir 8 Elemente haben, dann ist der höchstzulässige Wert als Index 7. 7 ist aber auch der Höchstwert in deiner For-Schleife. Und dann greifst du auf i+1 zu... Das kann gut gehen - muss aber nicht. (Und die Wahrscheinlichkeit ist hoch, dass es das nicht tut!)

@kisa (zum Verständnis für dich)
Habe ich ein Array definiert, das x Elemente hat, ist es leider stark von der Programmiersprache abhängig, wie ich darauf zugreifen kann. Die meisten Basic-Varianten würden das entweder während des Kompilierens merken und abrechen, oder aber spätestens zur Laufzeit abbrechen, mit der Mitteilung, dass hier auf ein unerlaubtes Element zugegriffen werden soll.

C (und damit eben auch C++) gehört zu den Sprachen, die sich um solche Dinge einen Feuchten kehren. C behandelt Array letztlich mit seiner sogenannten Pointerarithmetik. D.h. habe ich ein Array int a[10], dann reserviert C dafür 10 aufeinanderfolgende Bytes. Angesprochen werden sie mit a[0] bis a[9] und besagen dem Rechner letztlich folgendes: gehe an die Speicherstelle von a und addiere dazu X mal die Länge der einzelnen Variablen (bei Int oder Char eben ein Byte, bei Doubles 8 oder 16 Bytes (systemabhängig)). Rufe ich jetzt also a[10] auf, addiert der Rechner gnadenlos 10 mal ein Byte und greift auf die Speicherstelle zu. Im günstigsten Fall ist der Speicher an der Stelle gerade leer und 0. Im ungünstigsten Fall steht hier ein Wert, der zu einer ganz anderen Variable gehört... Deshalb immer aufpassen mit den Indizes...

So. Verwirrung kompott. Ich habe fertig.

@Lufton

Das weiß ich alles. Meine Variante ist der Einfachheit geschuldet. Um unterschiedliche Array-Längen zu realisieren, benötigt es den new - Befehl, den wollte ich mir hier sparen.

Wo Dein Problem mit der Array-Länge ist, weiß ich nicht. Halt, doch, natürlich schon ;). Du darfst nur nicht vergessen, das "caroline" in c++ 9 char-Array-Felder füllt. In den ersten acht Feldern steht der Name, im letzten eine Null. Das ist c++ Standard, und deshalb benötige ich neun Felder. Es gibt Möglichkeiten, das zu umgehen, aber wie gesagt, es sollte einfach sein.

Selbes gilt für die Schleife. Die ist so in Ordnung. +1 auf den Iterator anzuwenden ist in Ordnung, wenn die Schleife darauf angepasst ist, was in meinem Fall ja zutrifft. Bei Dir klingt es so, als ob das eine Frage des Zufalls ist. Bei Schleifen, die sich auf etwas dynamisches beziehen (bspw. ein Bild) arbeite ich auch so, und auch so ziemlich jede Referenzschleife, die ich kenne. Du kannst mir natürlich gerne einen anderen Ansatz zeigen.

Übrigens zum Ringtausch: Du liegst insofern falsch, als das man keine Zwischenvariable benötigt. Man kann es nämlich auch ohne machen. Aus Gründen der Einfachheit habe ich darauf verzichtet. Ich zeige es Dir aber mal.

Wir haben a = 3 und b = 9 und wollen, das a = 9 und b = 3 daraus wird. Wir rechnen:

a=3
b=9

a = b - a
b = b - a
a = a + b

Klappt auch prima mit Char-Variablen.