QuickSort - kurze Frage

Status
Nicht offen für weitere Antworten.
J

jhjp

Gast
Hallihallo,
also ich hab die Aufgabe nen QuickSort Algorithmus zu programmieren! Habs auch gemacht, siehe unten. Der Code funktioniert auch, jedoch nur für Felder mit der Länge 14. Bei längeren Feldern kommt ein StackOverflowError.
Wahrscheinlich weil die Rekursion zu tief geht! Liege ich in dieser Annahme richtig?????

und noch ne Frage: Ist das ein Algorithmus im Sinne des QuickSort???
(Hab vom Prof. zwar ne Vorlage bekommen, kann die aber nicht implementieren, weil er in einer Methode 2 Rückgabewerte macht, und ich weiß nicht wie man das in Java umsetzt.. :cry: )

Also hier mein Code (Bin ganz stolz darauf, habs in 20Minuten programmiert :D und es hat fast auf anhieb funktioniert)

Code:
   public static int[] QuickSort(int[] f){
		if(f.length == 1) return f;
		else{
			int p = pivotzerlegung(f);
			
			int f1length = lengthkleinergleich(f, p);
			int f2length = lengthgroesser(f, p);
			int[] f1 = new int[f1length];
			int[] f2 = new int[f2length];
			
			int if1 = 0; int if2 = 0;
			for(int i=0; i<f.length; i++){
				if(f[i] <= p){
					f1[if1] = f[i];
					if1++;
				}
				else{
					f2[if2] = f[i];
					if2++;
				}
			}
			return combine( QuickSort(f1), QuickSort(f2) );
		}
	}

	private static int pivotzerlegung(int[] f){
		int summe = 0;
		for(int i=0; i<f.length; i++) summe += f[i];
		return summe/f.length;
	}

	private static int lengthkleinergleich(int[] f, int p){
		int summekleinergleich = 0;
		for(int i=0; i<f.length; i++) if(f[i] <= p) summekleinergleich++;
		return summekleinergleich;
	}

	private static int lengthgroesser(int[] f, int p){
		int summegroesser = 0;
		for(int i=0; i<f.length; i++) if(f[i] > p) summegroesser++;
		return summegroesser;
	}
	
   private static int[] combine(int[] f1, int[] f2){
		int[] neu = new int[f1.length + f2.length];
		for(int i=0; i<f1.length; i++) neu[i] = f1[i];
		for(int i=0; i<f2.length; i++) neu[f1.length + i] = f2[i];
		return neu;
	}
gruß
beni
 

kopfsalat

Bekanntes Mitglied
Hab mir den Code jetzt nicht wirklich angesehen, aber allgemein zu Quicksort:

Startet man einen Standard-Quicksort mit einer Eingabe, die über große bereits sortierte Bereiche verfügt, wird die Pivotzerlegung stets sehr ungünstig gewählt, und der Algorithmus gerät in seine miserable worst-case-Laufzeit, was meistens im stack-overflow endet, bevor auch nur ein Element sortiert wurde.

Abhilfe schaffen da Abwandlungen vom Quicksort:
- Median-Quicksort
- Random-Quicksort
- Hoare-Partition-Quicksort
- ggf. iterativer Quicksort, um zu tiefe Rekursionstiefen zu vermeiden, oder Kombinationen wie z.B. Hoare- und Median.

Hier ein Link zu Folien einer Vorlesung dazu:
http://wwwcs.upb.de/cs/ag-bloemer/lehre/dua_SS2004/material/folien09.pdf
http://wwwcs.upb.de/cs/ag-bloemer/lehre/dua_SS2004/material/folien10.pdf
 

mic_checker

Top Contributor
jhjp hat gesagt.:
(Hab vom Prof. zwar ne Vorlage bekommen, kann die aber nicht implementieren, weil er in einer Methode 2 Rückgabewerte macht, und ich weiß nicht wie man das in Java umsetzt.. :cry: )
Schau dir mal folgenden Thread an, da wird am Ende ein ähnliches Problem behandelt. Wenn du nur zwei zurückgeben willst, kannst du wie dort auch steht "Point" verwenden, ansonsten schreibst du dir halt deine eigene Klasse.
http://www.java-forum.org/de/viewtopic.php?t=14255&highlight=point
 

Bleiglanz

Gesperrter Benutzer
ja ist im sinne von quicksort, aber bei 14 schon ein Stack-Overflow? sehr seltsam...

