Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- q1:java-sortierverfahrenquicksort [2017/07/11 08:54] – admin03
+++ q1:java-sortierverfahrenquicksort [2017/07/11 09:07] (aktuell) – [Quicksort] admin03
@@ Zeile 31: / Zeile 31: @@
 ^02|:::^08|:::^49|:::^51|:::^66|:::^67|:::^79|:::^85|:::^92|:::^95^
+**
+Laufzeitverhalten von Quicksort:**
+Im Idealfall wird jedes Teilfeld wieder in der Mitte geteilt (dem kommt man besonders nahe, wenn das Vergleichselement nicht sehr groß bzw. sehr klein, eben "mittel", war).
+Betrachten wir jeweils alle Teilfelder auf einer Zerlegungsstufe gemeinsam, so haben wir $n$ Vergleiche (denn jedes Element wird ja einem Vergleich unterzogen) und im Durchschnitt $\frac{1}{4}\cdot n$.Tauschoperationen (im ungünstigsten Fall $\frac{1}{2}\cdot n$ , im günstigsten Fall keine Vertauschungen).
+Zusammen ergibt dies $\frac{5}{4}\cdot n$  Operationen pro Zerlegungsstufe.
+Bei idealer Zerlegung muss für die Anzahl $k$ der Zerlegungsstufen gelten: $2^k=n$  (denn jedes Teilfeld wird ja stets halbiert), d.h. $k=\log_2(n)$ .
+Also ist das Laufzeitverhalten im Idealfall:
+$$k\cdot \frac{5}{4} \cdot n = \log_2(n) \cdot \frac{5}{4} \cdot n = \frac{5}{4}\cdot n \cdot \log_2(n) \sim n \cdot \log(n)$$
+(da die Logarithmen zu verschiedenen Basen sich nur durch einen konstanten Faktor unterscheiden, wird keine explizite Basis mehr angegeben).
+Der **ungünstigste Fall** entsteht, wenn jeweils nur ein 1-Teilfeld abgespaltet wird. Man erhält dann $k=n$ Zerlegungsstufen und damit $$n\cdot \frac{5}{4} \cdot n = \frac{5}{4} \cdot n^2 \sim n^2$$ Operationen, das Laufzeitverhalten des Sortierverfahrens ist dann quadratisch. Dieser ungünstigste Fall wird erreicht, wenn das Vergleichselement jeweils das größte oder kleinste Element im Teilfeld ist.
+====== Aufgaben ======
+===== Aufgabe 1 =====
+Sortiere den Notenspiegel mit Quicksort.
+ <html>
+<table>
+  <tr>
+    <th>0</th>
+    <th>1</th>
+    <th>2</th>
+    <th>3</th>
+    <th>4</th>
+    <th>5</th>
+    <th>6</th>
+    <th>7</th>
+    <th>8</th>
+    <th>9</th>
+    <th>10</th>
+    <th>11</th>
+    <th>12</th>
+    <th>13</th>
+    <th>14</th>
+    <th>15</th>
+  </tr>
+  <tr>
+    <td>13</td>
+    <td>8</td>
+    <td>6</td>
+    <td>8</td>
+    <td>10</td>
+    <td>16</td>
+    <td>11</td>
+    <td>9</td>
+    <td>9</td>
+    <td>13</td>
+    <td>12</td>
+    <td>10</td>
+    <td>7</td>
+    <td>6</td>
+    <td>5</td>
+    <td>2</td>
+  </tr>
+</table>
+</html>
+===== Aufgabe 2=====
+Sortiere das Feld
+^Igel^Baer^Lama^Tiger^Gnu^Affe^Schwein^Zebra^Esel^Maus^
+mit Quicksort
+===== Aufgabe 3 =====
+Sortiere das Zahlenfeld
+^456	^734	^829	^145^	788	^541^	901	^669^	291^595^	803^	101	^689	^472^
+mit Quicksort
+===== Aufgabe 4 =====
+Überlege, ob das Vergleichselement eines der Feldelemente sein muss.
+===== Aufgabe 5 =====
+Es gibt eine Verbesserung von Quicksort, bei der man als Kandidaten für das Vergleichselement das ganz links, das ganz rechts und das in der Mitte in Erwägung zieht. Welches sollte man nehmen? Wann bringt diese Abänderung Vorteile?