Problem bei einer Aufgabe

Hi!

Habe folgende Aufgabe bekommen:

Schreiben Sie ein Programm in der Sprache C4, welches das Verfahren Mergesort (Sortieren durch Mischen) implementiert.Das Hauptprogramm soll 20 Zahlen von der Console einlesen und in einem Array speichern.Nach der Sortierung sollen die sortierten Zahlen in einer Zeile durch ein Leerzeichen getrennt
wieder ausgeben werden.
Verfahren:
Das zu sortierende Feld wird in jedem Schritt in zwei Teilfelder aufgeteilt. Diese werden dann rekursiv sortiert. Anschließend werden die sortierten Teilfelder wieder zu einem Feld zusammengefügt. Dabei macht man sich zu nutze, daß die beiden Teilfelder bereits sortiert sind.
Rekursiver Algorithmus:
- gegeben ein Feld der Lange n
- ist n = 1, so ist nichts zu tun, sonst
- Zerlege das zu sortierende Feld a in zwei Felder a1 mit Lange n1 = n=2 (ganzzahlige
Division) und a2 mit Lange n2 = n - n1)
- Sortiere a1 und a2 (Rekursion)
- mische a1 und a2 unter Beibehaltung der richtigen Reihenfolge

Sitze nun schon die ganzen Ferien dran und komme nicht weiter.
Meine bisherige Lösung:

prog aufgabe4

void mergesort(int [] array)
{
array= new int [];
   if (array.Length <= 1) 
       print(array);
   else
       int [] linksarray;
	   linksarray= new int [];
	   int [] rechtsarray;
	   rechtsarray= new int [];
	   int i;
	   i=0;
	   while(i<=9)
         {
		 linksarray[i]=array[i];
	     i=i+1;
	     }
	   while(i>=10)
	     {
		 rechtsarray[i]=array[i];
	     i=i+1;
	     }

return  merge(mergesort(linksarray), mergesort(rechtsarray));
}

void  merge(int [] larray, int [] rarray)
{
    int [] neuarray;
	neuarray= new int [];
    larray= new int [];
	rarray= new int [];
	int a;
	int b;
	int c;
	a=0;
	b=0;
	c=0;
    while (larray.Length !=0 && rarray.Length !=0)
	{
        if(larray[a] <= rarray[b])
          neuarray[c]=larray[a];
		  a=a+1;
		  c=c+1;
        else
		  {neuarray[c]=rarray[a];
		  b=b+1;
		  c=c+1;}

    }
    while (larray.Length !=0)
       {
        neuarray[c]=larray[a];
	    a=a+1;
	    c=c+1;
       }
    while (rarray.Length !=0) 
        {
        neuarray[c]=rarray[a];
	    b=b+1;
	    c=c+1;
        }
return neuarray;
}

{
int i;
i=0;
int [] meinarray;
meinarray= new int [];
while(i<=19)
  {read(meinarray[i]);
   i=i+1;
  }
print(mergesort(meinarray));
}

Wäre schön wenn mir das einer berichtigen könnte oder Hilfen gibt.

nwp2

Das ist mehr Java als C. C4 kenn ich nur als Sprengstoff, aber ich versuchs mal in C.

#include <stdio.h>
int array[20];
int temparray[20];

void merge(int *a1, int l1, int *a2, int l2){
	int p1 = 0, p2 = 0; //positionen in der Liste
	for (int i = 0; i < l1 + l2; i++){
		if (p1 == l1) //erste liste zuende
			temparray[i] = a2[p2++];
		else if (p2 == l2) //zweite liste zuende
			temparray[i] = a1[p1++];
		else if (a1[p1] > a2[p2])
			temparray[i] = a2[p2++];
		else
			temparray[i] = a1[p1++];
	}
	//rückkopieren in array
	for (int i = 0; i < l1; i++)
		a1[i] = temparray[i];
	for (int i = l1; i < l1 + l2; i++)
		a2[i-l1] = temparray[i];
}

void mergesort(int *liste, int laenge){
	if (laenge>1){
		mergesort(liste, laenge / 2);
		mergesort(liste + laenge / 2, (laenge+1) / 2);
		merge(liste, laenge / 2, liste + laenge / 2, (laenge+1) / 2);
	}
}	

