C Sortierungsalgorithmus

[datalukas]

Hallo liebe Forencommunity,

hab mich mal seit längeren wieder mit Programmieren beschäftigt (bin auf dem Gebiet aber ziemlicher Amateur) und habe mir dabei dieses Video als Orientierung genommen.
http://www.youtube.com/watch?v=kgBjXUE_Nwc

Zunächst habe ich "bubble sort" in Code umgesetzt. Das ging noch ganz gut, aber merge sort hat einige Probleme bereitet. Im Grunde habe ich das ganze schon vor Wochen begonnen, immer ein bisschen verändert, dann mal wieder länger nichts gemacht. Man kann auch so leicht Fehler machen und dann braucht man wieder ewig, bis man das gefixt hat.
Den Code hänge ich als .txt an, da sonst wahrscheinlich wieder der Code-Tag aufgrund der ausgeprägten Verschachtelung in die Knie geht. Wahrscheinlich sollte man das ganz anders machen, aber ich habe das eben in meinem eigenen Stil gemacht. Die Funktion ist zunächst mal nur für ein Array der Größe 10 geeignet und soll dann ausgebaut werden.

Zunächst werden mithilfe der ersten Schleife Stapel mit je zwei Karte gebildet, die dann miteinander verglichen werde. Die Reihenfolge wird dann gleich in ins array layers[10][3] abspeichert. layers umfasst am Ende die Reihenfolge nach je einem Durchlauf des Algorithmus. 10 steht hier für die zehn Werte, die sortiert werden und drei für die Anzahl der Ebenen/Durchläufe, die für eine Sortierung notwendig sind.

In einem Durchlauf der äußeren Schleife mit der Variable c wird eine Ebene durchgearbeitet, wie in dem Video in der Grafik zu sehen.
Da ich das "der Stapel ist leer" und "die Karte wird nach oben verschoben" im Video schlecht umsetzen konnte, habe ich die Variablen counter_right, counter_left und counter_comp deklariert. Summiert mit der Schleifenvariable b werden so die jeweils richtigen "Karten" miteinander verglichen. counter_comp wird immer nach einer Wertzuweisung der nächsten Ebene um eins hochgezählt und Ob ein Stapel noch Karte enthält ist, wird mit "if(counter_right < maximum_right)" geprüft. maximum_right wird oben mithilfe der Schleifenvariable c der äußeren Schleife ermittelt.
Ist der Stapel leer, werden die übrig gebliebenen Karte ins Feld darüber gepackt.

Im Falle einer Kartenanzahl, die in der Primzahlenzerlegung nicht nur Zweier enthalten (gibt bestimmt einen Begriff dafür), gibt es außerdem noch Stapel, die kleiner sind als die anderen, hier ab der zweiten Ebene (zwei Stapel mit vier Karten, einer mit zwei). Dafür ist durch das Abprüfen der Größe von maximum_right und maximum_left am Anfang gesorgt.

maximum_right = (int)pow((double)2, c+1) - 1;
if(maximum_right > 9)
	maximum_right = 9;
maximum_left = (int)pow((double)2, c) - 1;
if(maximum_left > 9)
	maximum_left = 9;

Die Ausgabe des Programms ist richtig, allerdings wird der Fehler "Run-Time Check Failure #2 - Stack around the variable 'layers' was corrupted." angezeigt, allerdings nur, wenn ich drei Ebenen durchlaufen lasse, bei zwei passiert das nicht. Ich kann mir das nicht erklären, denn nirgendwo gibt es eine Wertzuweisung, bei der der eine Parameter des Arrays (oder wie man das da nennt) größer als neun ist, das habe ich alles durchprobiert.

Ich weiß ja nicht, ob meine Ausführungen nachvollziehbar waren. Ehrlich gesagt wäre ich eher erstaunt, wenn jemand dem folgen konnte, aber versuchen, kann man ja mal. Habt ihr Ideen?

Gruß
Datalukas

 

[dexi]

Also ohne genau darüber zu schauen. Wenn du 3 Ebenen / Durchläufe brauchst und deine Werte schon in 0 stehen, dann müsste doch das Array Layers [10][4] groß sein. Oder?

