Quicksort - Versionsgeschichte

Akaibel am 23. Januar 2022 um 16:52 Uhr

2022-01-23T16:52:25Z

← Nächstältere Version		Version vom 23. Januar 2022, 16:52 Uhr
Zeile 39:		Zeile 39:


	<code>		<code>
	public List<Person> quicksort(List<Person> pList){		public List<Person> quicksort(List<Person> pList){
	'''// leere Ergebnis-Liste erzeugen'''		'''// leere Ergebnis-Liste erzeugen'''
Zeile 78:		Zeile 78:
	return ergebnis;		return ergebnis;
	}		}
	</code>		</code>

Akaibel: /* für Arrays */

2020-03-09T08:10:36Z

für Arrays

@@ Zeile 78: / Zeile 78: @@
             return ergebnis;
+          }
 </code>

Akaibel: /* Prinzip */

2019-06-23T13:56:00Z

Prinzip

← Nächstältere Version		Version vom 23. Juni 2019, 13:56 Uhr
Zeile 9:		Zeile 9:

	<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>		<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>

			=Fachbegriffe=

			rekursiv, Divide-Conquer-Prinzip, Pivot-Element, Abbruchbedingung, Laufzeit

	=Prinzip=		=Prinzip=

	Quicksort arbeitet nach dem '''Divide-and-Conquer-Prinzip''':		Quicksort arbeitet nach dem '''Divide-and-Conquer-Prinzip''':

Akaibel: /* für Listen */

2017-12-03T09:19:31Z

für Listen

← Nächstältere Version		Version vom 3. Dezember 2017, 09:19 Uhr
Zeile 35:		Zeile 35:

	<code>		<code>
	public List<Person> quicksort(List<Person> pList){		public List<Person> quicksort(List<Person> pList){
	if(pList.isEmpty()){		'''// leere Ergebnis-Liste erzeugen'''
	return ~~pList~~;		List<Person> ergebnis = new ListWithViewer<Person>();
	}		'''// Abbruchbedingung für die leere Liste'''
	pList.toFirst();		if(pList.isEmpty()){
	Person pivot = pList.getContent();		return ergebnis;
	pList.next();		}
	~~if(!pList.hasAccess()){~~		'''// das erste Element der Liste als Pivot-Element festlegen'''
	~~return pList;~~		pList.toFirst();
	}		Person pivot = pList.getContent();
	List<Person> ~~kleiner~~ = new List<>();		'''// zum nächsten Element gehen'''
	List<Person> ~~groesser~~ = new List<>();		pList.next();
	while(pList.hasAccess()){		'''// die Listen links und rechts als leere Listen erzeugen
	Person ~~aktuell~~ = pList.getContent();		List<Person> links = new List<Person>();
	if(~~aktuell~~.getEinkommen() < pivot.getEinkommen()){		List<Person> rechts = new List<Person>();
	~~kleiner~~.append(~~aktuell~~);		'''// pList durchlaufen und die Elemente mit pivot vergleichen:'''
	}		'''// kleinere kommen nach links, die anderen nach rechts.'''
	else{		while(pList.hasAccess()){
	~~groesser~~.append(~~aktuell~~);		Person p = pList.getContent();
	}		if(p.getEinkommen() < pivot.getEinkommen()){
	pList.next();		links.append(p);
	}		}
	List<Person> ~~kleinerSortiert~~ = quicksort(~~kleiner~~);		else{
	List<Person> ~~groesserSortiert~~ = quicksort(~~groesser~~);		rechts.append(p);
			}
	~~List<Person>~~ ergebnis ~~= new ListWithViewer<Person>();~~		pList.next();
	ergebnis.concat(~~kleinerSortiert~~);		}
	ergebnis.append(pivot);		'''// rekursive Aufrufe von quicksort für links und rechts'''
	ergebnis.concat(~~groesserSortiert~~);		List<Person> linksSortiert = quicksort(links);
	return ergebnis;		List<Person> rechtsSortiert = quicksort(rechts);
	}		'''// die sortierten Teillisten und das Pivot-Element'''
			'''// in der richtigen Reihenfolge an ergebnis anhängen'''
			ergebnis.concat(linksSortiert);
			ergebnis.append(pivot);
			ergebnis.concat(rechtsSortiert);
			'''// die ergebnis-Liste zurückgeben'''
			return ergebnis;
			}
	</code>		</code>

