Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Quicksort

No description
by

on 14 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Quicksort

Quicksort
Programmablaufplan
Erklärung des Systems
Ziel:
QuickSort => Schnelles Sortieren
Bessere Performance gegenüber anderen Algorithmen

Umsetzung:
Pivot-Element als Vergleichsmaßstab
Prinzip: "Teilen und Herrschen"
Trennen von größeren und kleineren Werten
Prinzip auf Teillisten anwenden durch Rekursion

Sortieren der Werte von x bis y
Die erste Zählervariable wird unter der Bedingung, dass der Wert an diesem Index nicht größer ist, als der Wert des Pivots, erhöht.
Die zweite Zählervariable wird solange reduziert, bis das Element an diesem Index kleiner ist, als das Pivot.
Diese beiden Werte werden getauscht und solange
a <= b ist läuft die Suche weiter.
Rekursion
Nachdem die Werte so sortiert wurden, dass sich links des Pivots kleinere und rechts des Pivots größerer Werte als der des Pivots befinden, wird eine der beiden Listen erneut in zwei keinere Unterteilt. Dabei sind die Start- und Endwerte dieser Listen abhängig von zwei Verzweigungen:
Rekursion (1)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Startwert und der Wert des zweiten Zählers (-> b teilt die Liste [nah Pivot])
Eingabe des Start- und Endwerts
Die Methode sortieren hat zwei Parameter, einen Start- und einen Endwert. Diese werden einerseits für die Initalisierung der beiden Zählervariablen benötigt und andererseits für Verzweigungen, die über die Rekursion entscheidet.
Festlegen des
Pivot-Elementes
Das Pivotelement dient als Vergleichselement. Es wird errechnet, in dem die Summe von Start- und Endwert durch zwei geteilt wird. Demnach befindet sich das Pivotelement IMMER in der Mitte der jeweiligen Liste. Der Wert dieses besonderen Elementes dient als Maßstab für das Sortieren.
Quicksort
Rekursion (2)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Wert des ersten Zählers(-> a = b+1) und der Endwert
Der erste Zähler ist
kleiner als der Endwert
Startwert ist kleiner
als zweiter Zähler
Inhaltsverzeichnis
Rekursion - Was bedeutet das?

Definition:
Eine Funktion ruft sich solange selbst
auf, bis die Laufzeitbedingung nicht
mehr erfüllt ist
Beispiel:
public void rekursion()
{
if(Laufzeitbedingung)
{
rekursion();
}
}
Umsetzung des Sortieralgorithmus'
1. Voraussetzungen

2. Eingabe der Parameter

3. Bestimmen des Pivotelementes

4. Sortieren (Finden&Tauschen)

5. Rekursion
Quellen:
Beispielablauf:
Eingegebene Werte für das Array mit der Länge 7:
Sortieren der Werte von x bis y
Die erste Zählervariable wird unter der Bedingung, dass der Wert an diesem Index nicht größer ist, als der Wert des Pivots, erhöht.
Die zweite Zählervariable wird solange reduziert, bis das Element an diesem Index kleiner ist, als das Pivot.
Diese beiden Werte werden getauscht und solange
a <= b ist läuft die Suche weiter.
Rekursion
Nachdem die Werte so sortiert wurden, dass sich links des Pivots kleinere und rechts des Pivots größerer Werte als der des Pivots befinden, wird eine der beiden Listen erneut in zwei keinere Unterteilt. Dabei sind die Start- und Endwerte dieser Listen abhängig von zwei Verzweigungen:
Rekursion (1)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Startwert und der Wert des zweiten Zählers (-> b teilt die Liste [nah Pivot])
Eingabe des Start- und Endwerts
Die Methode sortieren hat zwei Parameter, einen Start- und einen Endwert. Diese werden einerseits für die Initalisierung der beiden Zählervariablen benötigt und andererseits für Verzweigungen, die über die Rekursion entscheidet.
Festlegen des
Pivot-Elementes
Das Pivotelement dient als Vergleichselement. Es wird errechnet, in dem die Summe von Start- und Endwert durch zwei geteilt wird. Demnach befindet sich das Pivotelement IMMER in der Mitte der jeweiligen Liste. Der Wert dieses besonderen Elementes dient als Maßstab für das Sortieren.
Quicksort
Rekursion (2)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Wert des ersten Zählers(-> a = b+1) und der Endwert
Der erste Zähler ist
kleiner als der Endwert
Startwert ist kleiner
als zweiter Zähler
0
1
2
3
4
5
6
5
2
7
6
4
1
3
Wertebelegungen:
Variable
Wert
1. Starten der Methode sortieren:
pStart = O; pEnde = 6
(=>zArray.length-1)
2. Deklarieren und Initialisieren der zwei Zählervariablen a & b
mit den Eingabeparametern:
int a = pStart; int b = pEnde
int a
int b
int pStart
int pEnde
3. Bestimmen des Pivotelements:
pivotBestimmen(O,6); => (0+6)/2 = 3
0
1
2
3
4
5
6
5
2
7
6
4
1
3
= Erster Zähler (a)
= Zweiter Zähler (b)
= Pivotelement
int zStellePivot
double zWertPivot
4. a) Finden von Elementen an dem falschen Platz: links von Pivot < zWertPivot < rechts von Pivot:

4. b)Tauschen von den Elementen mit falschen Plätzen:
5. a) Rekursion von linker Seite nötig?
pStart < b? O < 2
true: sortieren(O,2);
5. b) Rekursion von rechter Seite nötig?
a < pEnde? 4 < 6
true: sortieren(4,6);
O
6
O
6
3
O
0
1
2
3
4
5
6
5
2
7
6
4
1
3
= Erster Zähler (a)
= Zweiter Zähler (b)
= Pivotelement
0
1
2
3
4
5
6
5
2
3
6
4
1
7
= Erster Zähler (a)
= Zweiter Zähler (b)
= Pivotelement
Wikipedia:
http://de.wikipedia.org/wiki/Quicksort
http://de.wikipedia.org/wiki/Rekursion
Youtube:
www.youtube.com/watch?v=ywWBy6J5gz8
www.youtube.com/watch?v=aXXWXz5rF64
www.youtube.com/watch?v=8hEyhs3OV1w
Bild auf 2. Folie:
http://www.linux-related.de/index.html?/coding/sort/sort_quick.htm
1. Erklärung des Systems

2. Programmablaufplan

3. Umsetzung des Projektes
->Beispiel
Beispielablauf:
Sortieren der Werte von x bis y
Die erste Zählervariable wird unter der Bedingung, dass der Wert an diesem Index nicht größer ist, als der Wert des Pivots, erhöht.
Die zweite Zählervariable wird solange reduziert, bis das Element an diesem Index kleiner ist, als das Pivot.
Diese beiden Werte werden getauscht und solange
a <= b ist läuft die Suche weiter.
Rekursion
Nachdem die Werte so sortiert wurden, dass sich links des Pivots kleinere und rechts des Pivots größerer Werte als der des Pivots befinden, wird eine der beiden Listen erneut in zwei keinere Unterteilt. Dabei sind die Start- und Endwerte dieser Listen abhängig von zwei Verzweigungen:
Rekursion (1)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Startwert und der Wert des zweiten Zählers (-> b teilt die Liste [nah Pivot])
Eingabe des Start- und Endwerts
Die Methode sortieren hat zwei Parameter, einen Start- und einen Endwert. Diese werden einerseits für die Initalisierung der beiden Zählervariablen benötigt und andererseits für Verzweigungen, die über die Rekursion entscheidet.
Festlegen des
Pivot-Elementes
Das Pivotelement dient als Vergleichselement. Es wird errechnet, in dem die Summe von Start- und Endwert durch zwei geteilt wird. Demnach befindet sich das Pivotelement IMMER in der Mitte der jeweiligen Liste. Der Wert dieses besonderen Elementes dient als Maßstab für das Sortieren.
Quicksort
Rekursion (2)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Wert des ersten Zählers(-> a = b+1) und der Endwert
Der erste Zähler ist
kleiner als der Endwert
Startwert ist kleiner
als zweiter Zähler
0
1
2
2
3
1
Wertebelegungen:
Variable
Wert
1. Starten der Methode sortieren:
pStart = O; pEnde = 2
2. Deklarieren und Initialisieren der zwei Zählervariablen a & b
mit den Eingabeparametern:
int a = pStart; int b = pEnde
int a
int b
int pStart
int pEnde
3. Bestimmen des Pivotelements:
pivotBestimmen(O,2); => (0+2)/2 = 1
int zStellePivot
double zWertPivot
4. a) Finden von Elementen an dem falschen Platz: links von Pivot < zWertPivot < rechts von Pivot:

