# n-kleinstes Element einer ArrayList



## Papuerus (20. Mai 2011)

Hallo zusammen,

in einer Hausaufgabe haben wir die Aufgabe das n-kleinste Element einer ArrayListe (unsortiert!!! Edit: Und wir dürfen vorher nicht Sortieren, Ziel ist es keinen n*log(n) Aufwand zu bekommen)

zu bestimmen...
und es soll rekursiv sein

es müsste irgendwie wie Quicksort funktionieren

Und man teilt die ArryList in 3 Teile, wozu man vorher einen Median (aus 5 oder 3?!) günstig bestimmen sollte, und dann halt immer größer , gleich oder kleiner

Aber ich habe keine Ahnung wie das konkret aussehen muss und wie man da genau vorgeht


----------



## Tomate_Salat (20. Mai 2011)

und die Frage ist jetzt?


----------



## Gast2 (20. Mai 2011)

Kannst den Array ja komplett sortieren und dann einfach die n-kleinste Zahl über [c] int gesuchteZahl = array[n-1][/c] bekommen.

Das Sortieren kannst du ja gerne rekursiv implementieren 

Quicksort


----------



## Papuerus (20. Mai 2011)

Wir dürfen vorher nicht sortieren, Ziel ist es eben keinen Aufwand von n*log(n) zu erreichen

Die Frage ist: Wie gehe ich vor?


----------



## faetzminator (20. Mai 2011)

Du implementierst einen Quick Sort.
Die einzigen Änderungen zu einem normalen Quick Sort:
- Wenn du die ArrayList danach noch im ursprünglichen Zustand benötigst, machst du eine Kopie davon
- Du gibst am Schluss das Item an n-ter Stelle zurück


----------



## SlaterB (20. Mai 2011)

'n-kleinstes Element' in Suchmaschine
->
http://www-ai.math.uni-wuppertal.de/SciComp/teaching/ss07/info2/Handouts/slides417-460.pdf

so, jetzt hast du die komplett Java-unabhängige Mathematik-Idee umsonst bekommen,
mal sehen ob du die Implementierung in Java als zweiten Schritt dann auch noch brauchst


----------



## Papuerus (20. Mai 2011)

@SlaterB
Die Seite habe ich auch gefunden und um die mathematische Idee ging es mir nicht, im ersten Beitrag habe ich ja kurz erläutert wie die Idee aussieht

mir geht es eher um die Umsetzung mit ArrayList

ich verstehe nicht wie das an einem Konkreten Beispiel aussieht, also die einzelnen Schritte

z.B.

[5,13,12,25,3,18,7,9,22] -> Sortiert(nur zur Hilfe) [3,5,7,9,12,13,18,22,25]
Median ist 13

Der erste Schritt müsste ja jetzt sein ein Pivot Element zu suchen, nach dem ich dann die Liste Teile
Sollte man hier jetzt schon z.B. 5,22,12,3,7 (median von 5 beliebigen oder müssen die aufeinander folgend sein?) nehmen und daraus z.B. einen Median brechne mit dem man die Liste dann wieder teilt?

so das ich 7 herrausbekomme

Und gehe ich jetzt linear die Elemente der Ursprünglichen Liste ab?
also
5<7 -> 5 kommt in meine kleiner gleich Liste (und hier die Frage brauche ich dann noch eine Liste bzw drei????)
13>7 kommt in > Liste (zusätzliche Liste?)

und gehe ich dann alle Elemente bis zu 22 durch

so das ich am Ende drei Listen habe

Liste(<7) = [3,5]
Liste(=7) = null
Liste(>7) = [9,12,13,18,22,25]

und wenn ich das habe, wie mache ich dann weiter?


----------



## SlaterB (20. Mai 2011)

die Liste(=7) ist nicht null, enthält die 7, evtl. mehrere, das ist schon wichtig,

wie es dann weiter geht steht auf Seite 419 oben im PDF, entweder ist 7 die gesuchte Zahl, 
oder das ganze nochmal mit der linken oder der rechten Teilliste, mit evtl. geänderten Suchindex

