Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- q1:java-sortierverfahrenquicksort [2017/07/11 08:58] – admin03
+++ q1:java-sortierverfahrenquicksort [2017/07/11 09:07] (aktuell) – [Quicksort] admin03
@@ Zeile 41: / Zeile 41: @@
 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_2(n)$$
+$$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?