Denn sonst bekommst du spätestens hier: layers[b+counter_comp][c] ein Problem wenn c = 3 ist.

 

[antred]

Also, das, was du gepostet hast, ist nicht mal kompilierbar. Schau mal in Zeile 63 ... da fehlt z.B. die schließende Klammer. Poste lieber eine exakte Kopie deines Programms.

 

[AggroOrk]

Wie wäre es damit:
Algorithmen und Datenstrukturen in C/ Mergesort

 

[datalukas]

@dexi Nein, denn die erste Ebene ist praktisch das numbers-array.
@antred Das habe ich nachträglich geändert. Im Programm war das schon richtig.
Hier wäre das ganze Programm.
@AggroOrk Danke, ich dachte ja schon, dass das wohl anders gemacht wird, aber wenn ich schon so angefangen habe...

 

[antred]

Also jetzt, wo ich's mir mal genauer ansehe, muß ich dexi schon Recht geben. Du greifst z.B. in Zeile 68 mit

layers[b+counter_comp][c] = layers[b+counter_left][c-1];

In das Layers-Array, wobei dein Schleifen-Zähler c Werte von 1 bis 3 annehmen kann. Index 3 ist hier aber eins mehr, als diese Dimension deines Arrays hergibt, das du ja in Zeile 35 mit

int layers[10][3];

angelegt hast.


P.S. Wieso läßt du das Programm nicht einfach im Debugger laufen? Der würde dich sogar auf die Codezeile stubsen, in der es knallt. Dann könntest du dir in Ruhe die Werte der verschiedenen Variablen ansehen.

 

[datalukas]

Du hast Recht. Man, ich schau die ganze Zeit in den unteren Bereich, weil das ganze ja funktioniert und dann steckt der Fehler oben. Ich dachte, der Compiler meldet das einem gleich (dann würde das Programm gar nicht starten), wenn man in nicht vorhandenes Feld im Array verwendet. Der hat aber nichts gemacht.

Der Debugger hat mich übrigens nicht auf die Codezeile hingewiesen.

 

[asdfman]

Ich dachte, der Compiler meldet das einem gleich

Merkwürdige Vorstellung. Der Compiler meldet einem, wenn er das Programm nicht kompilieren kann und ein paar kleinere häufige Irrtümer, die aber lokal begrenzt sind. Das wars dann aber auch. Wenn es denn überhaupt möglich wäre, zu beweisen, welche Variablen welche Werte annehmen können, woher soll der Compiler denn wissen, dass du das nicht vielleicht absichtlich machst? Gewöhn dir an, dass Software grundsätzlich davon ausgeht, dass der Benutzer weiß, was er tut. Eine Erfahrung, die ich bei meiner ersten Benutzung von mkfs machen musste, daraus dann aber fürs Leben gelernt habe :3

 

[antred]

Der Debugger hat mich übrigens nicht auf die Codezeile hingewiesen.

Hat er nicht? Hmm, ich war der Meinung, er sollte da automatisch anhalten, wenn er schon erkannt hat, dass der Stack korrumpiert worden ist. Dann halt nicht. :\

Ich dachte, der Compiler meldet das einem gleich (dann würde das Programm gar nicht starten), wenn man in nicht vorhandenes Feld im Array verwendet. Der hat aber nichts gemacht.

Nee, so was kann er wirklich nicht! Dazu müßte der Compiler ja eine komplette Programmanalyse vornehmen. Für so was gibt's allerdings Programme wie z.B. Valgrind (open source ... Linux ... eventuell auch für Windows?) oder IBM's Rational Purify (kommerziell, teuer!).

P.S. Und selbst diese Programme können nicht von vorn herein für sämtliche mögliche Pogrammpfade alle möglichen Permutationen simulieren sondern überwachen lediglich im jeweiligen Programmdurchlauf die gerade genommenen Programmpfade.

 

[datalukas]

Wie macht ihr das eigentlich mit den Fehlern beim Programmieren? Mir passieren da extrem leicht Flüchtigkeitsfehler. Außerdem muss man sich oft sehr reindenken und wenn man dann wieder rauskommt, muss man erst mal wieder den Zugang finden.

 

[antred]

