Rekursiv-Sortieren

[drpingoo]

Hallo zusammen!

Ich bins mal wieder. Bin gerade daran, wie der Titel dieses Thema schon verlauten lässt, eine Rekursiv-Sortierung vorzunehmen. Das Element a[0] sollte grösser sein als das Element a[1] etc. Ich weiss nicht, ob ich es ganz richtig gemacht habe, ich füge den Code mal hinzu (bei void sort (int i) ), denn beim Output kommt dann etliche Male rot angestrichen, dass es einen Fehler gäbe. Ich hab bei void sort übrigens zweilmal die"if" verwendet, da es bei "else" komischerweise immer einen Fehler feststellt... Kann mir da jemand weiterhelfen?

lg

Exception in thread "main" java.lang.StackOverflowError
at array.SortArray.sort(SortArray.java:77)
at array.SortArray.sort(SortArray.java:77)
at array.SortArray.sort(SortArray.java:77)
at array.SortArray.sort(SortArray.java:77) etc.

package array;

import java.util.Random;
import java.util.*;
/**
* Informatik II - SS2007 <br>
* Uebungsserie 2, Aufgabe 1 <br>
* Template for class SortArray.java <br>
*
* @author Silvia Santini
*/

public class SortArray {
  // int-Array (15 elements)
  int[] a = new int[15];
  int myarray;
  int length() {
	return 0;
}
  /**
   * insert comments here
   */
 void initialize() {

	  for(int i=0; i<a.length; i++)
		 { 
		 int myarray = a[i];
		  Random f = new Random();
	      int z = Math.abs(f.nextInt(1000));
	     
	      a[i]=z;
	      myarray=z;
		// System.out.println(a[i]);
	      
	 };
	  

    System.out.println("Implement here: initialization");
 }

  /**
   * insert comments here
   */
  void print() {
		
	 for(int i=0; i<a.length;i++) {
		 int arr = a[i];
		// System.out.println(arr);
	      
		
		  
	 }
	
	      
	
	      
	 };
		
	 
  
  
  

  /**
   * insert comments here
   */
  void sort(int i) {
	  i = 0;
	  int j = i+1;
	  if( a[i] <= a[j]);
	  {
	  int temp = j;
	   j = i;
	   i = temp;
	  };
	   if(a[i] >= a[j]);
	   {sort(i+1);
	   }
	   
	  
	 
	  
	  
	/*  
	  while( a[i] > a[i+1])
	  {int b=a[i];
	   a[i]=a[i+1];
	   a[i+1] =b;}
	  }
  
	*/  
	  /*while (int j>0 && curElement < a[j-1]) {
			a[j]=a[j-1];  //move elements forward
			j = j-1;
	  System.out.println("Implement here: sorting method");
   */
  
  }
  /**
   * insert comments here
   */
  public static void main(String[] args) {
    
	
      
      // An instance of the class SortArray need to be created
      // to access class' Methods
      SortArray s = new SortArray();

      // Call to method methodName with s.<methodName>
      // Initialize:
      s.initialize();

      System.out.println("Array not sorted:");
      // Output, not sorted:
      s.print();
   
      
      
      // Sorting (Which parameter as input?)
      s.sort(9999);

      System.out.println("Array sorted:");
      // Output, sorted:
     s.print();
   }
 }

 

[kle-ben]

Hi,

also das wichtigste für eine rekursive Funktion ist eine Abbruchbedingung.
Die sollte man sich als erstes bei der Implementierung einer rekursiven Funktion
überlegen. Wenn du das hast, bekommst du auch sicher keinen stack overflow.

Wahrscheinlich wolltest du sowas mit dem Parameter i machen, den du zu beginn
jedoch jedes mal überschreibst.

Desweiteren solltest du dir noch mal die Syntax eines if Statements
genau anschauen.Bzw. an welchen Stellen du Semikolons setzten musst
und was diese für auswirkungen haben.

Gruß,
Benny

 

[drpingoo]