int main(){
	for (int i = 0; i < 20; i++) scanf("%d", &array[i]);
	mergesort(array, 20);
	for (int i = 0; i < 20; i++) printf("%d ", array[i]);
	printf("\n");
	return 0;
}

Ist von optimal weit entfernt, man kann zum Beispiel durch geschicktes Tauschen das temparray weglassen.

ja das ist so einer vorstufe von c#...

hab deins mal umgeschrieben in c4, hab aber noch ein paar probleme....
ich kann keine Zeiger, also die * verwenden. Hab nur zur not Referenzen(ref) zur Verfügung.
ALso mal den umgeschriebenen Code:

prog aufgabe4neu

    void merge(int a1, int l1,int a2, int l2){
    int p1;
    p1= 0;
    int p2;
	p2= 0; //positionen in der Liste
	int [] array;
    array= new int [20];
    int [] temparray;
    temparray= new int [20];
	int i;
		i=0;
    while (i < l1 + l2){

        if (p1 == l1) //erste liste zuende
            temparray[i] = a2[p2];
			p2=p2+1;
			i=i+1;
        if (p2 == l2) //zweite liste zuende
            temparray[i] = a1[p1];
			p1=p1+1;
			i=i+1;
        if (a1[p1] > a2[p2])
            temparray[i] = a2[p2];
			p2=p2+1;
			i=i+1;
        else
          { temparray[i] = a1[p1];
			p1=p1+1;
		    i=i+1;}
    }
    //rückkopieren in array
	int g;//Hilfsvariable
	g=0;
    while (g < l1){
        a1[g] = temparray[g];
		g=g+1;}
	int j;//Hilfsvariable
    j=l1;
    while(j < l1 + l2){
        a2[j-l1] = temparray[j];
		j=j+1;}
}

void mergesort(int liste, int laenge){
    if (laenge>1){
        mergesort(liste, laenge / 2);
        mergesort(liste + laenge / 2, (laenge+1) / 2);
        merge(liste, laenge / 2, liste + laenge / 2, (laenge+1) / 2);
    }
}   

{
    int [] array;
    array= new int [20];
    int [] temparray;
    temparray= new int [20];
    int i;
	i=0;
    while (i < 20)
	{
	read(array[i]);
	i=i+1;
	}
    mergesort(array, 20);
	int g;
    while ( g < 20)
	{
	print(array[g]);
    print("\n");
	g=g+1;}
}

und hier die Fehler, die mein Compiler anzeigt:

line 30:9 ERROR: Syntax error
line 31:12 NOTE: Parsing resumed here
line 19:28 ERROR: indices are not allowed on type: int
line 23:28 ERROR: indices are not allowed on type: int
line 26:13 ERROR: indices are not allowed on type: int
line 26:22 ERROR: indices are not allowed on type: int
line 27:28 ERROR: indices are not allowed on type: int
line 31:29 ERROR: indices are not allowed on type: int
line 39:9 ERROR: indices are not allowed on type: int
line 44:9 ERROR: indices are not allowed on type: int
line 68:15 ERROR: type of expression is int[*] but context expects type int

Also die indices Fehler liegen ja denk ich mal an den fehlnden Zeiger.
Und die Zeile30/31 nunja der Fehler tritt auf egal ob ich die Klammern nach dem else Teil setze oder auch nicht, weiß also nicht woran der Fehler liegt -.-
Vielleicht noch eine Idee wie ich es umschreibe damit es läuft?

In C kann man nur am Anfang eines Blocks Variablen deklarieren.

Keine Ahnung jedenfalls, die Sprache ist kein "normales" C.

richtig
die fehler sind im übrigen immer 2 zeilen vorher...

nwp2

Versuchs mal mit void merge(int a1[], int l1, int a2[], int l2) und void mergesort(int liste[], int laenge), vielleicht gehts dann.

Edit: Dir fehlen geschweifte Klammern um die if-Konstuktionen Zeilen 16 bis 27.

ja danke, jetzt hab ich nur noch ein problem mit der mergesort funktion...

