Insertion Sort Algorithmus problem

[hedges]

ich bekomme in zeile 22 ein ArrayIndexOutOfBoundsException: 4

versteh aber nicht warum.
kann mir das einer erklären?

public class prog1uebung41 {

	public static void main(String[] args) 
	{
		prog1uebung41.aufgabe2();
	}
	
	public static void aufgabe2()
	{
		int[] raniarray = {5,1,2,4};
		int puffer;
		
		for (int o = 0; o < raniarray.length; o++)
		{
			System.out.println(o+". Element "+raniarray[o]);
		}
		
		for (int i = 1; i < raniarray.length; i++)
		{
			for ( int z = 0; z < i ; z++ )
			{
				if ( raniarray[i] <= raniarray[z] )			
				{
					puffer = raniarray[i];
					int j=i;
					do 
					{
						if ( j == 0 ){break;}
						raniarray[j] = raniarray[j-1];	
						j--;
						
					}while(raniarray[z]==raniarray[j+1]);
					
				raniarray[z] = puffer;
				z=i;
				}
			}
		}
		System.out.println("Das neu sortierte Array");
		for (int o = 0; o < raniarray.length; o++)
		{
			System.out.println(o+". Element "+raniarray[o]);
		}
	}
}

 

[SlaterB]

> for (int i = 1; i <= raniarray.length; i++)
> {

i kann 4 sein, das Array ist aber nur 4 lang, damit sind nur Indexe 0, 1, 2 und 3 erlaubt

vergleiche das mit der vorherigen Schleife:
> for (int o = 0; o < raniarray.length; o++)
> {

o wird nicht 4

 

[xysawq]

bitte haken setzen, das wars, ist die richtige lösung ^^

 

[hedges]

ein problem hab ich noch, er sortiert das array richtig bis 1 2 5 4 dann tauscht er die 4 mit der 5, allerdings überschreibt er das zweite array element mit dem inhalt des ersten elements.
ich kapier aber nicht warum, da ja z = 2 sein muss ( für die 5) und fertig. warum wechselt er nochmal array[0] auf array[1]?

 

[SlaterB]

ich sehe, warum das Programm das macht auf Code-Ebene,
verstehe aber absolut nicht, was die while-j-Schleife da machen soll,
und kann daher nicht sagen, was daran richtig oder falsch ist,

ich finde, dass diese Schleife nur zwischen z und i laufen sollte,
durch das j bzw. durch das while(raniarray[z]==raniarray[j+1]); gehts aber viel weiter nach links

da muss eine Bedingung wie
while (j > z)
rein oder ähnliches, wieso ein Vergleich der Array-Elemente?

 

[hedges]

vergleich der array elemente muss ja sein um rauszufinden ob array kleiner array[z] ist, und wenn ja sollen ja alle elemente eins nach rechts gerückt werden, und array an der stelle array[z] eingefügt werden.

 

[SlaterB]

alles klar, mit einer Antwort 'ist doch richtig so' sind meine Zweifel ausgeräumt
:bahnhof:


du musst schon Schritt für Schritt erklären was da passiert

-------

> vergleich der array elemente muss ja sein um rauszufinden ob array kleiner array[z] ist

das ist sowieso der Fall, bis
> if ( raniarray <= raniarray[z] )
ist alles korrekt,
was die do-while-Schleife darin dann macht ist aber fraglich

> und wenn ja sollen ja alle elemente eins nach rechts gerückt werden, und array an der stelle array[z] eingefügt werden.

dass das nicht passiert sagt dir ja das Programm selber, in meiner Anwort stehts auch,
was bringt es, diese Aussage zu wiederholen?

es ist immer noch fraglich, was dein Programm an dieser Stelle tut,
ich glaube ja gerne, dass du das richtige vorhast,
interessant sind nun aber die einzelnen Schritte, die du dafür einsetzt

 

[xysawq]

Ich glaube mit der while-Schleife versucht er solange zu schieben, bis das Ende erreicht ist, auch wenn es mehr als sinnlos ist.

Eine einfache for-Schleife hätte gereicht, da man ja die Position und die Länge kennt.

Aber diese Aufgabe ist so einfach, da bringt es mehr den Herren nach diesem Tipp selber auf den Code kommen zu lassen (der nun wirklich nicht schwer ist).

Bubble-Sort war das doch im Übrigen, oder?

 

[hedges]

Beispiel array = {5,1,2,4}

die while schleife verschiebt array[0] ( 5 ) ein feld nach rechts.

raniarray[j] = raniarray[j-1];

ergo is das neue array = {5,5,2,4}
da ich aber vorher das grad überschriebene element gespeichert hab:

puffer = raniarray[i];

füg ich dieses wieder ein mit

raniarray[z] = puffer;

und das array ist nun: array = {1,5,2,4}

das ist genau das was auch passieren soll, allerdings wird beim letzen durchlauf array[1] mit array[0] überschrieben und ich weiß nicht warum.

array vorletzter durchlauf : array = {1,2,5,4}
array nach dem letzten durchlauf : array = {1,1,4,5}

also hat er erkannt das 4 kleiner 5 ist, hat die 5 auf die position von der 4 verschoben, die 5 auf die position der 4 gespeichert, ABER leider auch element [1] mit inhalt vom element [0] überschrieben, und da weiß ich nich weiter warum dsa passiert.

hoffe das mein problem jetzt klarer geworden ist

 

[hedges]

@ xysawq

es soll später mit einem zufällig generierten array sortiert werden, ergo ist die anzahl nicht klar.

es ist der insertion sort algorithmus...

 

[xysawq]

...ähm... array.length ist doch eine bekannte länge oder?

und ja, es ist insertion... bubble war ja das tauschen mit dem nachbarn...

dann hast du z und i als position, was will man mehr?

 

[SlaterB]

das Problem ist von Anfang an völlig klar, ich verstehe vollkommen, wie so ein Programm arbeiten sollte und verstehe vollkommen, dass da was falsch passiert und auch wo,

ich könnte nun ein korrektes Programm posten, aber das ist nicht in meinem Sinne,
ich versuche daher seit mehreren Post dich zu fragen, was du da programmiert hast,

eine Antwort 'ein korrektes Programm' hilft da nicht weiter,
sondern etwas in Art von
'die Schleife j fängt bei i an und geht dann immer weiter nach links und schreibt jedes Element ein Feld weiter rechts,
die Schleife geht immer weiter nach links bis ... [hier verstehe ich nämlich deinen Code absolut nicht]'

damit will ich erreichen, dass du über deinen Code nachdenkst, ihn mal in Worten beschreibst und wir die Denkfelher aufdecken können, die zu diesem falschen Code führen,

also: was passiert dort in Zeile 26 bis 32, insbesondere was soll die Bedingung 32?
du musst dir doch irgendwas dabei gedacht haben,
und antworte bitte nicht nochmal 'das ist Code der zur korrekten Sortierung führt', sondern WAS GENAU DIESER CODE MACHT?!

 

[xysawq]

jetzt bin ich mal gespannt, das hat der schlaue SlaterB wieder mal klar und deutlich augedrückt, so wie es sein soll

 

[hedges]

   do{

anfang do schleife

 if ( j == 0 ){break;}

wenn j null sein sollte muss die while schleife unterbrochen werden da in der nächsten zeile j-- dann ein array[-1] geben würde, und das nich geht, daher diese zeile

raniarray[j] = raniarray[j-1];

hier wird dem element welches einsortiert werden soll ein neues wert zugewiesen, und zwar der wert des elements links danaben

j--;

hier wird j dekrementiert, damit alle elemente links von dem neu einzuordnenden element jeweils um eins nach rechts verschoben wird.

}while(raniarray[z]==raniarray[j+1]);

abbruch der while schleife wenn
z ( die position wohin das neu einzuordnende element hin soll )
gleich ist wie das einzuordnende element.

 

[SlaterB]

nun gut, da kommen wir wohl nicht weiter, ich verstehe es jedenfalls immer noch nicht

du hast
1, 2, 5, 4

als erstes wird daraus
1, 2, 5, 5
j ist dann 2, array[z=2] == 5 == 5 == array[j+1=3], ok

ich meine, dass an dieser Stelle abgebrochen werden müsste (*),
du schreibst aber, dass es an dieser Stelle weiter geht,
warum willst du nicht näher erläutern, ich kann es nicht hellsehen,

das Unglück nimmt seinen Lauf, nächster Durchgang:
1, 2, 2, 5
j=1
die while-Bedingung ist immer noch erfüllt,
array[z=2] == 2 == 2 == array[j+1=2],
j+1 ist gar direkt z,
while sagt ok, warum verstehe ich nicht, kann dir dabei nicht helfen

als nächstes
1, 1, 2, 5
j=0
hier nun endlich Abbruch der Schleife
array[z=2] == 2 != 1 == array[j+1=1],



danach wird dann Array[z] auf 4 gesetzt

-----------

als Lösungshinweis noch: ich würde die Schleife an Punkt (*) weiter oben abbrechen, wie schon gesagt,
am besten mit einer ganz einfachen Bedingung wie while(j>z) oder so, evtl +-1,

die Bedingung
if ( j == 0 ){break;}
könnte dann übrigens wegfallen, j muss nicht kleiner als z werden

 

[xysawq]

	int kleinsteZahl;
	int position;
	
	for(int i=0; i<(array.length-1); i++)
	{
		kleinsteZahl = array[i];
		position = i;
		for(int j=1; j<array.length; j++)
		{
			if(array[j] < kleinsteZahl)
			{
				kleinsteZahl = array[j];
				position = j;
			}
		}
		
		if(i != position)
		{
			for(int k=position; k>i; k--)
			{
				array[k] = array[k-1];
			}
			array[i] = kleinsteZahl;
		}
	}

mir reichts, nimm jetzt endlich FOR-Schleifen, das ist doch alles sinnlos da oben...

 

[hedges]

hab das mal getestet mit deinem code, leider wird das array nich richtig sortiert.

public static void test1()
	{
		
		   int[] array = {5,1,2,4};
		   int kleinsteZahl;
		   int position;
		   
		   for(int i=0; i<(array.length-1); i++)
		   {
		      kleinsteZahl = array[i];
		      position = i;
		      for(int j=1; j<array.length; j++)
		      {
		         if(array[j] < kleinsteZahl)
		         {
		            kleinsteZahl = array[j];
		            position = j;
		         }
		      }
		      
		      if(i != position)
		      {
		         for(int k=position; k>i; k--)
		         {
		            array[k] = array[k-1];
		         }
		         array[i] = kleinsteZahl;
		      }
		   }
			for (int o = 0; o < array.length; o++)
			{
				System.out.println(o+". Element "+array[o]);
			}
	}

bekomm ich folgende ausgabe:

0. Element 1
1. Element 2
2. Element 2
3. Element 4

es sollte aber eigentlich

0. Element 1
1. Element 2
2. Element 4
3. Element 5

sein.

 

[SlaterB]

> for(int j=1;

->

for(int j=i+1;

 

[hedges]

so hab jetzt meine version doch noch fertigstellen können.
ich wollte lieber eine eigene version schreiben, da ick sonst ja nix dabei lerne. auch wenn mich das jetzt insgesamt 6 stunden gekostet hat....naja aus fehlern lernt man.

ich habe einfach etliche ausgaben machen lassen und bin bei einem beispiel array alles komplett durchgegangen.
hier die lösung, es lag an einem falschen abbruch der while schleife.

	public static void aufgabe2()
	{
		int[] raniarray;
		raniarray = new int[99];
		int puffer;

		System.out.println("Zufalls - Array generieren:");
		
		for (int i = 0; i < raniarray.length; i++)
			{
				int zufallszahl = new Random().nextInt( 1000 );
				raniarray[i] = zufallszahl;

				if (i%10 == 0)
				{
					System.out.println("\n");
				}
				System.out.print(raniarray[i]+" ");
			}

		for (int i = 1; i < raniarray.length; i++)
		{
			for ( int z = 0; z < i ; z++ )
			{
				if ( raniarray[i] <= raniarray[z] )			
				{
					puffer = raniarray[i];
					int j=i;
					do 
					{
						if ( j == z ){;break;}
						raniarray[j] = raniarray[j-1];	
						j--;
					}while(z<j);
					
				raniarray[z] = puffer;
				z=i;
				}
			}
		}
		System.out.println("\n\nDas neu sortierte Array:");
		for (int o = 0; o < raniarray.length; o++)
		{
			if (o%10 == 0)
			{
				System.out.println("\n");
			}
			System.out.print(raniarray[o]+" ");
		}
	}
}

ich danke euch für die hilfe. und sry das ick vielleich bissl gestresst hab...cya danny