ist komplizierter als ich zuerst dachte, und dass mit der Rekursion kein n*log(n) herauskommt ist für mich gar nicht so leicht zu sehen,
vielleicht vereinfacht ausgedrückt weil nur eine der Teillisten rekursiv durchsucht werden muss, nicht beide..,

c* n + c*n *1/2 + c*n *1/4 + c*n *1/8 sind letzlich nur 2*c*n, 
im PDF ist das natürlich ewig kompliziert bewiesen

ich frage mich ob man als 'Median' nicht auch ein zufälliges Element wählen könnte, 
mag dann ab und zu relativ falsch am Rand liegen, dann eben ne Nullrunde, 
dafür spart man den kompletten Durchlauf zur Median-Suche..

unter Annahme von keinem Dauerpech wäre es interessant zu testen, ob das schneller geht


----------



## Papuerus (20. Mai 2011)

Eine kurze Zwischenfarge

Ich hab eine ArrayList mit Generischem Datentyp

ArrayList<T> list = .......

jetzt kann ich zwar ein Objekt vom typ T deklaprieren

T median; z.B.
Aber ich weiß nicht wie ich ihn instanziiere

T median = newT....?

Könnte mir da jemand weiter helfen?


----------



## SlaterB (20. Mai 2011)

das geht nicht, aber das brauchst du ja auch nicht, wofür willst du das haben?

T median;
oder
T median = null;
reicht, 
in die Variable kommt letzlich irgendwas aus der Liste rein, nichts neu ausgedachtes


----------



## Papuerus (20. Mai 2011)

Naja ich habe jetzt den ersten Median einfach mit "median of three" bestimmt, was mir erst mal reicht

und wollte den zuweisen, dein Tipp hat geholfen, vielen dank

ich arbeite jetzt an dem Rest, momentan noch ohne Rekursion

Edit:

index := Index( k, a, anfang, anfang + f< − 1 )

wie sieht das als java Algo aus?

Weil meinem Algo übergebe ich nur eine ArrayList und ein int n

also Index(ArrayList a, int n)

deswegen verstehe ich die Komma Setzung da nicht so ganz

Edit2:
und sie schreiben da ja auch nur von einem Datensatz und k


----------



## Papuerus (20. Mai 2011)

ich habe ein weiteres Problem

ich möchte jetzt gerne meinen Median mit dem k vergleichen

k habe ich aber nur als int übergeben bekommen

und meine median ist vom Typ T

Wie vergleiche ich die beiden jetzt über compaterTo?
da k ja kein Objekt ist...


----------



## SlaterB (20. Mai 2011)

was soll dir der Vergleich bringen? selbst wenn du eine Liste von Zahlen hast, z.B. 500, 600, 700, 800
und du suchst das k=2-kleinste Element, hilft es dir dann die 600 mit der 2 zu vergleichen?..

bisschen nachdenken bitte

edit:
beantwortet vielleicht auch deine bisher nicht gesehenen roten edits zuvor,
zwischen Indexen und Werten unterscheiden


----------



## Papuerus (20. Mai 2011)

Also was bedeutet dann dieses:

wenn k <= (f<)....

wenn k >= (f<)+(f=)

ist damit die Länge der Listen gemeint einfach?


----------



## SlaterB (20. Mai 2011)

ja


----------



## Papuerus (20. Mai 2011)

Danke^^

Ich denke ich bin fertig, aber wie teste ich das jetzt?


----------



## Gast2 (20. Mai 2011)

JUnit test cases schreiben oder eine main-Methode mit ein paar Beispielaufrufen/Arrays.

z.B.:


```
public static void main(String[] args) {

		int[] array = new int[]{3,9,12,2,76,1,6,8};
		int thirdSmallestElement = deineMethodeUmEsZuBerechnen(array);
		if(thirdSmallestElement == 3){
			System.out.println("alles okay :)");
		} else {
			System.out.println("haste wohl nen Fehler drin ;)");
		}
	}
```
Poste doch mal deine Lösung.


----------



## Papuerus (20. Mai 2011)

Mein Code sieht nun so aus