prog aufgabe4neu

    void merge(int [] a1, int l1,int [] a2, int l2){
    int p1;
    p1= 0;
    int p2;
	p2= 0; //positionen in der Liste
	int [] array;
    array= new int [20];
    int [] temparray;
    temparray= new int [20];
	int i;
		i=0;
    while (i < l1 + l2){

        if (p1 == l1) //erste liste zuende
            {temparray[i] = a2[p2];
			p2=p2+1;
			i=i+1;}
        if (p2 == l2) //zweite liste zuende
            {temparray[i] = a1[p1];
			p1=p1+1;
			i=i+1;}
        if (a1[p1] > a2[p2])
            {temparray[i] = a2[p2];
			p2=p2+1;
			i=i+1;}
        else
           temparray[i] = a1[p1];
		   p1=p1+1;
		   i=i+1;
    }
    //rückkopieren in array
	int g;//Hilfsvariable
	g=0;
    while (g < l1){
        a1[g] = temparray[g];
		g=g+1;}
	int j;//Hilfsvariable
    j=l1;
    while(j < l1 + l2){
        a2[j-l1] = temparray[j];
		j=j+1;}
}

void mergesort(int [] liste, int laenge){
    if (laenge>1){
        mergesort(liste, laenge / 2);
        mergesort(liste + laenge / 2, (laenge+1) / 2);
        merge(liste, laenge / 2, liste + laenge / 2, (laenge+1) / 2);
    }
}   

{
    int [] array;
    array= new int [20];
    int [] temparray;
    temparray= new int [20];
    int i;
	i=0;
    while (i < 20)
	{
	read(array[i]);
	i=i+1;
	}
    mergesort(array, 20);
	int g;
	g=0;
    while ( g < 20)
	{
	print(array[g]);
    print("\n");
	g=g+1;}
}

Kriege jetzt folgende Fehler:

line 49:19 ERROR: type of expression is int but context expects type int[*]
line 49:19 ERROR: type of expression is int[*] but context expects type int
line 49:27 ERROR: type of expression is int but context expects type int[*]
line 50:34 ERROR: type of expression is int but context expects type int[*]
line 50:34 ERROR: type of expression is int[*] but context expects type int
line 50:42 ERROR: type of expression is int but context expects type int[*]

Probier mal:

void mergesort(int [] liste, int laenge){
    if (laenge>1){
        mergesort(liste, laenge / 2);
        mergesort((*liste) + (laenge / 2), (laenge+1) / 2);
        merge(liste, laenge / 2, (*liste) + (laenge / 2), (laenge+1) / 2);
    }
}

kann ja leider keine Zeiger, also * nehmen. Die gibts in c4 nicht

nwp2

Wenn das auch nicht klappt übergebe für jedes Array (int [] array, int position, int länge). Durch den zusätzlichen Parameter position kannst du einen Pointer simulieren. Du musst dann nur jedes array[zahl] durch array[zahl + position] ersetzen.

@bauko
schreib doch bitte nicht ständig c4 das gibts wirklich, nicht nur als sprengstoff

Aja
Muss sagen so langsam wirds echt zu hoch für mich.
Soll ich nun nur mergesort ändern oder das komplette programm?
Kann ich nicht für die Position array[1] usw nehmen?

nwp2

Klar kannst du array[1] benutzen, aber du musst irgendwie "liste + laenge / 2" ausdrücken. liste ist ein Pointer auf ein int Array und der Pointer wird um laenge / 2 hochgezählt. Aber bei dir gibt es keine Pointer, also musst du sie simulieren.

Ich hab mal deinen Code kopiert und entsprechend geändert:

prog aufgabe4neu

    void merge(int [] a1, int pos1, int l1,int [] a2, int pos2, int l2){
    int p1;
    p1= 0;
    int p2;
    p2= 0; //positionen in der Liste
    int [] array;
    array= new int [20];
    int [] temparray;
    temparray= new int [20];
    int i;
        i=0;
    while (i < l1 + l2){

        if (p1 == l1) //erste liste zuende
            {temparray[i] = a2[p2+pos2];
            p2=p2+1;
            i=i+1;}
        if (p2 == l2) //zweite liste zuende
            {temparray[i] = a1[p1+pos1];
            p1=p1+1;
            i=i+1;}
        if (a1[p1+pos1] > a2[p2+pos2])
            {temparray[i] = a2[p2+pos2];
            p2=p2+1;
            i=i+1;}
        else
           temparray[i] = a1[p1+pos1];
           p1=p1+1;
           i=i+1;
    }
    //rückkopieren in array
    int g;//Hilfsvariable
    g=0;
    while (g < l1){
        a1[g+pos1] = temparray[g];
        g=g+1;}
    int j;//Hilfsvariable
    j=l1;
    while(j < l1 + l2){
        a2[j-l1+pos2] = temparray[j];
        j=j+1;}
}

