Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
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
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
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
@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?)
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
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
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));
}
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..
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
Java:
private static <T extends Comparable<T>> T findNthSmallest(ArrayList<T> list, int n) {
lieber
Java:
private static <T extends Comparable<T>> T findNthSmallest(List<T> list, int n) {
[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);
}
}
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
[...]
new ArrayList<Integer>(){{
add(1);
add(2);
add(3);
add(4);
add(5);
add(6);
add(7);
add(8);
}};[/Java]
[...][/QUOTE]
mit diesen Werten bekomme ich bereits einen Fehler oO
mit den anderen nicht, zumindest nicht beim compilieren...
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.
[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
Java:
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)
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...
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);
}
