mergesort/rekursion

[babuschka]

hallo zusammen,
ich hätt' da mal ein mehr oder minder großes problem :roll: . ich möchte ein programm realisieren, welches folgendes beinhalten soll:
-eine funktion zum einlesen einer reihe beinhaltet-durch eingabe der array-größe durch den benutzer über standardeingabe soll die größe des anfangs"feldes" festgelegt werden.
-dieses feld soll im nächsten schritt mit der anzahl der zuvor eingegeben werte durch eingabe dieser initialisiert werden.
-das so entstandene array soll nun mit hilfe von mergesort gemischt und die ergebnisse in ein neues hilfsfeld kopiert werden, welches dann ausgegeben werden soll--> result.

PROBLEME meinerseits, da ich noch immer im absoluten Anfängerstadium schwebe:
-weiß nicht so recht wo und wie ich die variablen deklarieren/initialisieren soll (in main, oder den funktionen selbst)
-wie mache ich es, dass die funktion zu devide/conquer die eingabe entweder zur hälfte teilt, oder wenn ungerade in höchstens von 1 verschiedene felder?
-ich kenne bisher nur "while"-"for"-"switch"-"return"..also einfachste formen zur umsetzung.

HIER im Folgenden mal das, was mir bisher dazu einfiel (Ist leider nicht allzu viel):

public class mergesort
{
	public static void main (String [] args)
	{
		System.out.println("Eingabe der gewünschten Laenge der Folge: ");
		int length= EM02.liesInt();

		System.out.println("Geben Sie jetzt die zu sortierenden Werte ein: ");
		int [] reihe=new int [length];

		int [] f1,f2,sorted;



	}//Ende main


	/*public static int read (int[]folge) //Funktion zum Einlesen der Folge
	{
		int anfang = folge[0];
		int
		for (int i=1;i<folge.length;i++)
		{
			if (folge[i]>anfang)
			anfang = folge[i];
		}
			return folge;
	}*/Ende read


	public static int [] merge (int[]f1, int[]f2)
	{
		int i=0, j=0, k=0;
		int[]sorted = new int[f1.length + f2.length];

		while ((i<f1.length) && (j<f2.length))
		{
			if	(f1[i] < f2[j])
				sorted [k++] = f1[i++];

			else
				sorted [k++] = f2[j++];
		}
		while (i<f1.length) sorted[k++] = f1[i++];
		while (j<f2.length) sorted[k++] = f2[j++];

		return sorted;
	}//Ende merge


}//Ende mergesort

Zum einlesen einer Folge habe ich leider keine rechte Idee, wie ich weitermachen soll, allerdings kenne ich die
Methode x.liesInt() zum einlesen von int-Werten.
Ich wäre soo dankbar für ein paar Denkanstöße :wink: , Danke...
grüße, s.ho

 

[Wildcard]

weiß nicht so recht wo und wie ich die variablen deklarieren/initialisieren soll (in main, oder den funktionen selbst)

Variablen immer so lokal wie möglich, also in der Methode in der sie gebraucht werden.

wie mache ich es, dass die funktion zu devide/conquer die eingabe entweder zur hälfte teilt, oder wenn ungerade in höchstens von 1 verschiedene felder?

du hast ein eingabeArray mit länge x.
jetzt machst du 2 neue, eins mit x/2, das andere mit x-x/2.
Jetzt machst du eine for-schleife von 0 bis x-1.
je nachdem ob du in einem geraden oder ungeraden duchlauf bist verteilst du
die Werte auf die beiden Arrays.

Titel: mergesort/rekursion

was hat das mit rekursion zu tun?

 

[babuschka]

erstmal danke für die anregungen, werde das gleich mal versuchen in die TAT umzusetzen
was das mit rekursion zu tun hat: ? stimmt, blöder titel. wollte
ursprünglich mit rekursion arbeiten..

 

[Wildcard]

wollte ursprünglich mit rekursion arbeiten..

das muss ich schon aus Prinzip unterstützen! :toll:

 

[babuschka]

