Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- q1:java-sortierverfahrenquicksort [2017/07/11 08:52] – admin03
+++ q1:java-sortierverfahrenquicksort [2017/07/11 09:07] (aktuell) – [Quicksort] admin03
@@ Zeile 22: / Zeile 22: @@
 Die nächsten Schritte geben wir nur noch grafisch an. Das Vergleichselement wird kursiv fett gekennzeichnet. Wir geben jeweils die Zerlegung aller Teilfelder in einer Zeile an, auch wenn es in der Praxis so ist, dass das am weitesten links gelegene Teilfeld zuerst vollständig zerlegt wird.
-^08^02|:::49^51^66^67|:::79|:::92^85^95^
+^08^02|:::49^51^66^67|:::^79|:::^92^85^95^
+Hier sieht man noch folgenden Sonderfall im zweiten Teilfeld: bleiben beide Zeiger auf demselben Element stehen (das kann nur das Vergleichselement sein), kann man das Vergleichselement unmittelbar als Einser-Feld abtrennen.
+^02|:::^08|:::^49|:::^51|:::^66^67|:::^79|:::^85|:::^92^95^
+^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?