[Java]

	private static <T extends Comparable<T>> T findNthSmallest(ArrayList<T> list,
	    int n) {
		T nsmallest = null;

		//1 Wähle Median mit "median of three"

		T a = list.get(0);
		T b = list.get(list.size()-1);
		T c = list.get(list.size()/2);
		T workmedian = null;
		if ( (a.compareTo(b)== 1) & (a.compareTo(c) == -1) || ( a.compareTo(b)==-1 & a.compareTo(c)==1 ) )
			workmedian = a;
		if ( (b.compareTo(a)== 1) & (b.compareTo(c) == -1) || ( b.compareTo(a)==-1 & b.compareTo(c)==1 ) )
			workmedian = b;
		if ( (c.compareTo(a)== 1) & (c.compareTo(b) == -1) || ( c.compareTo(a)==-1 & c.compareTo(b)==1 ) )
			workmedian = c;

		ArrayList<T> smallerworkmedian = new ArrayList<T>();
		ArrayList<T> equalworkmedian = new ArrayList<T>();
		ArrayList<T> biggerworkmedian = new ArrayList<T>();

		for (int i = 0; i<list.size()-1 ; i++){
			if ((list.get(i).compareTo(workmedian))== -1)
				smallerworkmedian.add(list.get(i));
			if ((list.get(i).compareTo(workmedian))== 1)
				biggerworkmedian.add(list.get(i));
			if ((list.get(i).compareTo(workmedian))== 0)
				equalworkmedian.add(list.get(i));			
		}

		if (smallerworkmedian.size() >= n){
			nsmallest = findNthSmallest(smallerworkmedian,n);
		}
		else
		{
			if (n <= smallerworkmedian.size()+biggerworkmedian.size() )
				nsmallest = equalworkmedian.get(0);
			else
			{
				nsmallest = findNthSmallest(biggerworkmedian, n);
			}
		}

		return nsmallest;
	}

[/Java]

JUnit war klar, aber ich weiß nicht wie man mit Generic die Tests schreibt


----------



## SlaterB (20. Mai 2011)

ruhig auch Zufallsarrays mit 10.000 Zahlen erstellen,
konventiell sortieren, per Schleife alle Elemente von k= 0 bis 9999 anschauen und jeweils im unsortierten (!) Array das k-kleinste Element suchen und vergleichen 

edit:
wehe wenn a, b, c nicht drei verschiedene Elemente sind..


----------



## Papuerus (20. Mai 2011)

Ja stimmt, ich bau mal noch ein if rein

aber für Listen mit < 3 Elementen ist es ja eh Trivial, aber ja das muss ich ja im Grunde berücksichtigen


----------



## Gast2 (20. Mai 2011)

Guck mal hier:


```
int nThelement = 4;
		ArrayList<Integer> list = fillArrayByRandom(10,10000);
		System.out.println("Unsorted: "+Arrays.toString(list.toArray()));
		Integer i = findNthSmallest(list,nThelement);
		System.out.println("Berechnetes "+ nThelement+"tes Element: "+i);
		Collections.sort(list);
		System.out.println("Sorted: "+Arrays.toString(list.toArray()));
		Integer j = list.get(nThelement-1);
		System.out.println(nThelement+"tes Element: "+j);
		assert(i==j);

//...
	private static ArrayList<Integer> fillArrayByRandom(int size, int limit){
			 Random rnd = new Random();
	         Set<Integer> set = new HashSet<Integer>();
	         while(set.size()<size){
	        	 set.add(rnd.nextInt(limit));
	         }
	         return new ArrayList<Integer>(set);
		
	}
```

Ist noch ein bisschen was dran zu tun (z.B. das zufällige Befüllen ist gefährlich schlecht implementiert), aber die grobe Richtung solltest du schon einschlagen zum Testen.


Nebenbei solltest du die Signatur ändern und statt

```
private static <T extends Comparable<T>> T findNthSmallest(ArrayList<T> list, int n) {
```
lieber 

```
private static <T extends Comparable<T>> T findNthSmallest(List<T> list, int n) {
```
nutzen


----------



## Andi_CH (20. Mai 2011)

Super mir hauts als erstes gleich eine NPE um die Ohren - da gibts aber noch einiges zu tun ;-)


----------



## Gast2 (20. Mai 2011)

Ach, einfach zwei, drei, viermal ausführen, dann klappt es schon 

