MergeSort Problem
-
Hallo alle zusammen,
ich befasse mich zur Zeit mit einer Aufgabe, in der es Hauptsächlich um den MergeSort befehl geht. Mein Code sieht momentan folgendermaßen aus:void merge_sort_mod( int liste[], const int groesse, int *buffer ) { /* * add your code here! */ int haelfte1[groesse/2]; int haelfte2[(groesse + 1)/2]; /* Für den Fall, dass man eine ungerade Größe hat */ int i; for(i = 0; i < groesse/2; ++i) haelfte1[i] = liste[i]; for(i = groesse/2; i < groesse; ++i) haelfte2[i - groesse/2] = liste[i]; MergeSort(haelfte1,groesse/2); MergeSort(haelfte2,(groesse + 1)/2); int *pos1 = &haelfte1[0]; int *pos2 = &haelfte2[0]; for(i = 0; i < groesse; ++i){ if(*pos1 <= *pos2){ liste[i] = *pos1; if (pos1 != &haelfte2[(groesse+1)/2 - 1]) { // pos1 nicht verändern, wenn der größte Wert mehrmals vorkommt if(pos1 == &haelfte1[groesse/2 - 1]){ pos1 = &haelfte2[(groesse+1)/2 - 1]; } else{ ++pos1; } } } else{ liste[i] = *pos2; if(pos2 == &haelfte2[(groesse + 1)/2 - 1]){ pos2 = &haelfte1[groesse/2 - 1]; } else{ ++pos2; } } } return; }Die Funktion wird dann halt später im Programm aufgerufen.
Leider kommt bei meinem Compiler folgende Fehlermeldung:
[Linker error] undefined reference toMergeSort' [Linker error] undefined reference toMergeSort'
ld returned 1 exit statusZur Info: Ich benutze Dev-C++ 4.9.9.2 auf Windows Vista
Kann mir jemand sagen, wie ich das Problem lösen kann, bzw wie ich den MergeSort Befehl richtig anwende?
Danke schon mal im voraus.Edit: Ja, dieser Code ist zum größten Teil nicht von mir geschrieben, ich würde ihn aber trotzdem gerne verstehen, vor allem, wie der Befehl MergeSort genau arbeitet.
-
Bevor da irgendjemand Arbeit in eine Antwort investiert der Hinweis: Der Code ist mehr oder weniger identisch mit dem hier:
http://de.wikibooks.org/wiki/Algorithmen_und_Datenstrukturen_in_C/_Mergesort
-
Jap, ist auch nur leicht abgeändert, klappen tut's nur leider trotzdem nicht
-
Bei dir gibt es keinen MergeSort-Befehl.
Da es ihn nicht im Standard gibt, musst du dich selber darum kümmern.Das Beispiel aus dem Link von Bashar arbeitet mit Rekursion (die Funktion ruft sich selber auf). Das geht aber nur, wenn auch die Namen identisch sind.
-
D.h. MergeSort ist kein vordefinierter C-Befehl?
Also müsste ich die oberste Zeile beispielsweise invoid MergeSort (int liste[], const int groesse, int *buffer)ändern?
-
Ja, die hättest du nie verändern dürfen.
Code abschreiben, den man nicht versteht, und damit herumspielen, ist nicht Programmieren. Besser wäre, erst zu lernen, wie Rekursion funktioniert.
-
Okay, danke
Ist schon mal ganz gut zu wissen, dass das kein eigener Befehl ist
Ich werde das jetzt erstmal weiter versuchen zu verstehen. Wenn das nicht klappt, meld ich mich hier noch mal
-
Der Aufruf einer Funktion muss auch zu der Definition passen.
Anzahl, Typ und Reihenfolge der Paramter müssen eingehalten werden.
-
Wie könnte man denn die von Bashar gepostete Funktion aufrufen?
Also ich hab jetzt meine main-Funktion und dann hab ich einfach folgende Zeile genommen:MergeSort( 8, 10);Also einfach aus Versuchszwecken 2 Werte eingegeben für die beiden Eingabeparameter. Klappen tut's nur immer noch nicht
-
Was sollte denn da auch passieren? Was soll sortiert werden? 8 und 10? Wo soll das Ergebnis hin? Das macht doch schon allein logisch keinen Sinn. Und erst recht nicht, wenn man die Signatur der Funktion ansieht, die eine andere Anzahl an Parametern (aus gutem Grund) und einen ganz anderen Typ an Parametern erwartet (ebenfalls aus gutem Grund).
Funktionsaufrufe sind absolute Grundlagen, drittes Kapitel in einem Anfängerlehrbuch ungefähr. Du kannst nicht Programmieren lernen indem du einfach irgendwo Code abschreibst und damit herum experimentierst! Haben schon viele versucht, es wird nie was draus.
c.rackwitz schrieb:
Wenn du selber Code schreibst, musst du ihn auch verstehen. Code ist kein Haufen von wahllos zusammengeschmissenen Buchstaben und Zeichen, Code ist Logik pur. Du musst genau wissen, warum du wo und welches Zeichen setzt.
Wenn du eine Aufgabe hast, MergeSort zu implementieren (durchaus eine fortgeschrittene Aufgabe!), aber die Grundlagen der Sprache verschlafen hast, dann bist du in deinem Kurs bereits ziemlich weit abgehängt. Deine Lehrer kennen den Wikipediacode auch (trotz deines "cleveren" Versuchs, ein paar Namen zu ändern
) und wenn du ihn nicht einmal zum Laufen bringen kannst, dann glaubt dir sowieso niemand, dass du das selber geschrieben hast. Du musst 2-4 Wochen Stoff nachholen, wenn du irgendwie an die Aufgabe rangehen willst. Das musst du machen, das kann und wird ein Internetforum nicht für dich tun.
-
Slisus schrieb:
Edit: Ja, dieser Code ist zum größten Teil nicht von mir geschrieben, ich würde ihn aber trotzdem gerne verstehen, vor allem, wie der Befehl MergeSort genau arbeitet.
Du hast drei Probleme
* Du hast das Problem nicht verstanden. Was genau soll sortiert werden.
* Du weisst nicht wie die Lösung funktioniert.
* Du kannst die Sprache nicht.Den "Befehl" Mergesort hast du schon vor dir. Mehr ist das nicht.
Wie er funktioniert, kannst du dir bei youtube ansehen.
Z.B:http://www.youtube.com/watch?v=EeQ8pwjQxTModer auch
als Tanz:http://www.youtube.com/watch?v=XaqR3G_NVooDie Sprache musst du selber lernen.
-
So, die MergeSort Funktion hab ich jetzt geschafft richtig ins das vorgegebene Programm zu implementieren. Als nächstes sollen wir jetzt aber den Natural Mergesort Algorithmus anwenden, also er gucken, ob es schon runs gibt. Meine Idee war bisher folgendes:
void merge_sort_mod( int numbers[], const int zahlen_anzahl) { if(zahlen_anzahl > 1){ /* ------------ Aufspalten der Zahlen ----------- */ /* Schnittstelle finden */ int cut=0; int j; for (j=0; j < zahlen_anzahl/2; j++) { if (cut==0) { /* Wenn cut einen Wert erhalten hat, wurde schon eine Schnittstelle gefunden */ if (cut==0){ if (numbers[zahlen_anzahl/2 + j] > numbers[zahlen_anzahl/2 + j + 1]) cut = (zahlen_anzahl/2 + j); } if (cut==0) { if (numbers[zahlen_anzahl/2 - j] < numbers[zahlen_anzahl/2 - j - 1]) cut = (zahlen_anzahl/2 - j - 1); } } else break; } int haelfte1[cut]; int haelfte2[(zahlen_anzahl - cut)]; int i; for(i = 0; i < cut; i++) /*In die erste Hälfte werden die ersten Zahlen reingeschrieben */ haelfte1[i] = numbers[i]; for(i = cut; i < zahlen_anzahl; i++) /*In die zweite Hälfte werden die übrigen Zahlen reingeschrieben */ haelfte2[i - cut] = numbers[i]; /*--------- Funktion wird in sich selber aufgerufen -------------*/ merge_sort_mod(haelfte1, cut); /*Die Funktion ruft sich selber auf, die Anzahl der Zahlen und die die Zahlen in jedem "Abschnitt" verändern sich dabei jedes mal, bis zahlen_anzahl = 1) */ merge_sort_mod(haelfte2,(zahlen_anzahl - cut)); /* --------- Sortieren der Zahlen ------------ */ int *pointer1 = &haelfte1[0]; int *pointer2 = &haelfte2[0]; for(i = 0; i < zahlen_anzahl; i++){ if(*pointer1 <= *pointer2){ numbers[i] = *pointer1; if (pointer1 != &haelfte2[(zahlen_anzahl - cut) - 1]) { // pointer1 nicht verändern, wenn der größte Wert mehrmals vorkommt if(pointer1 == &haelfte1[cut - 1]){ pointer1 = &haelfte2[(zahlen_anzahl - cut) - 1]; } else{ pointer1++; //Der Pointer zeigt auf die nächste Zahl } } } else{ numbers[i] = *pointer2; if(pointer2 == &haelfte2[(zahlen_anzahl -cut ) - 1]){ pointer2 = &haelfte1[cut - 1]; } else{ pointer2++; } } } } }Vielleicht noch zur Ergänzung: numbers[] sind Zahlen von 0 - zahlen_anzahl die vorher schon gemischt wurden.
Hab ich da irgendwo einen Denkfehler drin?
Wie immer, danke schon mal für die Antworten
