Tilman
59 lines
4.4 KiB
PHP
59 lines
4.4 KiB
PHP
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
|
|
<link rel="stylesheet" type="text/css" media="all" href="stylesheet.css">
|
|
<title>Sortieralgortihmen</title>
|
|
</head>
|
|
<body>
|
|
<span id="menu"><a href="index.php">zurück zur Liste</a></span>
|
|
|
|
<div id="buttons">
|
|
<form action="edit.php" method="POST">
|
|
<input type="hidden" name="filename" value="<?php echo $_SERVER['SCRIPT_FILENAME']?>">
|
|
<p>
|
|
<input type="submit" value="Seite bearbeiten">
|
|
</p>
|
|
</form>
|
|
</div>
|
|
|
|
<h1>Sortieralgorithmen</h1>
|
|
|
|
<h3>Quicksort</h3>
|
|
Der Quicksort-Algortithmus ist eines der schnellsten und zugleich einfachsten Sortierverfahren. Es arbeitet nach dem Divide-and-Conquer-Prinzip.<br>
|
|
Es wird zunächst ein <b>Pivotelement</b> ausgewählt und die Liste in zwei geteilt. Die Elemente, die kleiner als das Pivotelement sind, kommen in die erste Liste und die anderen in die zweite. Mit den entstehenden Listen wird genauso fortgefahren, bis es nur noch Teillisten der Länge 1 gibt. Diese Listen werden nun der Reihe nach wieder zusammengefügt.<br><br>
|
|
|
|
<h3>Mergesort</h3>
|
|
Ähnlich wie bei Quicksort beruht das Verfahren auf der Divide-and-Conquer-Strategie. Die zu sortierende Folge wird in zwei gleichgroße Hälften geteilt. Die entstehenden Listen werden weiter und weiter geteilt, bis es wieder nur noch Teillisten der Länge 1 gibt. Zusammengefügt wird, indem die ersten beiden Elemente zweier Teillisten verglichen werden, das kleinere gelöscht und in eine neue Liste eingetragen wird. Die neuen ersten beiden Elemente verglichen, das kleinere gelöscht und in die neue Liste eingetragen wird...<br><br>
|
|
|
|
<h3>Bubblesort</h3>
|
|
Bubblesort ist einer der simpelsten Sortieralgorithmen.<br>
|
|
Im ersten Durchlauf wird nach dem kleinsten Element gesucht, im zweiten Durchlauf nach dem zweitkleinsten usw.<br>
|
|
Man geht den Array immer von hinten nach vorne durch. Zunächst vergleicht man das letzte mit dem vorletzten Element. Ist das hintere kleiner, werden die beiden Elemente vertauscht. Dann wird mit dem vorletzten und dem vorvorletzten weitergemacht. Dadurch bleiben die größeren liegen und die kleineren Elemente werden nach vorne durchgereicht.<br><br>
|
|
|
|
<h3>Insertionsort</h3>
|
|
Man hat eine zu sortierende Folge a<sub>0</sub>, a<sub>1</sub>, ... , a<sub>n-1</sub>, wobei der erste Teil a<sub>0</sub>, a<sub>1</sub>, ... , a<sub>k-1</sub> bereits aufsteigend sortiert ist und der zweite Teil a<sub>k</sub>, a<sub>k+1</sub>, ... , a<sub>n-1</sub> noch unsortiert ist. Zu Anfang besteht der sortierte Teil nur aus a<sub>0</sub>, zum Schluss aus allen Elementen a<sub>0</sub>, a<sub>1</sub>, ... , a<sub>n-1</sub>.<br>
|
|
Das Element a<sub>k</sub> wird als nächstes in die bereits sortierte Liste eingefügt, indem es der Reihe nach mit a<sub>k-1</sub>, a<sub>k-2</sub> usw. verglichen wird. Sobald ein Element a<sub>j</sub> mit a<sub>j</sub>≤a<sub>k</sub> gefunden wird, wird es hinter dieses eingefügt. Wird kein solches Element gefunden, wird a<sub>k</sub> an den Anfang der Folge gesetzt.<br>
|
|
Damit ist der sortierte Teil um ein Element länger geworden. Im nächsten Schritt wird a<sub>k+1</sub> in den sortierten Teil eingefügt...
|
|
<br><br>
|
|
|
|
<h2>Vergleich Mergesort und Quicksort</h2>
|
|
von <a href="http://www.gm.fh-koeln.de/~ehses/ap/folien/folien9.pdf">http://www.gm.fh-koeln.de/~ehses/ap/folien/folien9.pdf</a>
|
|
<ul>
|
|
<li>Mergesort ist garantiert O(n log n), Quicksort im Mittel</li>
|
|
<li>Die Anzahl der Vergleich und der Datenbewegungen ist bei Mergesort n log2(n)</li>
|
|
<li>Quicksort hat im Mittel O(1.4 n log2 n) Vergleiche</li>
|
|
<li>Quicksort hat im Mittel O(0.7 n log2 n) Datenbewegungen</li>
|
|
<li>Quicksort ist schneller, wenn die Vergleiche schneller sind als die Datenbewegungen (einfache Datentypen)</li>
|
|
<li>Mergesort ist schneller, wenn die Vergleiche die Zeit dominieren (Objekte)</li>
|
|
<li>Es gibt Varianten von Mergesort für Felder und Listen (nicht rekursiv)</li>
|
|
</ul>
|
|
|
|
<h2>Links</h2>
|
|
zu Laufzeiten s.a.: <a href="o-notation.php">O-Notation</a><br>
|
|
<a href="http://www.sortieralgorithmen.de/index.html">www.sortieralgorithmen.de - mit klasse Applet</a>
|
|
<br>
|
|
<a href="http://www.vameo.de/uni/tutorium/toposort.pdf">Merkblatt zu topologisches Sortieren von Augustin</a>
|
|
|
|
</body>
|
|
</html> |