Quicksort

[Elfenlied]

Hallo! ich soll einen Quicksort implementieren bzw modifizieren. Ich muss mich deshalb erstmal mit dem Code auseinandersetzen und ich frage mich was der Unterstrich zu bedeuten hat.

public static void quicksort (int [] a) {
_quicksort (a ,0,a. length -1); // [a0, . . . ,an-1]
}
static void _quicksort (int [] a,int l, int r) {
if (r>l) { // [al, . . . ,ar]
int m= partition (a,l,r); // pivot p = am
_quicksort (a,l,m -1);
_quicksort (a,m+1,r);
}
}


warum muss dort ein _quicksort hin und nicht nur quicksort. Kann mir das jemand sagen?!

 

[Gast2]

1) Benutze Java-Tags:

public static void quicksort (int [] a) {
_quicksort (a ,0,a. length -1); // [a0, . . . ,an-1]
}
static void _quicksort (int [] a,int l, int r) {
if (r>l) { // [al, . . . ,ar]
int m= partition (a,l,r); // pivot p = am
_quicksort (a,l,m -1);
_quicksort (a,m+1,r);
}
}

2) Es muss _quicksort heißen da die Methode als _quicksort deklariert wurde!

...
static void _quicksort (int [] a,int l, int r) // <-- Das ist die Deklaration. Sprich der Name der Methode.
...

 

[Dow Jones]

Der Unterstrich hat gar keine besondere Bedeutung. "quicksort" und "_quicksort" sind einfach zwei verschiedene Methoden denen man (zufällig?) ähnlich klingende Namen gegeben hat. Aber sie könnten ebensogut auch "bahnhof" und "bratkartoffel" heissen. Mach dir darüber keine Gedanken; betrachte sie einfach als das was sie sind: Zwei verschiedene Methoden, die von Haus aus nichts mit einander zu tun haben.

 

[Elfenlied]

achso das ist einfach ein teil des namens sozusagen. Und ich google mir schon die finger wund, welch besonderer befehl dahintersteckt haha ok dann ist alles gut. Danke

 

[Gast2]

achso das ist einfach ein teil des namens sozusagen. Und ich google mir schon die finger wund, welch besonderer befehl dahintersteckt haha ok dann ist alles gut. Danke

Jap. Ich persöhnlich fände internalQuicksort(...) besser als _quicksort. Scheint eher eine nach außen nicht zu verwendende interne Implementierungsmethode zu sein. Aber ja genau es ist nur Teil des Namens.

 

[Elfenlied]

	 public static <T extends Comparable<T>> void quickSort(Time[]a) {
	    	_quicksort (a ,0,a. length -1); // [a0, . . . ,an-1]

	    }
		static void _quicksort (Time[] a,int l, int r) {
		if (r>l) { // [al, . . . ,ar]
		int m= partition (a,l,r); // pivot p = am
		_quicksort (a,l,m -1);
		_quicksort (a,m+1,r);
		}
		}
		
		static int partition ( Time[] a,int l,int r) {
			assert (l <=r);
			Time p=a[r];// pivot
			Time t;
			int i=l, j=r -1;
			do {
			while (a[i].compareTo(p)==-1) ++i; // find
			while (j >0 && (a[j].compareTo(p)==1)) --j;
			t=a[i]; a[i]=a[j]; a[j]=t; // swap
			} while (i<j);
			a[j]=a[i]; a[i]=a[r]; a[r]=t;
			return i; // new index of pivot
			}

