Sortieren - Versionsgeschichte

Kristin: /* Heapsort */

2017-01-18T17:37:08Z

‎Heapsort

Kristin: /* Sortieralgoritmen */

2016-11-30T14:47:43Z

‎Sortieralgoritmen

Kristin am 4. August 2016 um 15:42 Uhr

2016-08-04T15:42:07Z

Kristin: /* Mergesort */

2016-08-04T15:29:28Z

‎Mergesort

Marius: /* Mergesort */

2016-07-31T12:59:23Z

‎Mergesort

Marius: /* Mergesort */

2016-07-31T12:58:11Z

‎Mergesort

Marius: /* Mergesort */

2016-07-31T12:57:35Z

‎Mergesort

Kristin: "Feld" -> "Array"

2016-06-26T23:14:58Z

"Feld" -> "Array"

Marius: /* Insertionsort */

2016-06-25T16:03:51Z

‎Insertionsort

Marius: /* Insertionsort */

2016-06-25T16:03:39Z

‎Insertionsort

← Nächstältere Version		Version vom 18. Januar 2017, 17:37 Uhr
Zeile 52:		Zeile 52:


−	Im '''Heapsort''' wird sich die Eigenschaft zu Nutze gemacht, dass in einem korrekten [[Heap]] das kleinste Element immer in der Wurzel des Heaps steht. ~~Wird~~ dieses entfernt und im neuen Baum die ~~Heapstruktur~~ wiederhergestellt, lässt sich das Array sortieren. Das Wiederherstellen eines Heaps geht relativ schnell.	+	Im '''Heapsort''' wird sich die Eigenschaft zu Nutze gemacht, dass in einem korrekten [[Heap]] das kleinste Element immer in der Wurzel des Heaps steht. Werden dieses wiederholt entfernt und im jeweils neuen Baum die Heap-Eigenschaften wiederhergestellt, lässt sich das [[Array]] sortieren. Das Wiederherstellen eines Heaps geht relativ schnell.

	<source lang="java">		<source lang="java">

@@ Zeile 1: / Zeile 1: @@
 Das '''Sortieren''' ist ein Standardproblem der Informatik.
-=Sortieralgoritmen=
+=Sortieralgorithmen=
 ==Bubblesort==

@@ Zeile 5: / Zeile 5: @@
 ==Bubblesort==
-Das '''Bubblesort'''-Sortierverfahren versucht in jeder Iteration das größte Element an das Ende des [[Arrays]] zu bewegen. Somit besteht das Ende des Arrays immer aus einem sortierten Teilfeld. Nach '''n''' Durchläufen ist damit das Array vollständig sortiert. Bei diesem Verfahren wird in jedem Schritt jedes Element mindestens ein Mal mit einem anderen verglichen.
+Das '''Bubblesort'''-Sortierverfahren versucht in jeder Iteration das größte Element an das Ende des [[Arrays]] zu bewegen. Daher besteht das Ende des Arrays immer aus einem sortierten Teilfeld. Nach '''n''' Durchläufen ist das Array vollständig sortiert.
 <source lang="java">
@@ Zeile 106: / Zeile 108: @@
 ==Insertionsort==
-Beim '''Insertionsort''' (Einfügesortieren) wird versucht, ein Element in der passenden Stelle eines bereits sortierten Teilfeldes ''einzufügen'' und den Rest des Arrays dabei zu "verschieben". Da dieses Verfahren bei Arrays viel Aufwand während der Verschiebung erfordert, bieten sich [[Liste]]n zur Implementierung hier besser an. Damit kann das Einfügen an eine gewisse Position viel einfacher erfolgen.
+Beim '''Insertionsort''' (Einfügesortieren) wird versucht, ein Element in der passenden Stelle eines bereits sortierten Teilfeldes ''einzufügen'' und den Rest des Arrays dabei zu "verschieben".
 <source lang="java">
@@ Zeile 151: / Zeile 155: @@
 ==Mergesort==
-Der '''Mergesort''' ist das klassische Beispiel eines [[Teile und herrsche]]-Algorithmus. Das eingegebene Array wird hierbei solange in zwei Hälften geteilt, bis jedes Teilarray nur noch eine einzige Zahl enthält. Danach werden die Teilarrays Schritt für Schritt wieder zusammengesetzt und dabei sortiert, bis am Ende ein einziges sortiertes Array vorhanden ist.
+Der '''Mergesort''' ist das klassische Beispiel eines [[Teile und herrsche]]-Algorithmus. Das eingegebene Array wird hierbei solange in zwei Hälften geteilt, bis jedes Teilarray nur noch eine einzige Zahl enthält. Danach werden die Teilarrays Schritt für Schritt wieder zusammengesetzt und dabei sortiert, bis am Ende ein einzelnes sortiertes Array vorhanden ist.
@@ Zeile 239: / Zeile 243: @@
 ==Quicksort==