void mergesort(int [] liste, int pos, int laenge){
    if (laenge>1){
        mergesort(liste, pos, laenge / 2);
        mergesort(liste, pos + laenge / 2, (laenge+1) / 2);
        merge(liste, pos, laenge / 2, liste, pos + laenge / 2, (laenge+1) / 2);
    }
}   

{
    int [] array;
    array= new int [20];
    int [] temparray;
    temparray= new int [20];
    int i;
    i=0;
    while (i < 20)
    {
    read(array[i]);
    i=i+1;
    }
    mergesort(array, 0, 20);
    int g;
    g=0;
    while ( g < 20)
    {
    print(array[g]);
    print("\n");
    g=g+1;}
}

Ich hoffe mal dass ich nichts übersehen habe. Mit etwas Glück läuft es so.

Mir fällt gerade auf dass ihr dynamische Arrays habt. Vielleicht ist es Cleverer für die Listen jeweils neue Arrays zu bauen und diese zurückzugeben. Ich habe leider keine Ahnung wie weit diese dynamischen Arrays definiert sind.

Ja werde dein Code gleich mal testen, hatte grade selberprobiert und eben versucht in der merge funktion die listen durch hilfsarrays zu ersetzen.

void mergesort(int [] liste, int laenge){
int [] helpliste;
helpliste= new int[];
    if (laenge>1){
	    int i;
		i=0;
		int g;
		g=laenge/2;
		while(i<laenge/2){
		helpliste[i]=liste[g];
		i=i+1;
		g=g+1;}
		mergesort(liste, laenge / 2);
        mergesort(helpliste, (laenge+1) / 2);
        merge(liste, laenge / 2, helpliste, (laenge+1) / 2);
    }
}

dann läuft das Programm zwar bricht aber mit einer arrayoutofbounceexception ab

@bauko

gibts den c4 compiler zum download? bzw. kannst mal nen link posten was du da verwendest?

Also hab grad deinen Code getestet, ist wie bei mir. Er bricht ab in Zeile 24 mit der arrayoutofbounceexception ab.

@noobLolo http://swt.informatik.uni-halle.de/lehre/2009ws/oop/
dort sind unten die bisherigen Skripte zu C1 bis C4.
SInd eben einfache Vorsprachen um langsam zu c# heranzuführen.
mit einem C4 compiler kann ich leider nicht diehnen,da es nur dateien gibt, um im Linux terminal zu kompilieren

Hab es jetzt nochmal geändert.Mein Code sieht nun so aus:

prog aufgabe4neu

    void merge(int [] a1, int l1,int [] a2, int l2){
    int p1;
    p1= 0;
    int p2;
	p2= 0; //positionen in der Liste
    int [] temparray;
    temparray= new int [20];
	int i;
	i=0;
    while (i < l1 + l2){

        if (p1 == l1) //erste liste zuende
            {temparray[i] = a2[p2];
			p2=p2+1;
			i=i+1;}
        if (p2 == l2) //zweite liste zuende
            {temparray[i] = a1[p1];
			p1=p1+1;
			i=i+1;}
        if (a1[p1] > a2[p2])
            {temparray[i] = a2[p2];
			p2=p2+1;
			i=i+1;}
        else
           temparray[i] = a1[p1];
		   p1=p1+1;
		   i=i+1;
    }
    //rückkopieren in array
	int g;//Hilfsvariable
	g=0;
    while (g < l1){
        a1[g] = temparray[g];
		g=g+1;}
	int j;//Hilfsvariable
    j=l1;
    while(j < l1 + l2){
        a2[j-l1] = temparray[j];
		j=j+1;}
}