Btw:

```
Unsorted: [5738, 5395, 7323, 9673, 4338, 6474, 7714, 2805]
Berechnetes 4tes Element: 4338
Sorted: [2805, 4338, 5395, 5738, 6474, 7323, 7714, 9673]
4tes Element: 5738
4338 != 5738
```

Die Berechnung scheint auch insgesamt noch Fehler zu haben


----------



## SlaterB (20. Mai 2011)

Papuerus hat gesagt.:


> Ja stimmt, ich bau mal noch ein if rein
> 
> aber für Listen mit < 3 Elementen ist es ja eh Trivial, aber ja das muss ich ja im Grunde berücksichtigen


ich meinte nicht zu wenig Elemente sondern gleiche Elemente,
nimm als Beispiel für die Tests  [3, 5, 6, 3] auf


----------



## Papuerus (20. Mai 2011)

Habe ihn noch mal angepasst

[Java]
private static <T extends Comparable<T>> T findNthSmallest(ArrayList<T> list,
	    int n) {
		T nsmallest = null;
		T workmedian = null;
		T a = null;
		T b = null;
		T c = null;

		if (list == null)
			return null;
		if (list.size() == 1)
			return list.get(0);
		if ( ( list.size() < 3 ) & ( list.get(0).equals(list.get(1)) == false ) )
			return null;
		if (list.size() > 1 && list.get(0).equals(list.get(1)) == true )
			return list.get(0);

		//Wahl des Median mit "median of three"
		a = list.get(0);
		b = list.get(list.size()-1);
		c = list.get(list.size()/2);
		if ( (a.compareTo(b)== 1) & (a.compareTo(c) == -1) || ( a.compareTo(b)==-1 & a.compareTo(c)==1 ) )
			workmedian = a;
		if ( (b.compareTo(a)== 1) & (b.compareTo(c) == -1) || ( b.compareTo(a)==-1 & b.compareTo(c)==1 ) )
			workmedian = b;
		if ( (c.compareTo(a)== 1) & (c.compareTo(b) == -1) || ( c.compareTo(a)==-1 & c.compareTo(b)==1 ) )
			workmedian = c;

		//teile in 3 Listen <,>,=
		ArrayList<T> smallerworkmedian = new ArrayList<T>();
		ArrayList<T> equalworkmedian = new ArrayList<T>();
		ArrayList<T> biggerworkmedian = new ArrayList<T>();
		for (int i = 0; i<list.size()-1 ; i++)
		{
			if ((list.get(i).compareTo(workmedian))== -1)
				smallerworkmedian.add(list.get(i));
			if ((list.get(i).compareTo(workmedian))== 1)
				biggerworkmedian.add(list.get(i));
			if ((list.get(i).compareTo(workmedian))== 0)
				equalworkmedian.add(list.get(i));			
		}

		//Vergleiche n mit länge der Teillisten <,>,=
		//entwerder return oder führe Rekursion aus
		if (smallerworkmedian.size() >= n)
			nsmallest = findNthSmallest(smallerworkmedian,n);
			else
			{
				if (n <= smallerworkmedian.size()+biggerworkmedian.size() )
					nsmallest = equalworkmedian.get(0);
				else
				{
					nsmallest = findNthSmallest(biggerworkmedian, n);
				}
			}

	return nsmallest;
	}
[/Java]

Edit: habs gesehen


----------



## Papuerus (20. Mai 2011)

Wir dürfen die Methode nicht ändern und müssen ArrayList nutzen


----------



## Andi_CH (20. Mai 2011)

Jetzt schreibt es 
	
	
	
	





```
null
```
 auf die Konsole

EDIT: äh ich muss hinzufügen - schreibe tu ich es - aber es gibt "null" zurück


----------



## Gast2 (20. Mai 2011)

Papuerus hat gesagt.:


> Wir dürfen die Methode nicht ändern und müssen ArrayList nutzen



Pfui! Direkt den Prof/Tutor vor die Tür setzen


----------



## Papuerus (20. Mai 2011)

Also ich habe dann das eine If einfach mal wieder ausgeklammert, obwohl ich dachte der Fall müsste stimmen mh

