 Quicksort |
|
|
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 |
|
__________________
Syntax Highlighting fürs Board (Link)
|
|
29.03.2016 09:45 |
|
|
woody56
Grünschnabel
Dabei seit: 28.03.2016
Beiträge: 3
 |
|
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
|
|
|
29.03.2016 12:28 |
|
|
|
|
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 |
|
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
29.03.2016 14:28 |
|
|
woody56
Grünschnabel
Dabei seit: 28.03.2016
Beiträge: 3
|
|
Jetzt passt es aber! Vielen Dank für deine Hilfe und Mühe! 
|
|
|
29.03.2016 16:40 |
|
|
|