>> if(f.length == 1) return f;

mach mal lieber length<=3 als abbruch, solche felder kannst du sofort von hand sortieren ("nicht soweit runter rekursieren")

wenn du mit 14 gleichverteilten reingehst, dann sollte es nur
wenige rekurstionsstufen geben

mit 14 aufgerufen
mit 7 aufgerufen 2mal
mit 3 oder 4 aufgerufen 4 mal
mit 1 oder 2 aufgerufen 8 mal

das ist recht wenig...

könnte es sein, dass bei dir - in gewissen Situationen - am ende arrays der länge 0 entstehen und er deshalb endlos rekursiert? scheint mir wahrscheinlich...
 
J

jhjp

Gast
danke für die Antworten:
@bleiglanz:
also ich hab mir das jetzt mal genauer angeschaut und bemerkt, dass nur ein Stack overflow kommt, wenn ich doppelte Zahlen ungeschickt verteilt hab. So z.b.
18|7|12|18|7|11|6|6|3|6|18|3|7|3|14|14|

Dann sieht das erste "Hilfsfeld" so aus:
7|7|6|6|3|6|3|7|3|

und das dann rekursiv aufgerufene Hilfsfeld sieht wiederum so aus:
3|3|3|
und jetzt geht er in ne endlos-rekursion!
(Ach ja, bei ungefähr 2000 rekursionsschritten kommt dann der StackOverflowError)


Vollständigkeitshalber: hab den Code nun erweitert, dass er auch bei gleichen Zahlen weitersortiert:
Code:
public static int[] QuickSort(int[] f){
		for(int i = 0; i<f.length; i++) System.out.print(f[i]+"|"); System.out.println();
		if(f.length == 1) return f;
		else{
			int p = pivotzerlegung(f);
			
			int f1length = lengthkleinergleich(f, p);
			int f2length = lengthgroesser(f, p);
			int[] f1 = new int[f1length];
			int[] f2 = new int[f2length];
			
			int if1 = 0; int if2 = 0;
			for(int i=0; i<f.length; i++){
				if(checkgleichheit(f)) return f;
				if(f[i] <= p){
					f1[if1] = f[i];
					if1++;
				}
				else{
					f2[if2] = f[i];
					if2++;
				}
			}
			return combine( QuickSort(f1), QuickSort(f2) );
		}
	}

	private static boolean checkgleichheit(int[] f){
		boolean check = true;
		for(int i=0; i<f.length-1; i++) if(f[i] != f[i+1]) check = false;
		return check;
	}

	private static int pivotzerlegung(int[] f){
		int summe = 0;
		for(int i=0; i<f.length; i++) summe += f[i];
		return summe/f.length;
	}

	private static int lengthkleinergleich(int[] f, int p){
		int summekleinergleich = 0;
		for(int i=0; i<f.length; i++) if(f[i] <= p) summekleinergleich++;
		return summekleinergleich;
	}

	private static int lengthgroesser(int[] f, int p){
		int summegroesser = 0;
		for(int i=0; i<f.length; i++) if(f[i] > p) summegroesser++;
		return summegroesser;
	}

	private static int[] combine(int[] f1, int[] f2){
		int[] neu = new int[f1.length + f2.length];
		for(int i=0; i<f1.length; i++) neu[i] = f1[i];
		for(int i=0; i<f2.length; i++) neu[f1.length + i] = f2[i];
		return neu;
	}

Hab den Code mit nem Feld der Länge 10 000 ausprobiert: Funzt einwandfrei!

Gruß
Beni
 
J

jhjp

Gast
Hab mir jetzt mal den Point angeschaut (wegen den 2 Rückgabewerten)!
Das geht bei mir nicht, weil ein Rückgabewert ein int[] und der andere ein int ist!!!! Point kann aber nur int annehmen.

Gibts da noch ne möglichkeit das hinzubekommen, ohne mir ein Objekt selbst zu definieren!?

Gruß
Beni
 

Wildcard

Top Contributor
Wo ist den das Problem ein Objekt selbst zu definieren?
Oder nimm ein Objekt[] und mach aus dem int ein Integer
 

kopfsalat

Bekanntes Mitglied
Hab mir den Code jetzt mal angesehen.
Zuerst mal:
Dein Algorithmus läuft ja so, dass zuächst ein Pivotwert nach dem arithmetischen Mittel aller Elemente des übergebenen Arrays bestimmt wird.
Dann werden alle Werte, die kleiner oder gleich sind in ein neues 'linkes', und alle die größer sind in ein neues 'rechtes' Array gepackt.