Ok, hab mal ein bisschen abgeändert, aber es funktioniert immer noch nicht. Was meint ihr dazu:

package array;

import java.util.Random;
import java.util.*;
/**
* Informatik II - SS2007 <br>
* Uebungsserie 2, Aufgabe 1 <br>
* Template for class SortArray.java <br>
*
* @author Silvia Santini
*/

public class SortArray {
  // int-Array (15 elements)
  int[] a = new int[15];
  int myarray;
  int length() {
	return 0;
}
  /**
   * insert comments here
   */
 void initialize() {

	  for(int i=0; i<a.length; i++)
		 { 
		 int myarray = a[i];
		  Random f = new Random();
	      int z = Math.abs(f.nextInt(1000));
	     
	      a[i]=z;
	      myarray=z;
		// System.out.println(a[i]);
	      
	 };
	  

    System.out.println("Implement here: initialization");
 }

  /**
   * insert comments here
   */
  void print() {
		
	 for(int i=0; i<a.length;i++) {
		 int arr = a[i];
		// System.out.println(arr);
	      
		
		  
	 }
	
	      
	
	      
	 };
		
	 
  
  
  

  /**
   * insert comments here
   */
  void sort(int i) {
	 
	  int j = i+1;
	 while(a[i] <= a[j])
	  
	  {
	  int temp = a[j];
	   a[j] = a[i];
	   a[i] = temp;
	   i++;
	   j--;
	  };
	   if(a[i] >= a[j]);
	   {sort(i+1);
	   }
	   
	  
	 
	  
	  
	/*  
	  while( a[i] > a[i+1])
	  {int b=a[i];
	   a[i]=a[i+1];
	   a[i+1] =b;}
	  }
  
	*/  
	  /*while (int j>0 && curElement < a[j-1]) {
			a[j]=a[j-1];  //move elements forward
			j = j-1;
	  System.out.println("Implement here: sorting method");
   */
  
  }
  /**
   * insert comments here
   */
  public static void main(String[] args) {
    
	
      
      // An instance of the class SortArray need to be created
      // to access class' Methods
      SortArray s = new SortArray();

      // Call to method methodName with s.<methodName>
      // Initialize:
      s.initialize();

      System.out.println("Array not sorted:");
      // Output, not sorted:
      s.print();
   
      
      
      // Sorting (Which parameter as input?)
      s.sort(999);

      System.out.println("Array sorted:");
      // Output, sorted:
     s.print();
   }
 }

lg

 

[SONY2]

Sieht ein wenig besser aus, allerdings setzt du vor dem rekursiven Aufruf immernoch ein überflüssiges und falsches Semikolon. Dieses Semikolon ist in Java eine leere Anweisung und somit zählt es dann zu deiner if. Somit wird der Block ( der eigentlich der if block sein soll) immer ausgeführt und du hast eine Endlosschleife.
Warum versuchst du eigentlich das Rad neu zu erfinden. Es gibt schon genügend Sortier Algorithmen, welche du natürlich nicht 1 zu 1 kopieren sollst (dann wär der Lern Effekt wohl weg), aber durchaus als Denkanstoss nutzen könntest.
Suchen könntest du unter anderem nach Quicksort, Heapsort oder Bubblesort.
Falls du nix finden solltest dann Poste ich gerne einen Sortieralgorithmus.

Gruß

sony2

 

[drpingoo]

Ich hab mit die Quicksort-Methode bereits angeschaut, aber da hat es immer mehrere Variablen am Anfang der Mehtode in Klammern, bei mir ist es jedoch nur das i, deshalb kann ich beim Rekursivaufruf nicht alles so schön ändern wie dort. Und es MUSS eine Rekursivftk. sein. Also, wenn ich das Semikolon wegnehmen würde, ist die Sache aber, so wie ich dich verstanden habe, immer noch nicht gegessen, oder?

lg

 

[SONY2]