Akaibel: /* für Listen */

2016-11-17T18:48:36Z

für Listen

← Nächstältere Version		Version vom 17. November 2016, 18:48 Uhr
Zeile 60:		Zeile 60:
	List<Person> groesserSortiert = quicksort(groesser);		List<Person> groesserSortiert = quicksort(groesser);

	List<Person> ergebnis = new ListWithViewer<>();		List<Person> ergebnis = new ListWithViewer<Person>();
	ergebnis.concat(kleinerSortiert);		ergebnis.concat(kleinerSortiert);
	ergebnis.append(pivot);		ergebnis.append(pivot);

Akaibel: /* Prinzip */

2016-11-14T19:41:14Z

Prinzip

← Nächstältere Version		Version vom 14. November 2016, 19:41 Uhr
Zeile 15:		Zeile 15:
	Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt (='''Divide'''). Dazu wählt Quicksort ein sogenanntes '''Pivotelement''' aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.		Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt (='''Divide'''). Dazu wählt Quicksort ein sogenanntes '''Pivotelement''' aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.

	Anschließend wird jede Teilliste in sich sortiert~~. Dazu wird~~ der Quicksort-Algorithmus '''rekursiv''' auf ~~der linken~~ und ~~auf der rechten~~ Teilliste ~~ausgeführt~~. Wenn eine Teilliste ~~leer ist~~, ~~erfolgt der Abbruch der~~ Rekursion, d. h. für diese Teilliste wird Quicksort nicht mehr aufgerufen.		Anschließend wird jede Teilliste in sich sortiert, indem der Quicksort-Algorithmus '''rekursiv''' auf die linke und die rechte Teilliste angewendet werden. Wenn eine Teilliste nur ein oder kein Element enthält, bricht die Rekursion ab, d. h. für diese Teilliste wird Quicksort nicht mehr aufgerufen.

	Am Ende werden die beiden Teillisten und das Pivot-Element zusammengeführt (='''Conquer''').		Am Ende werden die beiden Teillisten und das Pivot-Element zusammengeführt (='''Conquer''').

Akaibel: Akaibel verschob Seite Quicksort ab Abi 2017 nach Quicksort

2016-09-12T14:21:17Z

Akaibel verschob Seite Quicksort ab Abi 2017 nach Quicksort

← Nächstältere Version	Version vom 12. September 2016, 14:21 Uhr
(kein Unterschied)

Akaibel am 12. September 2016 um 14:20 Uhr

2016-09-12T14:20:55Z

← Nächstältere Version		Version vom 12. September 2016, 14:20 Uhr
Zeile 6:		Zeile 6:

	'''<font color='red'>im Zentralabitur nur relevant für den LK!</font>'''		'''<font color='red'>im Zentralabitur nur relevant für den LK!</font>'''


			<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>

	=Prinzip=		=Prinzip=
	Quicksort arbeitet nach dem '''Divide-and-Conquer-Prinzip''':		Quicksort arbeitet nach dem '''Divide-and-Conquer-Prinzip''':

Mgrifka: /* für Listen */

2016-08-09T08:26:08Z

für Listen

← Nächstältere Version		Version vom 9. August 2016, 08:26 Uhr
Zeile 54:		Zeile 54:
	}		}
	List<Person> kleinerSortiert = quicksort(kleiner);		List<Person> kleinerSortiert = quicksort(kleiner);
	List<~~person~~> groesserSortiert = quicksort(groesser);		List<Person> groesserSortiert = quicksort(groesser);

	List<Person> ergebnis = new ListWithViewer<>();		List<Person> ergebnis = new ListWithViewer<>();