public static void main (String[] args){
		Time [] a = {new Time(1,24),new Time (4,54),new Time(13,29),new Time(1,0)};
		quickSort(a);
		for ( int i =0;i<a.length;i++) {
    		System.out.print(a[i]+" " );
    	}

ich hab doch noch weitere Anliegen. Also das ist der kompette Quicksort.

Also ich habe Array, Time[]a= new und halt Zeitobjekte, die ich sortiert haben will

So dann setze ich es in Quicksort ein, quicksort(a).

Jetzt will ich verstehen wie es arbeitet.

Es geht praktisch in quicksort rein (also 1.Zeile).

da werden die Daten jetzt also weitergereicht in _quicksort?

also: _quicksort(a,0,a.length-1)

d.h. also a,0,3 (weil das Array 4 Elemente hat???)

0 ist die linke Grenze also der Anfang des Arrays und 3 das Ende.

So und jetzt ist das für mich etwas durcheinander, wenn meine Schlussfolgerungen
bis hierhin richtig sind.

[Java]int m= partition (a,l,r); // pivot p = am
_quicksort (a,l,m -1);
_quicksort (a,m+1,r);[/code]

also m=partion (a,l,r) wenn r>l (was ja immer der Fall ist eigentlich)

mir wird einfach nicht klar was dort passiert.

Weil er soll jetzt den Input von _quicksort in partition übergeben.
Aber warum dieser Schritt? warum nicht gleich von quicksort auf partition???

(Zeile 8 und 9 sind mir völlig unklar).

Den Teil partition lass ich jetzt erstmal aus ich will es nur bis hierhin ERSTMAL verstehen

 

[Bernd Hohmann]

Hier ist das schön erklärt und in einem Applet Schritt für Schritt dargestellt.

Bernd

 

[Elfenlied]

sry aber da finde ich das schlecht erklärt...ich meine mir ist Quicksort ungefähr bekannt, aber das verwirrt mich ja total

 

[Dow Jones]

Es geht praktisch in quicksort rein (also 1.Zeile).
da werden die Daten jetzt also weitergereicht in _quicksort?

Genau. Das dient vermutlich einerseits um es dem Anwender bequemer zu machen die Sortiermethode zu benutzen und andererseits dient es dem information hiding. Der Anwender braucht (und soll) gar nicht wissen das in dem Quicksort-Algorithmus irgendwelche Arraygrenzen verwendet werden.

also: _quicksort(a,0,a.length-1)
d.h. also a,0,3 (weil das Array 4 Elemente hat???)
0 ist die linke Grenze also der Anfang des Arrays und 3 das Ende.

Genau. Ein Array von nur 4 Elementen ist allerdings etwas zu klein um wirklich zu erkennen was Quicksort macht. Verwende doch stattdessen mal ein Array mit 10 Elementen, z.B. [c]{3, 0, 1, 8, 7, 2, 5, 4, 9, 6}[/c]

Der Grundgedanke bei Quicksort ist nun: Wir wählen ein beliebiges Element des Arrays aus (im folgenden Referenzelement genannt, wir wählen jetzt mal das erste Element: Die 3) und sorgen dafür das dieses Element an seine endgültige Position im Array wandert. Wir wissen zwar noch nicht wo diese Position ist, aber wir können sie folgendermaßen beschreiben: Das Referenzelement befindet sich genau dann an seiner endgültigen Position wenn alle Werte "links" vom Referenzelement kleiner/gleich sind als das Referenzelement. Ebenso müssen alle Werte "rechts" vom Referenzelement größer/gleich dem Referenzelement sein.

Wenn wir unser Array also derart modifizieren könnten das es beispielsweise so aussieht: [c]{2, 0, 1, _3_, 7, 8, 5, 4, 9, 6}[/c] Dann wissen wir das sich unser Referenzelement (3) bereits an seiner endgültigen Position befindet, so daß wir es nie wieder betrachten müssen. Alle Werte links von der drei sind kleiner/gleich 3, alle Werte rechts davon sind größer/gleich 3. Und dieses Wissen nutzen wir gleich aus.


Aber erstmal stellt sich ja die Frage wie wir das Array überhaupt so modifizieren, das die beiden oben genannten Bedingungen erfüllt sind. Na, das ist eigentlich nicht schwer. Wir vergleichen das Referenzelement halt der Reihe nach mit allen anderen Werten des Arrays. Sollten wir dabei feststellen, das unsere Bedingungen mal nicht erfüllt sind (also ein Element < 3 rechts vom Referenzelement steht, oder ein Element > 3 links vom Referenzelement) dann vertauschen wir das Referenzelement und das falsch positionierte Element einfach. Nach dem Vertauschen fahren wir dann wie gewohnt mit dem Vergleichen der restlichen Elemente fort.

Diesen gesamten Vorgang, also ein Referenzelement an seine endgültige Position zu schieben, erledigt bei dir die Methode partition. Dafür bekommt sie das zu sortierende Array sowie die linke und rechte Grenze des zu verarbeitenden Bereichs innerhalb des Arrays übergeben (zu den Grenzen gleich mehr; beim allerersten Aufruf bearbeitet die Methode jedenfalls ersteinmal das gesamte Array. Sie vergleicht das Referenzelement also mit allen anderen Werten des gesamten Arrays).


Wenn die Methode partition endet - was haben wir dann? Wir haben ein Element (das Referenzelement) an seine endgültige Position verschoben. Und wir haben das Array dadurch auch gleich in zwei Teile zerlegt: Alle Elemente die links vom Referenzelement stehen ([c]{2, 0, 1[/c])sind kleiner/gleich dem Referenzelement, die Elemente die rechts davon stehen ([c]{7, 8, 5, 4, 9, 6}[/c])sind größer/gleich. Und daraus können wir unschwer folgern, das wir die Elemente des linken Teilarrays gar nicht erst mit den Elementen des rechten Teilarrays zu vergleichen brauchen, und umgekehrt. Die linken Elemente sind ja sowieso allesamt kleiner/gleich den rechten Elementen. Wir können also jetzt ersteinmal hergehen und das linke Teilarray in aller Ruhe sortieren (ohne uns auch nur im geringsten um den rechten Teil des Arrays kümmern zu müssen). Und danach können wir in aller Ruhe das rechte Teilarray sortieren (ohne uns irgendwie um das linke Teilarray zu kümmern zu müssen).


Bleibt noch die Frage wie wir denn nun so ein Teilarray sortieren. Nun, man könnte sich ja ein beliebiges Element aus dem Teilarray als neues Referenzelement heraussuchen und dafür sorgen das es an seine endgültige Position wandert. Und dann könnte man das Teilarray links davon sowie das Teilarray rechts davon unabhängig voneinander sortieren. Zum Beispiel indem wir uns in den jeweiligen
neuen Teilarrays ein Referenzelement suchen und... so weiter und so fort.

Genau das ist die Idee des Quicksorts. Wir befördern ein Element an seine endgültige Position und zerlegen das Gesamtarray dadurch in zwei Teilarrays. In diesen Teilarrays schieben wir wieder jeweils ein Element an seine endgültige Position und zerlegen die bishereigen Teilarray dadurch auch wieder in jeweils zwei neue Teilarrays. Und so weiter. Dadurch erhalten wir zwar immer mehr zu sortierende Teilarrays, aber dafür werden diese auch immer kleiner. Bis sie irgendwann so klein sind, das ihre Sortierung trivial wird (z.B. wenn ein Teilarray nur noch zwei Elemente umfasst; diese beiden Elemente zu sortieren ist so einfach das wir das erledigen können ohne noch weiter zu unterteilen).

In deinem Programmcode wählt die Methode partition ein Referenzelement aus, schiebt es an seine aktuelle Position, und liefert diese Position als Rückgabewert zurück (m). Diese Position stellt die Grenze zwischen den beiden noch zu sortierenden Teilarrays dar. Anschließend wird zweimal _quicksort aufgerufen, einmal für das linke Teilarray (daher die Grenzen l und m-1) und einmal für das rechte Teilarray (welches die Grenzen m+1 und r hat). Die Methode _quicksort ruft nun partition auf um ein Element (aus dem beim Aufruf übergebenen Teilarray) an seine endgültige Position zu schieben und dadurchzwei neue Teilarrays zu schaffen. Für diese beiden neuen Teilarrays wird wiederum jeweils einmal _quicksort aufgerufen. Und so weiter. Durch diese rekursiven Aufrufe wird schlußendlich das gesamte Array sortiert.


Und wenn du bei diesen Erklärungen noch nicht eingeschlafen bist kannst du dir hier auch mal anschauen wie das Vergleichen/Vertauschen von Werten und das Teilen des Arrays vonstatten geht.