danke für das Feedback


----------



## Andi_CH (20. Mai 2011)

Mein erster Test ist immer mit dem Debugger und einem primitven Hauptpgrogramm -
Mein Liste die zum "null" führt ist 1,2,3,4,5
Tja ....


----------



## Gast2 (20. Mai 2011)

Nebenbei kommen da weiterhin Falsche ergebnisse bei rum:

```
Unsorted: [9273, 2151, 3281, 1817, 9607, 2145, 1542, 3696]
Berechnetes 4tes Element: 3281
Sorted: [1542, 1817, 2145, 2151, 3281, 3696, 9273, 9607]
4tes Element: 2151
3281 != 2151 => Fehler!
```

Mit folgender Testmethode:


```
public static void main(String[] args) {

		int nThelement = 4;
		ArrayList<Integer> list = fillArrayByRandom(8, 10000);
		System.out.println("Unsorted: " + Arrays.toString(list.toArray()));
		
		Integer i = findNthSmallest(list, nThelement);
		
		
		System.out.println("Berechnetes " + nThelement + "tes Element: " + i);
		Collections.sort(list);
		System.out.println("Sorted: " + Arrays.toString(list.toArray()));
		Integer j = list.get(nThelement - 1);
		System.out.println(nThelement + "tes Element: " + j);
		System.out.println(i == j ? i + " == " + j + " => Alles okay!" : i + " != "
				+ j + " => Fehler!");

	}
```

EDIT://

Oh ein Treffer:

```
Unsorted: [1295, 2299, 1522, 8080, 2572, 8155, 7717, 6682]
Berechnetes 4tes Element: 2572
Sorted: [1295, 1522, 2299, 2572, 6682, 7717, 8080, 8155]
4tes Element: 2572
2572 == 2572 => Alles okay!
```

Aber nur einer von 10 Testläufen... also etwas unzuverlässig.


----------



## Papuerus (20. Mai 2011)

was ist fillArrayByRandom
und collection?

Edit:
ich weiß auch nicht woran es liegt


----------



## Gast2 (20. Mai 2011)