Mgrifka: Die Seite wurde neu angelegt: „428px Kategorie:Sortierverfahren Kategorie:Informatik-Q1 [[Kategorie:Informatik-Abi…“

2016-08-09T08:25:53Z

Die Seite wurde neu angelegt: „thumb|Quicksort für das Wort "informatik" |428px Kategorie:Sortierverfahren Kategorie:Informatik-Q1 [[Kategorie:Informatik-Abi…“

Neue Seite

[[File:Quicksort.png|thumb|Quicksort für das Wort "informatik" |428px]]

[[Kategorie:Sortierverfahren]]
[[Kategorie:Informatik-Q1]]
[[Kategorie:Informatik-Abitur]]

'''im Zentralabitur nur relevant für den LK!'''
=Prinzip=
Quicksort arbeitet nach dem '''Divide-and-Conquer-Prinzip''':

Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt (='''Divide'''). Dazu wählt Quicksort ein sogenanntes '''Pivotelement''' aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.

Anschließend wird jede Teilliste in sich sortiert. Dazu wird der Quicksort-Algorithmus '''rekursiv''' auf der linken und auf der rechten Teilliste ausgeführt. Wenn eine Teilliste leer ist, erfolgt der Abbruch der Rekursion, d. h. für diese Teilliste wird Quicksort nicht mehr aufgerufen.

Am Ende werden die beiden Teillisten und das Pivot-Element zusammengeführt (='''Conquer''').

=Laufzeit=
Quicksort hat im '''Average Case''' die Laufzeit '''O(n*log(n))'''.
Im '''Worst Case''' steigt die Laufzeit auf '''O(n2)'''. 
Da der Worst Case nur für Listen (bzw. Arrays) eintritt, die schon sortiert sind, kann man den Worst Case ganz einfach vermeiden: Man muss vor dem Aufruf von Quicksort die Elemente mischen!

Quicksort ist das schnellste vergleichsbasierte Sortierverfahren. Das liegt daran, dass es für Arrays '''in situ''' sortiert, d.h. es müssen keine neuen Datenstrukturen erzeugt werden. Das ist der entscheidende Vorteil von Quicksort gegenüber [[Mergesort ab Abi 2017|Mergesort]].

=Implementierung=

== für Listen ==
Quicksort-Implementierung für eine Liste (vgl. Schnittstellenbeschreibung Zentralabitur), die mit Objekten vom Typ Person gefüllt ist.

Diese Implementierung ist einfacher als die [[Array|Array]]-Implementierung, dafür aber nicht so schnell, denn man muss ständig neue Listen erzeugen.

<code>
public List<Person> quicksort(List<Person> pList){
if(pList.isEmpty()){
return pList;
}
pList.toFirst();
Person pivot = pList.getContent();
pList.next();
if(!pList.hasAccess()){
return pList;
}
List<Person> kleiner = new List<>();
List<Person> groesser = new List<>();
while(pList.hasAccess()){
Person aktuell = pList.getContent();
if(aktuell.getEinkommen() < pivot.getEinkommen()){
kleiner.append(aktuell);
}
else{
groesser.append(aktuell);
}
pList.next();
}
List<Person> kleinerSortiert = quicksort(kleiner);
List<person> groesserSortiert = quicksort(groesser);

List<Person> ergebnis = new ListWithViewer<>();
ergebnis.concat(kleinerSortiert);
ergebnis.append(pivot);
ergebnis.concat(groesserSortiert);
return ergebnis;
}
</code>

== für Arrays ==
Auf Arrays ist Quicksort schneller, weil man "in situ" sortiert, d.h. es werden keine Teilarrays o.ä. erzeugt.

Dafür ist diese Implementierung komplizierter.

<code>
//Rahmenmethode
public void quicksort(Person[] personen){
quicksort(personen, 0, personen.length-1);
}

// rekursive Methode
private void quicksort(Person[] personen, int start, int ende){
if(start == ende){
return;
}
if(start + 1 == ende){
if(personen[start].istAlphabetischNach(personen[ende])){
tausche(personen, start, ende);
return;
}
}
Person pivot = personen[start];
int vomStart = start+1;
int vomEnde = ende;
while(vomStart < vomEnde){
while(vomStart < vomEnde && personen[vomStart].istAlphabetischNach(pivot) == false){
vomStart++;
}
while(vomStart < vomEnde && personen[vomEnde].istAlphabetischNach(pivot)){
vomEnde--;
}
tausche(personen, vomStart, vomEnde);
}
// pivot-Element in die Mitte bringen
tausche(personen, start, vomStart-1);
if(start < vomStart-1){
quicksort(personen, start, vomStart-1);
}
if(vomStart < ende){
quicksort(personen, vomStart, ende);
}
return;
}
</code>