| woody56 |
Quicksort
Hallo erstmal 
Ich habe eine Frage zum Quicksort. Wie lässt sich bei der Quicksort-Version mit dem mittlerem Pivotelement ein Worst-Case Beispiel problemlos erzeugen? Ich weiß, dass dabei das Pivotelement das größte oder das kleinste Element bei jedem Rekursionsaufruf sein muss. So ganz einfach lässt sich aber eine Feldbelegung dann doch nicht angeben 
Gibt's da vielleicht irgendwie ein Trick?
Es ist folgender Algorithmus:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
|
public void quicksort (int anfang, int ende)
{
int mitte, links, rechts;
int vergleich, hilf;
links=anfang; rechts=ende; mitte =(links + rechts)/2;
vergleich=zSortfeld[mitte];
do{
while (zSortfeld[links] < vergleich){
links++;
}
while (zSortfeld[rechts] > vergleich){
rechts--;
}
if (links <= rechts) {
hilf = zSortfeld[links];
zSortfeld[links]=zSortfeld[rechts];
zSortfeld[rechts]=hilf;
links++;
rechts--;
}
} while (links <=rechts);
if (anfang<rechts){
quicksort (anfang,rechts);
}
if (links<ende){
quicksort (links,ende);
}
}
|
|
|
| eulerscheZahl |
Dann stecke die kleinen Zahlen doch in die Mitte:
| code: |
1:
2:
|
quicksort(0, 15, new int[] { 15, 13, 11, 9, 7, 5, 3, 1, 2, 4, 6, 8, 10, 12, 14, 16 }); //14 Aufrufe nötig
quicksort(0, 15, new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }); //8 Aufrufe nötig |
|
|
| woody56 |
Danke für deine Antwort! Beim Worst Case sollte normalerweise ein Baum mit einem nur einem Zweig entstehen
also der Form: q(0,n-1), q(0,n-2),q(0,n-3), .... ,q(0, 1)
Bei der obigen Belegung kommt diese Form irgendwie nicht heraus
Auch das Pivotelement ist nicht immer das kleinste Element bei jedem Rekursionsaufruf z.B. bei q(2, 15), da ist es nämlich 13 obwohl da noch andere Elemente sich befinden, die kleiner bzw. größer sind |
| eulerscheZahl |
Es gibt 14 Aufrufe von quicksort. Das ist das maximal mögliche bei einer Länge von 15 - in jedem Schritt wird es nur ein Aufruf weniger.
Aber du hast Recht, dass die Intervalle nicht zwingend am Rand geteilt werden.
Ich habe mal per Programm nach dem worst case gesucht:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
|
public static void main(String[] args) {
for (int size = 3; size <= 10; size++)
combo(new boolean[size], new int[size], 0);
}
static void combo(boolean[] used, int[] nums, int index) {
if (index == used.length) {
if (quicksort(0, index - 1, Arrays.copyOf(nums, index), false))
{
System.out.println(Arrays.toString(nums));
quicksort(0, index - 1, Arrays.copyOf(nums, index), true);
}
return;
}
for (int i = 0; i < used.length; i++) {
if (!used[i]) {
used[i] = true;
nums[index] = i;
combo(used, nums, index + 1);
used[i] = false;
}
}
}
public static boolean quicksort(int anfang, int ende, int[] zSortfeld, boolean print)
{
int mitte, links, rechts;
int vergleich, hilf;
links = anfang;
rechts = ende;
mitte = (links + rechts) / 2;
vergleich = zSortfeld[mitte];
if (print)
System.out.println(anfang + " - " + ende + ": " + vergleich);
do {
while (zSortfeld[links] < vergleich) {
links++;
}
while (zSortfeld[rechts] > vergleich) {
rechts--;
}
if (links <= rechts) {
hilf = zSortfeld[links];
zSortfeld[links] = zSortfeld[rechts];
zSortfeld[rechts] = hilf;
links++;
rechts--;
}
} while (links <= rechts);
if (anfang < rechts) {
if (!quicksort(anfang, rechts, zSortfeld, print))
return false;
}
if (links < ende) {
if (!quicksort(links, ende, zSortfeld, print))
return false;
}
return vergleich == anfang;
} |
|
Ausgabe:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
|
[1, 0, 2]
0 - 2: 0
1 - 2: 1
[2, 0, 1, 3]
0 - 3: 0
1 - 3: 1
2 - 3: 2
[1, 3, 0, 2, 4]
0 - 4: 0
1 - 4: 1
2 - 4: 2
3 - 4: 3
[4, 2, 0, 1, 3, 5]
0 - 5: 0
1 - 5: 1
2 - 5: 2
3 - 5: 3
4 - 5: 4
[1, 5, 3, 0, 2, 4, 6]
0 - 6: 0
1 - 6: 1
2 - 6: 2
3 - 6: 3
4 - 6: 4
5 - 6: 5
[4, 2, 6, 0, 1, 3, 5, 7]
0 - 7: 0
1 - 7: 1
2 - 7: 2
3 - 7: 3
4 - 7: 4
5 - 7: 5
6 - 7: 6
[1, 5, 3, 7, 0, 2, 4, 6, 8]
0 - 8: 0
1 - 8: 1
2 - 8: 2
3 - 8: 3
4 - 8: 4
5 - 8: 5
6 - 8: 6
7 - 8: 7
[8, 2, 6, 4, 0, 1, 3, 5, 7, 9]
0 - 9: 0
1 - 9: 1
2 - 9: 2
3 - 9: 3
4 - 9: 4
5 - 9: 5
6 - 9: 6
7 - 9: 7
8 - 9: 8 |
|
|
| woody56 |
Jetzt passt es aber! Vielen Dank für deine Hilfe und Mühe! 
|