Siehe ein paar Postings weiter vorne (http://www.java-forum.org/hausaufgaben/118489-n-kleinstes-element-arraylist-2.html#post763893). Collections ist ein Utility Klasse mit der du z.B. eine Liste sortieren kannst. In diesem Fall um das Ergebniss zu vergleichen.


----------



## Papuerus (20. Mai 2011)

Ich glaube die Oders bei der Medianwahl sind falsch, das muss nur | sein, denke ich
Edit: Oder auch nicht... ist ja im Grunde egal bei oder, oder?


----------



## SlaterB (20. Mai 2011)

SlaterB hat gesagt.:


> die Liste(=7) ist nicht null, enthält die 7, evtl. mehrere, das ist schon wichtig,
> 
> wie es dann weiter geht steht auf Seite 419 oben im PDF, entweder ist 7 die gesuchte Zahl,
> oder das ganze nochmal mit der linken oder der rechten Teilliste, *mit evtl. geänderten Suchindex*


hast du nicht richtig umgesetzt,
wenn in der größeren Liste gesucht wird dann doch nicht mehr das k-te bzw. n-te Element,
weil ja schon einige gestrichen wurden (die kleine + die mittlere Liste),
schau auch noch mal im PDF nach


----------



## Gast2 (20. Mai 2011)

Bau dir einfache ein kleine Mainmethode, führe deine Methode aus und fang an sie zu debuggen.

Kannst ja auch erstnal mit einer festen Liste anfangen, z.B.:

```
public static void main(String[] args) {

		int nThelement = 4;
		ArrayList<Integer> list = //fillArrayByRandom(8, 10000);
			new ArrayList<Integer>(){{
				add(1);
				add(2);
				add(3);
				add(4);
				add(5);
				add(6);
				add(7);
				add(8);
			}};
		System.out.println("Unsorted: " + Arrays.toString(list.toArray()));
		
		Integer i = findNthSmallest(list, nThelement);
		System.out.println("Berechnetes " + nThelement + "tes Element: " + i);
		Collections.sort(list);
		System.out.println("Sorted: " + Arrays.toString(list.toArray()));
		Integer j = list.get(nThelement - 1);
		System.out.println(nThelement + "tes Element: " + j);
		System.out.println(i == j ? i + " == " + j + " => Alles okay!" : i + " != "
				+ j + " => Fehler!");

	}
```

oder 

```
ArrayList<Integer> list = //fillArrayByRandom(8, 10000);
			new ArrayList<Integer>(){{
				add(8);
				add(6);
				add(3);
				add(5);
				add(4);
				add(7);
				add(2);
				add(1);
			}};
```

Dann weitermachen mit Zufallszahlen

Hier kommt z.B. schon ein Fehler bei raus:

```
ArrayList<Integer> list = //fillArrayByRandom(8, 10000);
			new ArrayList<Integer>(){{
				add(8);
				add(6);
				add(3);
				add(5);
				add(40);
				add(70);
				add(2);
				add(1);
			}};
```


----------



## Papuerus (20. Mai 2011)

Und wie wird Collection und Arrays bzw. was muss ich dafür importieren, weil Eclipse bei mir da Fehler anzeigt


----------



## Gast2 (20. Mai 2011)

Strg+Shift+O oder aber 

```
import java.util.Arrays;
import java.util.Collections;
```


----------



## Papuerus (20. Mai 2011)

fassy hat gesagt.:


> [...]
> 
> ```
> [...]
> ...


----------



## Gast2 (20. Mai 2011)

Nur kompilieren zählt nicht... und was heißt "bekomm ich bereits einen Fehler"? Schon beim kompilieren? Das kann nicht sein, da hast du dich irgenwo vertippt.


----------



## Papuerus (20. Mai 2011)

Ich hab meinen COde unterdessen angepasst:

[Java]	private static <T extends Comparable<T>> T findNthSmallest(ArrayList<T> list,
	    int n) {
		T nsmallest = null;
		T workmedian = null;
		T a = null;
		T b = null;
		T c = null;

		if (list == null)
			return null;
		if (list.size() == 1)
			return list.get(0);
		if ( ( list.size() < 3 ) & ( list.get(0).equals(list.get(1)) == false ) )
			return null;
		if (list.size() > 1 && list.get(0).equals(list.get(1)) == true )
			return list.get(0);

		//Wahl des Median mit "median of three"
		a = list.get(0);
		b = list.get(list.size()-1);
		c = list.get(list.size()/2);
		if ( (a.compareTo(b)== 1) & (a.compareTo(c) == -1) | ( a.compareTo(b)==-1 & a.compareTo(c)==1 ) )
			workmedian = a;
		if ( (b.compareTo(a)== 1) & (b.compareTo(c) == -1) | ( b.compareTo(a)==-1 & b.compareTo(c)==1 ) )
			workmedian = b;
		if ( (c.compareTo(a)== 1) & (c.compareTo(b) == -1) | ( c.compareTo(a)==-1 & c.compareTo(b)==1 ) )
			workmedian = c;

		//teile in 3 Listen <,>,=
		ArrayList<T> smallerworkmedian = new ArrayList<T>();
		ArrayList<T> equalworkmedian = new ArrayList<T>();
		ArrayList<T> biggerworkmedian = new ArrayList<T>();
		for (int i = 0; i<list.size()-1 ; i++)
		{
			if ((list.get(i).compareTo(workmedian))== -1)
				smallerworkmedian.add(list.get(i));
			if ((list.get(i).compareTo(workmedian))== 1)
				biggerworkmedian.add(list.get(i));
			if ((list.get(i).compareTo(workmedian))== 0)
				equalworkmedian.add(list.get(i));			
		}

		//Vergleiche n mit länge der Teillisten <,>,=
		//entwerder return oder führe Rekursion aus
		if (smallerworkmedian.size() >= n)
			nsmallest = findNthSmallest(smallerworkmedian,n);
			else
			{
				if (n <= smallerworkmedian.size()+biggerworkmedian.size() )
					nsmallest = equalworkmedian.get(0); 
				else
				{
					nsmallest = findNthSmallest(biggerworkmedian, n - smallerworkmedian.size() - equalworkmedian.size()); //hier geändert
				}
			}

	return nsmallest;
	}[/code]

vllt. deswegen

Edit:
das spuck die Console aus

```
Unsorted: [1, 2, 3, 4, 5, 6, 7, 8]
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
	at java.util.ArrayList.RangeCheck(Unknown Source)
	at java.util.ArrayList.get(Unknown Source)
	at Median.findNthSmallest(Median.java:50)
	at Median.findNthSmallest(Median.java:84)
	at Median.findNthSmallest(Median.java:77)
	at Median.main(Median.java:119)
```


----------



## Gast2 (20. Mai 2011)

Füg das mal hinzu:


```
private static int durchlauf = 1;

	private static <T extends Comparable<T>> T findNthSmallest(
			final ArrayList<T> list, int n) {
		System.out.println("Rekursionsdurchlauf: "+durchlauf++);
		System.out.println("Liste: " + Arrays.toString(list.toArray()));
		
		T nsmallest = null;
		T workmedian = null;
		T a = null;
		T b = null;
		T c = null;
		[...]
```

Du darfst nicht vergessen das du die Liste die übergeben wird veränderst...


----------



## Papuerus (20. Mai 2011)

So schaut es dann aus

```
Unsorted: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Rekursionsdurchläufe: 1
Liste: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Rekursionsdurchläufe: 2
Liste: [1, 2, 3, 4]
Rekursionsdurchläufe: 3
Liste: []
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
	at java.util.ArrayList.RangeCheck(Unknown Source)
	at java.util.ArrayList.get(Unknown Source)
	at Median.findNthSmallest(Median.java:52)
	at Median.findNthSmallest(Median.java:86)
	at Median.findNthSmallest(Median.java:79)
	at Median.main(Median.java:122)
```

Aber wieso gibt es bei dir keinen Fehler?^^


----------



## Gast2 (20. Mai 2011)

Es gibt ja Fehler... du hast da noch Programmierfehler drin


----------



## Papuerus (20. Mai 2011)

Mit der Verbesserung sollte es jetzt eigentlich laufen, aber ich sehe jetzt auch nichts mehr

ich glaube ich brauch eine Pause^^


----------



## Papuerus (20. Mai 2011)

fassy hat gesagt.:


> [...]
> 
> 
> ```
> ...



Wo bekomme ich das fillArrayByRandom her?


----------



## Gast2 (21. Mai 2011)

Aus meinem Beitrag in http://www.java-forum.org/hausaufgaben/118489-n-kleinstes-element-arraylist-2.html#post763893

Aber ich habs dir nochmal rauskopiert:

```
private static ArrayList<Integer> fillArrayByRandom(int size, int limit){
             Random rnd = new Random();
             Set<Integer> set = new HashSet<Integer>();
             while(set.size()<size){
                 set.add(rnd.nextInt(limit));
             }
             return new ArrayList<Integer>(set);
        
    }
```


----------



## Papuerus (21. Mai 2011)

Ah Sorry, danke, ich war etwas blind >.<
Ich teste dann mal, ich denke ich habe es jetzt...


----------



## Papuerus (22. Mai 2011)

Was muss ich dafür noch importieren?

```
Set<Integer> set = new HashSet<Integer>();
```

Eclipse zeigt es mir noch als Fehler an


----------



## Papuerus (22. Mai 2011)

Ok hat sich erledigt hab Set und HashSet einfach importiert

hier mein endgültiger Code


```
private static <T extends Comparable<T>> T findNthSmallest(final ArrayList<T> list, int n) {
		T nsmallest = null;
		T workmedian = null;
		T a = null;
		T b = null;
		T c = null;

		if (list.size() < n)
			return null;
		if (list.size() == 1)
			return list.get(0);

		//Wahl des Median mit "median of three"
		a = list.get(0);
		b = list.get(list.size()-1);
		c = list.get(list.size()/2);
		if (list.size() == 2)
			workmedian = list.get(1);
		if ( (a.compareTo(b)== 1) & (a.compareTo(c) == -1) | ( a.compareTo(b)==-1 & a.compareTo(c)==1 ) )
			workmedian = a;
		if ( (b.compareTo(a)== 1) & (b.compareTo(c) == -1) | ( b.compareTo(a)==-1 & b.compareTo(c)==1 ) )
			workmedian = b;
		if ( (c.compareTo(a)== 1) & (c.compareTo(b) == -1) | ( c.compareTo(a)==-1 & c.compareTo(b)==1 ) )
			workmedian = c;
		
		//teile in 3 Listen <,>,=
		ArrayList<T> smallerworkmedian = new ArrayList<T>();
		ArrayList<T> equalworkmedian = new ArrayList<T>();
		ArrayList<T> biggerworkmedian = new ArrayList<T>();
		for (int i = 0; i < list.size() ; i++)
		{
			if ((list.get(i).compareTo(workmedian))== -1)
				smallerworkmedian.add(list.get(i));
			if ((list.get(i).compareTo(workmedian))== 1)
				biggerworkmedian.add(list.get(i));
			if ((list.get(i).compareTo(workmedian))== 0)
				equalworkmedian.add(list.get(i));			
		}

		//Vergleiche n mit länge der Teillisten <,>,=
		//entwerder return oder führe Rekursion aus
		if (n <= smallerworkmedian.size())
			nsmallest = findNthSmallest(smallerworkmedian,n);
			else
			{
				if (n <= smallerworkmedian.size()+equalworkmedian.size() )
					nsmallest = equalworkmedian.get(0);
				else
				{
					nsmallest = findNthSmallest(biggerworkmedian, n - smallerworkmedian.size() - equalworkmedian.size());  ///**- smallerworkmedian.size() - equalworkmedian.size()*/
				}
			}

	return nsmallest;
	}
```

Alle meine Tests waren immer in Ordnung
mag vllt. noch mal jemand testen?

bzw. wie modifiziere ich den Test so, dass ich mit einer Schleife testen kann

mit for (int i = 0; i< 100; i++)......
oder so?


----------



## Gast2 (22. Mai 2011)

Ja, zum Beispiel so:


```
public static void main(String[] args) {
		Random rnd = new Random();
		for (int test = 1; test < 100; test++) {
			int nThelement = rnd.nextInt(99);
			ArrayList<Integer> list = fillArrayByRandom(100, 10000);
			System.out.println("Unsorted: " + Arrays.toString(list.toArray()));
			Integer i = findNthSmallest(list, nThelement);
			System.out.println("Berechnetes " + nThelement + "tes Element: "
					+ i);
			Collections.sort(list);
			System.out.println("Sorted: " + Arrays.toString(list.toArray()));
			Integer j = list.get(nThelement - 1);
			System.out.println(nThelement + "tes Element: " + j);
			if (i != j) {
				throw new RuntimeException();
			}
		}
		System.out.println("______________________");
		System.out.println("Alle tests erfolgreich");
	}
```


----------



## Papuerus (22. Mai 2011)

```
int nThelement = rnd.nextInt(99);
```
 hier noch + 1 und es haut alles hin^^
weil es ja nicht 0 sein darf

danke für die schnelle Hilfe
nach 1000000 erfolgreichen Tests bin ich ganz zuversichtlich


----------



## Gast2 (23. Mai 2011)

Papuerus hat gesagt.:


> ```
> int nThelement = rnd.nextInt(99);
> ```
> hier noch + 1 und es haut alles hin^^
> weil es ja nicht 0 sein darf



Stimmt natürlich. 



Papuerus hat gesagt.:


> nach 1000000 erfolgreichen Tests bin ich ganz zuversichtlich



Na, das sieht doch gut aus. Herzlichen Glückwunsch - auf zur nächsten Aufgabe. Denke mal du hast jetzt schon viel gelernt.


----------



## SlaterB (23. Mai 2011)

teste noch mit [3, 3, 3, 3, 3]
wenn alle gleich sind, funktioniert die Median-Bestimmung meiner Ansicht nach nicht


----------



## Gast2 (23. Mai 2011)

Ist die Frage ob [3,3,3,3] als Eingabe überhaupt erlaubt ist. Ich würde die Aufgabe auffassen als "Alle Zahlen im Array müssen unterschiedlich sein". Aber hast recht, dann sollte man zumindest mit einem Fehlerhandling darauf reagieren.


----------

