Informatiker Board | Druckvorschau: Quicksort

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Quicksort (http://www.informatikerboard.de/board/thread.php?threadid=2931)

Geschrieben von woody56 am 28.03.2016 um 22:28:

Quicksort

Hallo erstmal smile

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 unglücklich

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);
      }    
    }

Geschrieben von eulerscheZahl am 29.03.2016 um 09:45:

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

Geschrieben von woody56 am 29.03.2016 um 12:28:

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 unglücklich

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

Geschrieben von eulerscheZahl am 29.03.2016 um 14: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