-'''Quicksort''' ist das zweite übliche Beispiel für '''Teile und Herrsche-Sortieralgorithmen'''. In ihm wird anhand eines arbiträr (willkürlich) gewählten Wertes (meistens das mittlere) das Array vorsortiert: Alle Elemente kleiner als das gewählte Element werden links davon einsortiert, alle größeren rechts davon. Damit hat man zwei Teilarrays, die selbst nicht sortiert sind. Also wird rekursiv nach demselben Muster vorgegangen: Die beiden kleineren Teilarrays werden wieder arbiträr nach einem Element aufgeteilt und in zwei grob sortierte Teilstrukturen aufgeteilt. Dies geschieht so lange, bis das Array in Teilarrays der Größe 1 aufgeteilt wurde. Diese sind alle sortiert, somit auch die größeren Teilarrays und damit das gesamte Array.
+'''Quicksort''' ist das zweite übliche Beispiel für '''Teile und Herrsche-Sortieralgorithmen'''. In ihm wird anhand eines arbiträr (willkürlich) gewählten Wertes (meistens das mittlere) das Array vorsortiert: Alle Elemente kleiner als das gewählte Element werden links davon einsortiert, alle größeren rechts davon. Damit hat man zwei Teilarrays, die selbst nicht sortiert sind. Also wird [[Rekursion|rekursiv]] nach dem gleichen Muster vorgegangen: Die beiden kleineren Teilarrays werden wieder arbiträr nach einem Element aufgeteilt und in zwei grob sortierte Teilstrukturen aufgeteilt. Dies geschieht so lange, bis das Array in Teilarrays der Größe 1 aufgeteilt wurde. Diese sind alle sortiert, somit auch die größeren Teilarrays und damit das gesamte Array.
 <source lang="java">

← Nächstältere Version		Version vom 4. August 2016, 15:29 Uhr
Zeile 151:		Zeile 151:
	==Mergesort==		==Mergesort==

−	Mergesort ist das klassische Beispiel eines [[Teile und herrsche]]-Algorithmus. Das eingegebene Array wird hierbei solange in zwei Hälften geteilt, bis jedes Teilarray nur noch eine Zahl enthält. Danach werden die Teilarrays wieder zusammengesetzt~~. Dabei wird bei der Zusammensetzung so~~ sortiert, ~~dass~~ am Ende ~~nur noch~~ ein sortiertes Array vorhanden ist.	+	Der '''Mergesort''' ist das klassische Beispiel eines [[Teile und herrsche]]-Algorithmus. Das eingegebene Array wird hierbei solange in zwei Hälften geteilt, bis jedes Teilarray nur noch eine einzige Zahl enthält. Danach werden die Teilarrays Schritt für Schritt wieder zusammengesetzt und dabei sortiert, bis am Ende ein einziges sortiertes Array vorhanden ist.

@@ Zeile 222: / Zeile 222: @@
 </source>
-Beispiel:
+ Beispiel:
 ==Quicksort==

← Nächstältere Version		Version vom 31. Juli 2016, 12:58 Uhr
Zeile 221:		Zeile 221:

	</source>		</source>
		+
		+	Beispiel:

	==Quicksort==		==Quicksort==

@@ Zeile 151: / Zeile 151: @@
 ==Mergesort==
-Mergesort ist das klassische Beispiel eines [[Teile und herrsche]]-Algorithmus.
+Mergesort ist das klassische Beispiel eines [[Teile und herrsche]]-Algorithmus. Das eingegebene Array wird hierbei solange in zwei Hälften geteilt, bis jedes Teilarray nur noch eine Zahl enthält. Danach werden die Teilarrays wieder zusammengesetzt. Dabei wird bei der Zusammensetzung so sortiert, dass am Ende nur noch ein sortiertes Array vorhanden ist.
 <source lang="java">

@@ Zeile 123: / Zeile 123: @@
   Beispiel:
-−
   ''[5, 4, 1, 8, 0, 2, 6, 9, 7, 3]''

@@ Zeile 125: / Zeile 125: @@
   ''[5, 4, 1, 8, 0, 2, 6, 9, 7, 3]''