4. b)Tauschen von den Elementen mit falschen Plätzen:
5. a) Rekursion von linker Seite nötig?
pStart < b? O < 0
false
5. b) Rekursion von rechter Seite nötig?
a < pEnde? 1< 2
true: sortieren(1,2);
O
2
O
2
1
1
Programmablauf
0
1
2
2
3
1
Umsetzung
Beispiel
0
1
2
2
3
1
0
1
2
2
3
1
Sortieren der Werte von x bis y
Die erste Zählervariable wird unter der Bedingung, dass der Wert an diesem Index nicht größer ist, als der Wert des Pivots, erhöht.
Die zweite Zählervariable wird solange reduziert, bis das Element an diesem Index kleiner ist, als das Pivot.
Diese beiden Werte werden getauscht und solange
a <= b ist läuft die Suche weiter.
Rekursion
Nachdem die Werte so sortiert wurden, dass sich links des Pivots kleinere und rechts des Pivots größerer Werte als der des Pivots befinden, wird eine der beiden Listen erneut in zwei keinere Unterteilt. Dabei sind die Start- und Endwerte dieser Listen abhängig von zwei Verzweigungen:
Rekursion (1)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Startwert und der Wert des zweiten Zählers (-> b teilt die Liste [nah Pivot])
Eingabe des Start- und Endwerts
Die Methode sortieren hat zwei Parameter, einen Start- und einen Endwert. Diese werden einerseits für die Initalisierung der beiden Zählervariablen benötigt und andererseits für Verzweigungen, die über die Rekursion entscheidet.
Festlegen des
Pivot-Elementes
Das Pivotelement dient als Vergleichselement. Es wird errechnet, in dem die Summe von Start- und Endwert durch zwei geteilt wird. Demnach befindet sich das Pivotelement IMMER in der Mitte der jeweiligen Liste. Der Wert dieses besonderen Elementes dient als Maßstab für das Sortieren.
Quicksort
Rekursion (2)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Wert des ersten Zählers(-> a = b+1) und der Endwert
Der erste Zähler ist
kleiner als der Endwert
Startwert ist kleiner
als zweiter Zähler
Wertebelegungen:
Variable
Wert
1. Starten der Methode sortieren:
pStart = 4; pEnde = 6
2. Deklarieren und Initialisieren der zwei Zählervariablen a & b
mit den Eingabeparametern:
int a = pStart; int b = pEnde
int a
int b
int pStart
int pEnde
3. Bestimmen des Pivotelements:
pivotBestimmen(4,6); => (4+6)/2 = 5
int zStellePivot
double zWertPivot
4. a) Finden von Elementen an dem falschen Platz: links von Pivot <= zWertPivot <= rechts von Pivot:

4. b)Tauschen von den Elementen mit falschen Plätzen:
5. a) Rekursion von linker Seite nötig?
pStart < b? 4< 4
false
5. b) Rekursion von rechter Seite nötig?
a < pEnde? 5< 6
true: sortieren(5,6);
4
6
4
6
5
5
Sortieren der Werte von x bis y
Die erste Zählervariable wird unter der Bedingung, dass der Wert an diesem Index nicht größer ist, als der Wert des Pivots, erhöht.
Die zweite Zählervariable wird solange reduziert, bis das Element an diesem Index kleiner ist, als das Pivot.
Diese beiden Werte werden getauscht und solange
a <= b ist läuft die Suche weiter.
Rekursion
Nachdem die Werte so sortiert wurden, dass sich links des Pivots kleinere und rechts des Pivots größerer Werte als der des Pivots befinden, wird eine der beiden Listen erneut in zwei keinere Unterteilt. Dabei sind die Start- und Endwerte dieser Listen abhängig von zwei Verzweigungen:
Rekursion (1)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Startwert und der Wert des zweiten Zählers (-> b teilt die Liste [nah Pivot])
Eingabe des Start- und Endwerts
Die Methode sortieren hat zwei Parameter, einen Start- und einen Endwert. Diese werden einerseits für die Initalisierung der beiden Zählervariablen benötigt und andererseits für Verzweigungen, die über die Rekursion entscheidet.
Festlegen des
Pivot-Elementes
Das Pivotelement dient als Vergleichselement. Es wird errechnet, in dem die Summe von Start- und Endwert durch zwei geteilt wird. Demnach befindet sich das Pivotelement IMMER in der Mitte der jeweiligen Liste. Der Wert dieses besonderen Elementes dient als Maßstab für das Sortieren.
Quicksort
Rekursion (2)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Wert des ersten Zählers(-> a = b+1) und der Endwert
Der erste Zähler ist
kleiner als der Endwert
Startwert ist kleiner
als zweiter Zähler
Wertebelegungen:
Variable
Wert
1. Starten der Methode sortieren:
pStart = 5; pEnde = 6
2. Deklarieren und Initialisieren der zwei Zählervariablen a & b
mit den Eingabeparametern:
int a = pStart; int b = pEnde
int a
int b
int pStart
int pEnde
3. Bestimmen des Pivotelements:
pivotBestimmen(5,6); => (5+6)/2 = 5
int zStellePivot
double zWertPivot
4. a) Finden von Elementen an dem falschen Platz: links von Pivot <= zWertPivot <= rechts von Pivot:

4. b)Tauschen von den Elementen mit falschen Plätzen:
5. a) Rekursion von linker Seite nötig?
pStart < b? 5< 4
false
5. b) Rekursion von rechter Seite nötig?
a < pEnde? 6< 6
false
5
6
5
6
5
6
Sortieren der Werte von x bis y
Die erste Zählervariable wird unter der Bedingung, dass der Wert an diesem Index nicht größer ist, als der Wert des Pivots, erhöht.
Die zweite Zählervariable wird solange reduziert, bis das Element an diesem Index kleiner ist, als das Pivot.
Diese beiden Werte werden getauscht und solange
a <= b ist läuft die Suche weiter.
Rekursion
Nachdem die Werte so sortiert wurden, dass sich links des Pivots kleinere und rechts des Pivots größerer Werte als der des Pivots befinden, wird eine der beiden Listen erneut in zwei keinere Unterteilt. Dabei sind die Start- und Endwerte dieser Listen abhängig von zwei Verzweigungen:
Rekursion (1)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Startwert und der Wert des zweiten Zählers (-> b teilt die Liste [nah Pivot])
Eingabe des Start- und Endwerts
Die Methode sortieren hat zwei Parameter, einen Start- und einen Endwert. Diese werden einerseits für die Initalisierung der beiden Zählervariablen benötigt und andererseits für Verzweigungen, die über die Rekursion entscheidet.
Festlegen des
Pivot-Elementes
Das Pivotelement dient als Vergleichselement. Es wird errechnet, in dem die Summe von Start- und Endwert durch zwei geteilt wird. Demnach befindet sich das Pivotelement IMMER in der Mitte der jeweiligen Liste. Der Wert dieses besonderen Elementes dient als Maßstab für das Sortieren.
Quicksort
Rekursion (2)
Die Methode wird erneut aufgerufen, jedoch werden folgende Werte übergeben:
Der Wert des ersten Zählers(-> a = b+1) und der Endwert
Der erste Zähler ist
kleiner als der Endwert
Startwert ist kleiner
als zweiter Zähler
1
Wertebelegungen:
Variable
Wert
1. Starten der Methode sortieren:
pStart = 1; pEnde = 2
2. Deklarieren und Initialisieren der zwei Zählervariablen a & b
mit den Eingabeparametern:
int a = pStart; int b = pEnde
int a
int b
int pStart
int pEnde
3. Bestimmen des Pivotelements:
pivotBestimmen(O,2); => (1+2)/2 = 2
int zStellePivot
double zWertPivot
4. a) Finden von Elementen an dem falschen Platz: links von Pivot < zWertPivot < rechts von Pivot:

4. b)Tauschen von den Elementen mit falschen Plätzen:
5. a) Rekursion von linker Seite nötig?
pStart < b? O < -1
false
5. b) Rekursion von rechter Seite nötig?
a < pEnde? 2< 2
false
1
2
1
2
1
2
2
3
2
1
2
3
2
1
2
3
2
4
5
6
5
6
7
4
5
6
5
6
7
4
5
6
5
6
7
5
6
6
7
5
6
6
7
5
6
6
7
5
6
6
7
Full transcript