Soweit, so gut, das Problem ist, dass das so nur funktioniert, wenn die Elemente alle unterschiedliche Werte haben:
Angenommen, gegen Ende wird ein Array der Größe 2 an Quicksort übergeben mit den Elementen (20,20)
Dein Pivotwert wird zu (20+20)/2 = 20 bestimmt. Dann werden alle Elemente <= 20 nach links, die anderen nach rechts geschoben. Damit hat man links das array wieder der Größe 2 mit den Elemente (20,20) und rechts ein leeres der Größe 0.

Das Problem musst Du beheben. Auch kann dass von Anfang an passieren, z.B. wenn das zu sortierende Array von vorneherein nur aus gleichen Zahlen besteht.

Noch 2 Dinge:
a) in Zeile 3 nimm lieber " if(f.length <= 1) " denn ein Aufruf mit length=0 kann passieren
b) in der Pivotzerlegung nimm "long summe = 0;" denn summe kann größer als ein int werden
 
J

jhjp

Gast
@kopfsalat:
hab den code ja bereits geändert...

das artihmetische Mittel der Elemente im Array ist schon im Sinne des QuickSorts, oder?
Mein Prof. hat das irgendwie anders gemacht, blick da eh net durch...

gruß
beni
 

kopfsalat

Bekanntes Mitglied
Tsja, da hatte ich vor dem Posten nicht nochmal den Thread aktualisiert, so ein Mist, der Aufwand umsonst ;-)

Der 'eigentliche' Quicksort arbeitet anders:
Es wird einfach das linkeste Element im Array unabhängig von dessen Wert als Pivot genutzt. Dann wird das Array mit diesem Pivot entsprechend sortiert, so dass am Ende des Vorgangs links vom Pivot alle kleineren Werte, rechts von ihm alle größeren stehen. Je nach Vorsortierung kann es dabei zu äußerst ungüngstigen Partitionen kommen, wenn z.B. ganz links (als Pivot) immer der kleinste Wert des Arrays steht. Im 'Mittel' ist die Laufzeit aber sehr gut. In der Praxis jedoch sind nicht alle Vorsortierungen gleichwahrscheinlich, sondern es tauchen oft Arrays auf, die bereits große sortierte Bereiche enthalten.

Median-Quicksort nimmt einfach das Element, was genau in der Mitte des Arrays steht, unabhängig von dessen Wert als Pivot und verfährt dann genau wie der normale Quicksort. Damit ist er auf vorsortierten Arrays sehr schnell, aber es existieren immernoch schlimme Kombinationen, darunter die, wenn viele gleiche Elemente drin sind, sowie die Restwahrscheinlichkeit (die extrem gering ist), dass das Array am Anfang zwar völlig chaotisch ist, aber dummerweise diese Unordnung genau zur schlimmsten Partitionenfolge führt.

Randomized-Quicksort arbeitet wir die anderen, nimmt aber ein zufälliges Element aus dem Array als Pivot. Dadurch verhält er sich ähnlich wie Median, es existieren lediglich noch die extrem unwahrscheinliche Anfangs-Unordnungen.

Hoare-Quicksort startet links und rechts am Array-Rand und geht nach Auswahl eines Pivots von beiden Seiten gen Mitte. Damit ist er auch für Arrays mit großen Bereichen gleicher Elemente sehr gut geeignet.

Die von dir gepostete Quicksort-Variante kannte ich noch nicht, klingt aber interessant, zumindest wird der Pivot im Normalfall so gewählt, dass die Partition etwa 50/50 wird, was optimal ist. Nachteil ist sicherlich das ewige Aufsummieren aller Elemente. Einerseits kostet das Zeit (müßte man schauen, inwiefern das durch gute Partitionen wettgemacht wird), und der Wertebereich kann durchaus überschritten wird! Alternativ, da es ja nicht genau auf +/- 1 ankommt - könnte man bei der Pivotzerlegung auch statt dem 'nächsthöheren' Datentyp (z.B. int->long) auch das arithmetische Mittel in jedem Schleifendurchlauf bilden und in einer double-Zahl speichern, diese dann nachher als int zurückgeben.
Ein anderer Nachteil ist, dass diese Form hier nur mit Arrays arbeiten kann, die Elemente enthalten, die sich summieren lassen. Jeder andere Quicksort ist ein reiner Vergleichssortierer, kann also jedes Array sortieren, welche anordbare Objekte mit einer Vergleichsmöglichkeit auf <, =, > bietet (Also auch irgendwelche Objekte mit einer compare-Methode), da die nicht summiert werden müssen.