Hast recht damit allein ist die Sache wohl nicht gegessen. Ist aber halt ein grober Fehler. Ich muss ehrlich zugeben das ich den Gedanken hinter deiner sort-Methode nicht ganz verstehe. Du willst i als Parameter nutzen aber veränderst es in der Methode so, das eine ArrayIndexOutOfBoundsException auftreten kann bzw. auftritt.
Warum kannst du nicht mehr Parameter als den einen Nutzen ... ist das in der Aufgabenstellung so vorgegeben? Falls nicht wäre wirklich zu überlegen mit mehr Parametern zu arbeiten. FAlls es aber direkt die Aufgabenstellung ist nur diesen einen Parameter zu nutzen, dann ist der Quicksort wirklich nicht zu gebrauchen. Glaube aber zu wissen (bin mir wirklich nicht mehr sicher... is schon ein bisschen her) das zum Beispiel der Bubblesort Algorithmus nur einen Parameter, nämlich die Anzahl der zu sortierenden Elemente als Parameter verlangt ( wäre in deinem Fall dann a.length ). Is aber wirklich ein sehr uneffizienter Sortieralgorithmus und sollte gerade für große Datenmengen nicht benutzt werden.

Hoffe ich konnte wenigstens ein bisschen Helfen.

Gruß

sony2

 

[drpingoo]

Ja, es darf da nur einen Parameter eben. Also die Augabenstellung ist, dass man die Elemente der Reihe nach sortieren soll und zwar so, dass das erste Element, also a[0], grösser oder gleich gross ist wie das darauffolgende. Zuerst wird bei der Methode initialize eben eine Zufallszahl genereirt, die dann bei print() ausgegeben wird und bei void sort() sortiert werden soll. i sollte das gerade bearbeitete Element sein, also durch das ganze Array durchgehen und, falls nötig, mit j vertauscht werden. Es kommt bei Der Aufgabe auch nicht darauf an, ob sie mehr Speicher braucht oder nicht, aber du hast Recht, das hab ich auch gelesen, die Quicksort-Methode ist da wirklich sehr viel effizienter. Bubblesort ist aber, so weit ich weiss nicht rekursiv, oder? Denn das wäre eben auch eine Bedingung der Aufgabenstellung... Könntest du dir nicht eine Lösung des Problems durch diese Aufgabestellung vorstellen?

lg
drpingoo

 

[kle-ben]

Hi,

du kannst den bubblesort auch rekursiv schreiben das geht schon.
Ist wahrscheinich unter den Vorraussetzunge die sinnvollste Möglichkeit.

Vieleicht solltest du das erst mal in kleinen Schritten angehen.
Schreib eine Funktion die einen Parameter übergeben bekommt.
( Ich würde diesen len nennen da er die Länge des zu sortierenden arrays angibt )
Die fFnktion iteriert nun bis zu len -1 über das Array und schiebt den kleinsten
Wert bei bedarf eins weiter. ( Genau wie beim bubblesort )

Wenn du das hast und die Funktion mit der Gesamtlänge des Arrays aufrufst
sollte an der letzten Stelle des Arrays der kleinste Wert stehen. Stimmt das musst
du die Sortierfunktion nach einem Schleifendurchlauf einfach nochmal für len - 1 aufrufen. Aber Achtung du hast immer noch keine Abbruchbedingung. Die sollte zu begin der Funktion stehen.


Gruß ,
Benny

 

[SONY2]

Ich hab mich mal ein bisschen im Netz umgeguckt und ne Seite gefunden die dein Prblem lösen solte. Unter http://www.informatik.uni-leipzig.d...vaWS03.dir/Programme/Methoden/BubbleSort.java
findest du nen rekkursiven Bubblesort. Dort werden allerdings zwei Parameter verwendet, du kannst aber den ersten Parameter, also das Array weglassen, da das ja eine deiner Klassenattribute ist. Ansonsten müsstest du an dem Beispiel so gut wie nichts mehr ändern.

Gruß
sony2

 

[drpingoo]

ok, danke vielmals, sony. Ich sehs mir mal an.

lg