void mergesort(int [] liste, int laenge){
int [] helpliste;
helpliste= new int[laenge/2];
int [] addliste;
addliste= new int[laenge/2];
    if (laenge>1){
	    int i;
		i=0;
		int a;
		a=0;
		int g;
		g= laenge/2;
		while(i<laenge/2){
		addliste[i]=liste[i];
		i=i+1;}
		while(i>=laenge/2){
		helpliste[a]=liste[g];
		a=a+1;
		g=+1;}
		mergesort(addliste, laenge / 2);
        mergesort(helpliste, (laenge+1) / 2);
        merge(addliste, laenge / 2, helpliste, (laenge+1) / 2);
    }
}   

{
    int [] array;
    array= new int [20];
    int [] temparray;
    temparray= new int [20];
    int i;
	i=0;
    while (i < 20)
	{
	read(array[i]);
	i=i+1;
	}
    mergesort(array, 20);
	int g;
	g=0;
    while ( g < 20)
	{
	print(array[g]);
    print("\n");
	g=g+1;}
}

Leider bricht er mit folgender Fehlermeldung ab:

line 60:27: Error: ArrayIndexOutOfBoundException

Im Skript steht dazu:
Für Indexzugriffe idx auf eine Reihung x muss
0 <= idx < x.Length gelten
+ Ansonsten bricht das Programm mit einer
ArrayIndexOutOfBoundException ab.
Jemand noch eine Idee, erkenne nämlich wirklich nicht warum mein array überläuft...

evtl. weil du i nicht änderst und in ne endlos schleife rennst?

while(i>=laenge/2){
  helpliste[a]=liste[g];
  a=a+1;
  g=+1;
}

prog aufgabe4neu

    void merge(int [] a1, int l1,int [] a2, int l2){
    int p1;
    p1= 0;
    int p2;
	p2= 0; //positionen in der Liste
    int [] temparray;
    temparray= new int [20];
	int i;
	i=0;
    while (i < l1 + l2){

        if (p1 == l1) //erste liste zuende
            {temparray[i] = a2[p2];
			p2=p2+1;
			i=i+1;}
        if (p2 == l2) //zweite liste zuende
            {temparray[i] = a1[p1];
			p1=p1+1;
			i=i+1;}
        if (a1[p1] > a2[p2])
            {temparray[i] = a2[p2];
			p2=p2+1;
			i=i+1;}
        else
           temparray[i] = a1[p1];
		   p1=p1+1;
		   i=i+1;
    }
    //rückkopieren in array
	int g;//Hilfsvariable
	g=0;
    while (g < l1){
        a1[g] = temparray[g];
		g=g+1;}
	int j;//Hilfsvariable
    j=l1;
    while(j < l1 + l2){
        a2[j-l1] = temparray[j];
		j=j+1;}
}

void mergesort(int [] liste, int laenge){
int [] helpliste;
helpliste= new int[laenge/2];
int [] addliste;
addliste= new int[laenge/2];
    if (laenge>1){
	    int i;
		i=0;
		int a;
		a=0;
		int g;
		g= laenge/2;
		while(i<laenge/2){
		addliste[i]=liste[i];
		i=i+1;}
		if(i==10){
		  while(i<laenge){
		  helpliste[a]=liste[g];
		  a=a+1;
		  g=g+1;
		  i=i+1;}
		  }
		mergesort(addliste, laenge / 2);
        mergesort(helpliste, (laenge+1) / 2);
        merge(addliste, laenge / 2, helpliste, (laenge+1) / 2);
    }
}   

{
    int [] array;
    array= new int [20];
    int [] temparray;
    temparray= new int [20];
    int i;
	i=0;
    while (i < 20)
	{
	read(array[i]);
	i=i+1;
	}
    mergesort(array, 20);
	int g;
	g=0;
    while ( g < 20)
	{
	print(array[g]);
    print("\n");
	g=g+1;}
}

So jetzt läuft es schonmal im mergesort-Teil,nur im merge-Teil kommt jetzt der Fehler.Langsam verzeifel ich echt.

line 19:32: Error: ArrayIndexOutOfBoundException
Aborted

Da läuft nun auch noch ein array über -.-

Setz mal den else-Zweig auch in geschweifte Klammern:

void merge(int [] a1, int l1,int [] a2, int l2){ 
(...)
while (i < l1 + l2){ 
(...)
    else 
       {temparray[i] = a1[p1]; // <- hier
       p1=p1+1; 
       i=i+1;}                 // <- und da
}