so, nunmehr eine weile später: leider bin ich noch gar nicht bis dahin gekommen, wo ich die eingelesene folge teilen muss;-(
bisher kann ich nur eine größe für ein array einlesen, dann endet das programm, bevor ich mit eingabe von werten das array füllen kann..vielleicht kann mir jemand sagen, wo oeben der fehler liegt bis dahin?? ich habe ehrlich gesagt den überblich über meine vielen variablen verloren und verstehe das, was ich mit den [] feldern gemacht habe selber nur bedingt...
hilfesuchend: s.ho

 

[Wildcard]

du musst in der main die read methode aufrufen, und ihr reihe übergeben

 

[sliwalker]

Hilft Dir das?

public class mergesort 
{ 
   public static void main (String [] args) 
   { 
      System.out.println("Eingabe der gewünschten Laenge der Folge: "); 
      int length= EM02.liesInt(); 
      int [] reihe=new int [length]; 

      System.out.println("Geben Sie jetzt die zu sortierenden Werte ein: "); 
      for(int a = 0; a < length; a++)
     {
        System.out.println("Wert " + a);
        reihe[a] = EM02.liesInt();
     }
      

      int [] f1,f2,sorted; 



   }//Ende main

greetz
SLi

 

[babuschka]

danke ja, darin erkenn' ich die struktur des ursprungs schon eher wieder nur, dass der erste wert für a so in der eingabe immer schon 0 ist..muss wohl heute noch etwas länger machen, mit plan..bis hierher erstmal dankeschön!

 

[babuschka]

danke ja, darin erkenn' ich die struktur des ursprungs schon eher wieder nur, dass der erste wert für a so in der eingabe immer schon 0 ist..muss wohl heute noch etwas länger machen, mit plan..bis hierher erstmal dankeschön!

 

[babuschka]

ich schon wieder.. :?
es ist nun einige tage her, dass ich die erste frage zu meinem programm gestellt habe und nun bin ich weiter gekommen, komme allerdings nicht zum ende! ich weiß, es gibt viiele erklärungen und beispiele zu mergesort, quicksort im netz, die helfen mir aber im moment wirklich nicht weiter, weil ich wohl einfach einen "Denk"fehler habe.
Was im Programm nicht richtig klappt: Die Sortierung der Teilfelder f1 und f2.
Was noch fehlt: Wenn die Sortierung denn funktionieren würde, will ich die sortierten Teilfolgen mit Merge zusammenfügen--> wie ich das mache weiß ich schon.

Frage ist nun: Ist es überhaupt nötig, dass ich in main vor dem Quicksort schon das eingelesene Array teile?
Oder ist das ok und ich muss aber Quicksort nicht "vollständig" anwenden? Oder kann ich die beiden Teilreihen eigentlich auch mit Merge sortieren, ohne dass ich Hilfsfelder brauche (rekursiv)?? Ich wäre seeehr dankbar, wenn jemand sich das mal ansehen könnte und vielleicht meinen Fehler findet..DANKE :wink:

public class mergesort2
{
	//Hauptprogramm
	public static void main (String [] args)
	{
		System.out.print("Eingabewert fuer die Laenge der Reihung: ");
		int n = EM02.liesInt();
		int [] werte = lesen (n);//Funktionsaufruf lesen einer Reihe
		ausgabe(werte, n);		 //Funktionsaufruf ausgabe einer Reihe

		//Eingelesene Reihe wird in zwei Teilreihen geteilt
		int n1 = n / 2;
		int n2 = n - n1;
		int [] f1 = new int [n1];
		int [] f2 = new int [n2];

		for (int i = 0; i<n; i++)
		{
			if (i<n1)
				f1[i] = werte[i];

			else
				f2[i-n1] = werte[i];

		}

		//Funktionsaufruf Quicksort - Die Teilreihen sollen REKURSIV sortiert werden
		quicksort(n1, 0, f1);
		quicksort(n2, 0, f2);
		int [] ergebnis = merge(f1, f2, n);

		ausgabe(werte, n);
		ausgabe(f2, n2);


		//System.out.print(n1 + " " + n2);


		//System.out.println("Ihre Eingabe: "+ "\n" + "Die Reihung wird nun sortiert." );

	}//Ende main

	//Quicksort
	static void quicksort(int rechts, int links, int [] werte)
	{

		int i = links;
		int j = rechts - 1;

		if (i < j)
		{

			int pivot = werte[rechts - 1]; //Pivot-Element bekommt Wert des rechten äußeren Feldes

			while (i < j)
			{
				while ((werte[i] <= pivot) && (i < rechts - 1))
				{
					i++;
				}


				while ((werte[j] > pivot) && (j > links))
				{
					j--;
				}

				//Vertausche die Werte der Felder mit Zwischenspeicher x
				//wenn nicht aneinander vorbeigelaufen
				if (i < j)
				{
					int x = werte[i];
					werte [i] = werte[j];
					werte [j] = x;
					//bereits getauschte Felder müssen nicht noch einmal betrachtet werden
					//i++;
					//j--;
				}

			} //Ende While i <= j

			//Pivot-Element soll getauscht werden?
			int y = werte[rechts - 1];
			werte[rechts - 1] = werte[i];
			werte[i] = y;


			quicksort(i - 1, links, werte);
			quicksort(rechts, i + 1,werte);


		}

	}

	//Funktion zum einlesen der Reihung
	public static int [] lesen (int n)
	{
		System.out.println("Eingabe der Werte fuer die Reihung: ");
		int [] reihe = new int [n];

		for (int i = 0; i<n; i++)
		{
			reihe[i] = EM02.liesInt();

		}

		return reihe;
	}

	//Funktion zur Ausgabe einer Reihung
	static void ausgabe(int [] werte, int n)
	{
		System.out.print("Ihre Reihe lautet: ");

		for (int i = 0; i<n; i++)
		{
			System.out.print(" " + werte[i]);
		}
			System.out.println();

	}



}//Ende Mergesort

[edit by becstift: Code Tags eingefügt]