-−
-  ['''4''', '''5''', 1, 8, 0, 2, 6, 9, 7, 3]
+  [<span style="color:red>'''4'''</span>, <span style="color:red>'''5'''</span>, 1, 8, 0, 2, 6, 9, 7, 3]
-  ['''1''', 5, '''4''', 8, 0, 2, 6, 9, 7, 3]
+  [<span style="color:red>'''1'''</span>, 5, <span style="color:red>'''4'''</span>, 8, 0, 2, 6, 9, 7, 3]
-  ['''0''', 5, 4, 8, '''1''', 2, 6, 9, 7, 3]
+  [<span style="color:red>'''0'''</span>, 5, 4, 8, <span style="color:red>'''1'''</span>, 2, 6, 9, 7, 3]
-  [0, '''4''', '''5''', 8, 1, 2, 6, 9, 7, 3]
+  [0, <span style="color:red>'''4'''</span>, <span style="color:red>'''5'''</span>, 8, 1, 2, 6, 9, 7, 3]
-  [0, '''1''', 5, 8, '''4''', 2, 6, 9, 7, 3]
+  [0, <span style="color:red>'''1'''</span>, 5, 8, <span style="color:red>'''4'''</span>, 2, 6, 9, 7, 3]
-  [0, 1, '''4''', 8, '''5''', 2, 6, 9, 7, 3]
+  [0, 1, <span style="color:red>'''4'''</span>, 8, <span style="color:red>'''5'''</span>, 2, 6, 9, 7, 3]
-  [0, 1, '''2''', 8, 5, '''4''', 6, 9, 7, 3]
+  [0, 1, <span style="color:red>'''2'''</span>, 8, 5, <span style="color:red>'''4'''</span>, 6, 9, 7, 3]
-  [0, 1, 2, '''5''', '''8''', 4, 6, 9, 7, 3]
+  [0, 1, 2, <span style="color:red>'''5'''</span>, <span style="color:red>'''8'''</span>, 4, 6, 9, 7, 3]
-  [0, 1, 2, '''4''', 8, '''5''', 6, 9, 7, 3]
+  [0, 1, 2, <span style="color:red>'''4'''</span>, 8, <span style="color:red>'''5'''</span>, 6, 9, 7, 3]
-  [0, 1, 2, '''3''', 8, 5, 6, 9, 7, '''4''']
+  [0, 1, 2, <span style="color:red>'''3'''</span>, 8, 5, 6, 9, 7, <span style="color:red>'''4'''</span>]
-  [0, 1, 2, 3, '''5''', '''8''', 6, 9, 7, 4]
+  [0, 1, 2, 3, <span style="color:red>'''5'''</span>, <span style="color:red>'''8'''</span>, 6, 9, 7, 4]
-  [0, 1, 2, 3, '''4''', 8, 6, 9, 7, '''5''']
+  [0, 1, 2, 3, <span style="color:red>'''4'''</span>, 8, 6, 9, 7, <span style="color:red>'''5'''</span>]
-  [0, 1, 2, 3, 4, '''6''', '''8''', 9, 7, 5]
+  [0, 1, 2, 3, 4, <span style="color:red>'''6'''</span>, <span style="color:red>'''8'''</span>, 9, 7, 5]
-  [0, 1, 2, 3, 4, '''5''', 8, 9, 7, '''6''']
+  [0, 1, 2, 3, 4, <span style="color:red>'''5'''</span>, 8, 9, 7, <span style="color:red>'''6'''</span>]
-  [0, 1, 2, 3, 4, 5, '''7''', 9, '''8''', 6]
+  [0, 1, 2, 3, 4, 5, <span style="color:red>'''7'''</span>, 9, <span style="color:red>'''8'''</span>, 6]
-  [0, 1, 2, 3, 4, 5, '''6''', 9, 8, '''7''']
+  [0, 1, 2, 3, 4, 5, <span style="color:red>'''6'''</span>, 9, 8, <span style="color:red>'''7'''</span>]
-  [0, 1, 2, 3, 4, 5, 6, '''8''', '''9''', 7]
+  [0, 1, 2, 3, 4, 5, 6, <span style="color:red>'''8'''</span>, <span style="color:red>'''9'''</span>, 7]
-  [0, 1, 2, 3, 4, 5, 6, '''7''', 9, '''8''']
+  [0, 1, 2, 3, 4, 5, 6, <span style="color:red>'''7'''</span>, 9, <span style="color:red>'''8'''</span>]
-  [0, 1, 2, 3, 4, 5, 6, 7, '''8''', '''9''']
+  [0, 1, 2, 3, 4, 5, 6, 7, <span style="color:red>'''8'''</span>, <span style="color:red>'''9'''</span>]
   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-−
   ''[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]''