Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- algorithmen:algolektion03 [14.02.2011 16:13] – Frank Schiebel
+++ algorithmen:algolektion03 [09.11.2014 15:47] (aktuell) – Stefan Gaum
@@ Zeile 1: / Zeile 1: @@
-[[algorithmen:algolektion02|Algorithmen 2]]
+[[algorithmen:algolektion02|Lektion 3 - Übungen]]
-====== Sortieren ======
+====== Lektion 4 - Sortieren ======
-Allen klassischen Sortierverfahren liegt das folgende Modell zugrunde => vgl. Abbildung:
+Sortierverfahren sind von großer Bedeutung für die Informatik, siehe auch
+http://de.wikipedia.org/wiki/Sortierverfahren
+Vielen Sortierverfahren liegt das folgende Modell zugrunde => vgl. Abbildung:
   * zu Beginn liegt ein //**sortierter**// und ein //**unsortierter** Datenbereich// vor
   * beide Datenbereiche werden durch ein //**Grenzelement**// voneinander getrennt
@@ Zeile 27: / Zeile 30: @@
-===== Sortieren durch Auswahl (Selection Sort) =====
+===== Sortieren durch Auswahl (Selectionsort) =====
+[[http://de.wikipedia.org/wiki/Selectionsort|Selectionsort]] bei Wikipedia
 Beim Sortieren durch Auswahl wird das kleinste Element des unsortierten Bereichs gesucht, ausgewählt und schließlich mit dem Grenzelement vertauscht. Die Grenze wird anschließend um einen Schritt weitergeschoben, bis das Ende erreicht ist => vgl. Abbildung:
@@ Zeile 39: / Zeile 43: @@
 Im nachstehenden Struktogramm wird eine variable Anzahl von Elementen sortiert. Die Variablen **//kleinstes//** und //**grenze**// beschreiben dabei die //Position// des kleinsten Elementes bzw. des Grenzelementes, und NICHT das Element selber. Vorteil ist, dass sich so der Algorithmus auf verschiedene Datentypen (Zeichen, Zahlen, Buchstaben) anwenden lässt.
-{{:algorithmen:selectsort.jpg|}}
+{{:algorithmen:selectsort2.jpg|}}
+[[http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html|Animation für einen Selectionsort]]
 ===== Aufgaben =====
@@ Zeile 47: / Zeile 52: @@
   - Sortiere die Zahlen 7, 5, 3, 8, 4, 6, 1, 2, 9 auf einem Blatt Papier nach dem Auswahlverfahren.
-  - Setze den Algorithmus aus dem Struktogramm in ein PHP-Programm.
+  - Folge dem Struktogramm und programmiere einen code für diesen Sortieralgorithmus.
-  - Teste dein Programm, indem du ein Formular erstellst, welches als Eingabe eine durch Leerzeichen getrennte Liste von Zahlen entgegen nimmt und diese anschließend einmal //**unsortiert**//, einmal //**aufsteigend sortiert**// und einmal //**absteigend sortiert**// ausgibt.
+  - Gib den Mittelwert der Listenelemente aus.
+  - Wie viele Elemente sind größer bzw. kleiner als der Mittelwert?
-----
+[[algorithmen:algolektionl1|Lösungsvorschlag]]
-Zusatzaufgaben:
-  * Gib den Mittelwert der Listenelemente aus.
-  * Wie viele Elemente sind größer bzw. kleiner als der Mittelwert?
-----
-  * Erstelle einen Array $numbers mit den Elementen "2" "8" "25" "49" "76" "1231" "4232" "4234" "10000" "1238123"
-  * Schreibe ein php-Programm, welches eine beliebig eingegebene Zahl dem Array hinzufügt und anschließend zusammen mit den anderen Arrayelementen //**sortiert**// ausgibt.
-----
-für ganz Schnelle:
-  * Finde heraus, welche Laufzeit dein Sortier-Algorithmus für 5, 10, 20, 30, ..., 200, ... Elemente hat und formuliere eine Aussage über die Abhängigkeit der Laufzeit von der Anzahl der Listenelemente.
-===== Lösungsvorschlag =====
-<code php>
-  <form action="sortieren.php" method="POST">
-  <input type="text"  name="zahlen" />
-  <input type="submit" value="Do it!" />
-  </form>
-  <?php
-  $jetzt = microtime();
-  print $jetzt;
-  $zahlen = $_POST['zahlen'];
-  $einzelzahlen = explode(" ", $zahlen);
-  $anzahl = count($einzelzahlen);
-  //echo $anzahl;
-  //print_r($einzelzahlen);
-  // Alle "leeren" Elemente rauswerfen
-  $dieguten = array();
-  for( $i=0; $i<$anzahl; $i++) {
-      if( is_numeric($einzelzahlen[$i])){
-  	   print "Index $i: $einzelzahlen[$i] ist Zahl<br />";
-  	   $dieguten[] = $einzelzahlen[$i];
-      }
-  }
-  print_r($dieguten);
-  $anzahl = count($dieguten);
-  $grenze = 0;
-  while($grenze < $anzahl) {
-  	// kleinstes Element suchen
-  	$index_min = $grenze;
-  	for( $i = $grenze; $i<$anzahl; $i++) {
-  		if ($dieguten[$i] < $dieguten[$index_min]) {
-  			$index_min = $i;
-  		}
-  	}
-  	// $dieguten[$index_min] ist das kleinste Element#
-  	// vertausche $dieguten[$grenze] mit $dieguten[$index_min]
-  	$zwischen = $dieguten[$grenze];
-  	$dieguten[$grenze] = $dieguten[$index_min];
-  	$dieguten[$index_min] = $zwischen;
-  	// Grenze eins nach rechts
-  	$grenze++;
-  }
-  $zeit = microtime() - $jetzt;
-  print_r($dieguten);
-  print "dauer: $zeit";
+[[algorithmen:algolektion04|Lektion 5 - Pseudocode]]
-  ?>
-</code>
-[[algorithmen:algolektion04|Lektion 4]]