Fazit: Welches Quicksort-Derivat man nimmt, kommt immer drauf an...
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
I Java Quicksort PAP Java Basics - Anfänger-Themen 2
B Quicksort in Verbindung mit einem Projekt Java Basics - Anfänger-Themen 1
M QuickSort und Liste Java Basics - Anfänger-Themen 6
S Laufzeit Quicksort wenn alle Elemente gleich sind Java Basics - Anfänger-Themen 4
G Quicksort Algorithmus Java Basics - Anfänger-Themen 12
Hanschyo Quicksort sortiert von groß nach klein Java Basics - Anfänger-Themen 3
R Quicksort mit Interface Comparable Java Basics - Anfänger-Themen 6
L Quicksort verstehen Java Basics - Anfänger-Themen 3
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 5
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 0
J Quicksort mit Stack Java Basics - Anfänger-Themen 4
Liondary Quicksort Java Basics - Anfänger-Themen 20
K Quicksort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
S Quicksort Algorithmus Java Basics - Anfänger-Themen 2
D Java Quicksort Java Basics - Anfänger-Themen 5
A Frage zu QuickSort Java Basics - Anfänger-Themen 9
B Quicksort mit Durchschnitt als Pivot Java Basics - Anfänger-Themen 1
K Quicksort Java Basics - Anfänger-Themen 3
M Quicksort - Probleme Java Basics - Anfänger-Themen 5
T QuickSort implementieren Java Basics - Anfänger-Themen 5
R QuickSort Verständis Problem (?) Java Basics - Anfänger-Themen 2
M Quicksort implementierung Java Basics - Anfänger-Themen 23
E Quicksort Java Basics - Anfänger-Themen 8
Xendarii Quicksort gibt kein Ergebnis aus Java Basics - Anfänger-Themen 13
E QuickSort: Ergebniss speichern Java Basics - Anfänger-Themen 2
P quickSort eines Objekt-Arrays geht nicht! Java Basics - Anfänger-Themen 11
F Stackoverflow bei Quicksort Java Basics - Anfänger-Themen 2
F Quicksort Java Basics - Anfänger-Themen 22
C Quicksort Invariante Java Basics - Anfänger-Themen 2
C QuickSort - Pivot in der Mitte Java Basics - Anfänger-Themen 5
P QuickSort iterativ Java Basics - Anfänger-Themen 5
K Eine Frage zum Quicksort Java Basics - Anfänger-Themen 11
B Quicksort --> Methodenaufruf Java Basics - Anfänger-Themen 10
B QuickSort - Fehler nicht zu finden Java Basics - Anfänger-Themen 2
W Quicksort Problem Java Basics - Anfänger-Themen 3
A Quicksort, #Vergleiche zählen klappt nicht Java Basics - Anfänger-Themen 3
J Quicksort Implementierung-- Exception ArrayOutOfBounds Java Basics - Anfänger-Themen 6
M Fehler in meinem Quicksort! Java Basics - Anfänger-Themen 21
B Quicksort Struktogramm Java Basics - Anfänger-Themen 9
G Frage zu Quicksort Java Basics - Anfänger-Themen 18
0 Quicksort bsp Java Basics - Anfänger-Themen 5
B Quicksort Problem Java Basics - Anfänger-Themen 6
S Mein Quicksort Problem: he method quickSort(int[], int, int) Java Basics - Anfänger-Themen 2
M Quicksort Java Basics - Anfänger-Themen 2
C Quicksort raten Java Basics - Anfänger-Themen 2
K ArrayList sortieren mit Quicksort Java Basics - Anfänger-Themen 3
M Quicksort Java Basics - Anfänger-Themen 4
J Quicksort programmieren Probleme Java Basics - Anfänger-Themen 9
S Quicksort Programm Java Basics - Anfänger-Themen 7
D Quicksort Java Basics - Anfänger-Themen 3
K Parameterübergabe bei quickSort Java Basics - Anfänger-Themen 6
S QuickSort will mir nicht in den Kopf (an einer Stelle) Java Basics - Anfänger-Themen 14
0 Quicksort Java Basics - Anfänger-Themen 2
M QuickSort Java Basics - Anfänger-Themen 4
H Quicksort und Rekursiv: Türme von Hanoi Java Basics - Anfänger-Themen 9
F Kurze Frage zu replace() Java Basics - Anfänger-Themen 19
Vivien Kurze Verständnisfrage zu Java Point aus java.awt.* Java Basics - Anfänger-Themen 5
dieter000 Kurze Frage kann mir ejmand kurz diesen Code erklären, bzw wie man die zeilen erklärt und so Java Basics - Anfänger-Themen 1
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
M Rationale Zahl erkennen - Kurze Frage zum Restwert nach Division Java Basics - Anfänger-Themen 3
S Kurze Verständnissfrage Java Basics - Anfänger-Themen 4
L Kurze Frage... Java Basics - Anfänger-Themen 2
C Kurze Frage zur Polymorphie Java Basics - Anfänger-Themen 1
B Rekursion Schneeflocke - Kurze Frage zur Methode Java Basics - Anfänger-Themen 11
TechGirl LinkedList - kurze allgemeine Frage Java Basics - Anfänger-Themen 17
T Objektorientierung-Kurze Frage Java Basics - Anfänger-Themen 5
L Kurze Frage zu verschachtelten Schleifen Java Basics - Anfänger-Themen 3
D Compiler-Fehler kurze Frage (Fehler): runde Klammern im Println Java Basics - Anfänger-Themen 3
N Kurze Hilfe !! Java Basics - Anfänger-Themen 3
A 2 kurze Anfänger fragen Java Basics - Anfänger-Themen 6
M Baum Code kurze frage ... Java Basics - Anfänger-Themen 6
M kurze frage zu meinem Code ... Java Basics - Anfänger-Themen 3
T Kurze Frage zu Arrays Java Basics - Anfänger-Themen 4
S Java - Client/Server mit Stomp kurze Frage Java Basics - Anfänger-Themen 0
T Eine kurze frage vor der prüfung bitte. Java Basics - Anfänger-Themen 5
X Kurze Frage zu Java Doc Java Basics - Anfänger-Themen 3
G Kurze Frage zu Arrays Java Basics - Anfänger-Themen 3
G Warteschlange/Reihungen kurze syntaktische Frage Java Basics - Anfänger-Themen 2
J Erste Schritte Kurze Frage zu Listenern und If-Bedingung Java Basics - Anfänger-Themen 2
B Methoden Tricky, kurze Schreibweise? Java Basics - Anfänger-Themen 3
M Kurze Verständnisfrage zu einer Java Aufgabe Java Basics - Anfänger-Themen 12
S Erste Schritte HashMap Kurze Frage - Werte über Schleife ausgeben Java Basics - Anfänger-Themen 30
M kurze frage: Ohne index.of position von string angeben Java Basics - Anfänger-Themen 16
V Ganz kurze Java-Hilfe - Ich finde meinen Fehler nicht Java Basics - Anfänger-Themen 4
R Kurze Linien alle x-Pixel Java Basics - Anfänger-Themen 2
A Methoden Langer Text, kurze Frage Java Basics - Anfänger-Themen 10
S Kurze Frage zur Effizienz: Java Basics - Anfänger-Themen 4
R Kurze Ouelltext frage Java Basics - Anfänger-Themen 3
U ArrayList kurze Einführung Java Basics - Anfänger-Themen 3
2 Datentypen Kurze Schreibform bei ArrayList (Vs String Array) Java Basics - Anfänger-Themen 6
M kurze Frage zu Graphics Java Basics - Anfänger-Themen 5
P OOP 3 kurze Fragen Java Basics - Anfänger-Themen 2
J Benötige kurze Definition zum Programm Java Basics - Anfänger-Themen 2
Screen Kurze Frage Umwandlung von Zahlen Java Basics - Anfänger-Themen 2
J Math.random() - kurze frage. Java Basics - Anfänger-Themen 20
S Kurze Frage zum Ergebniss Java Basics - Anfänger-Themen 5
R klausurvorbereitung uni HILFE!! kurze fragen,kurze antworten Java Basics - Anfänger-Themen 9
A kurze frage zu arrays und deren zuweisung Java Basics - Anfänger-Themen 11
J Kurze Frage zur Primzahlberechnung Java Basics - Anfänger-Themen 8
B kurze Frage if(!) Java Basics - Anfänger-Themen 19

Ähnliche Java Themen

Neue Themen


Oben