Ich persönlich versuche, das Potenzial für Fehler gering zu halten, indem ich mir meine Probleme in möglichst kleine, überschaubare Unterproblemchen aufbreche. Dann löse ich diese kleinen Unterproblemchen und setze sie dann zusammen.

Konkret heißt das, anstatt alles in einer komplexen Riesenfunktion mit wer weiß wie vielen Variablen, Schleifen und if-else-Verzweigungen auszukodieren, bin ich bemüht, x kleine Unterfunktionen zu schreiben ... und ich meine KLEINE ... wenn's mehr als 50 Zeilen werden, ist die Funktion für meinen Geschmack schon wieder zu groß. Dann kann man sich in seinem Programm (wie eine Art Baukastensystem) logisch höher angesiedelte Blöcke an Funktionalität aus x logisch niedriger liegenden Bausteinen zusammenstecken.

Ich habe jetzt dein Programm nicht hinreichend studiert, um beurteilen zu können, ob es sinnvoll wäre, z.B. deine mergeSorting()-Funktion noch weiter in Unterfunktionen aufzuspalten, und außerdem war es ja in diesem Fall so wie so eher ein Gehirnfurz, der dir vielleicht mit kleineren Unterfunktionen genau so passiert wäre.

Was übrigens bei der Entwicklung auch hilft, ist das Überprüfen von Invariablen mittels assert(). Du bist dir sicher, daß x an dieser Stelle nie größer als z sein sollte, dann tue da einfach mal ein assert( x <= z ); hin. Und nur nicht zu geizig mit solchen assert's sein. Kostet dich ja nix. Willst du den so enstandenen Runtime-Overhead nicht, einfach mit -DNDEBUG kompilieren, und die ganzen asserts werden vom Compiler einfach ignoriert.

 

[black90]

Rekursion ist das Zauberwort. Damit fällt der Code sehr klein aus.

 

[TrebuTurbo]

Ich kann nur wärmsten den Youtube-Kanal von AlgoRythmics empfehlen. Da werden verschiedenste Sortieralgorithmen sehr anschaulich dargestellt ;-)
http://www.youtube.com/watch?v=ywWBy6J5gz8

Sonst kann ich black90 nur zustimmen - wenn nix gegen Rekursion spricht würde ich sie verwenden. Dadurch wird es um einiges einfacher und wirklich sehr klein

 

[asdfman]

Ergänzung zu antreds wertvollem Rat sich die Arbeit in Häppchen zu zerteilen: Das Verfahren kann man besonders einfach mit "wishful thinking" umsetzen. Das sieht folgendermaßen aus:

Statt mit den Bausteinen anzufangen und daraus den Algorithmus zusammenzusetzen geht man genau andersherum vor. Man schreibt die Funktion, die man haben will als erstes komplett hin und tut bei den nötigen Bausteinen so, als hätte man sie schon fertig. Zum Beispiel so:

int eval(char *ausdruck) {
    if(istzahl(ausdruck)) return atoi(ausdruck);
    if(istsymbol(ausdruck)) return lookup(ausdruck);
    if(istsumme(ausdruck)) return eval(erstersummand(ausdruck)) + eval(zweitersummand(ausdruck));
    if(istprodukt(ausdruck)) return eval(ersterfaktor(ausdruck)) * eval(zweiterfaktor(ausdruck));
    ...
}

(Spoiler: bin am Telefon mit Auto"korrektur". Kann etliche Fehler enthalten. Die Idee sollte klar sein.)

So weiß man direkt, welche Bausteine man als nächstes benötigt und kann diese dann (wiederum mit "wishful thinking") der Reihe nach implementieren.

Wenn man auf diese Weise vorgeht, erübrigen sich Probleme, dass man vorher geschriebene Teile abändern muss, oder dass sie am Ende sogar völlig überflüssig sind und man Arbeit umsonst gemacht hat.

Allgemein ist der Ansatz divide et impera einer der wichtigsten, um Komplexität handhabbar zu machen und man sollte ihm immer folgen. Und gerade die Handhabung von Kokplexität ist quasi die Definition davon, was das Programmieren eigentlich fundamental ist.

€ 2600 edits an diversen Stellen.