Adaptiver Sortieralgorithmus - Versionsgeschichte

T. Wirbitzki: /* Einzelnachweise */ lk, Linkbeschriftung

2022-10-22T11:43:31Z

Einzelnachweise: lk, Linkbeschriftung

← Nächstältere Version		Version vom 22. Oktober 2022, 13:43 Uhr
Zeile 50:		Zeile 50:
	\| [[AVL-Baum\|AVL]] Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref name=AVL>A. Elmasry. ''Adaptive sorting with AVL trees.'', 2004, S. 309. </ref>		\| [[AVL-Baum\|AVL]] Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref name=AVL>A. Elmasry. ''Adaptive sorting with AVL trees.'', 2004, S. 309. </ref>
	\|-		\|-
	\| [[Mergesort#Natural Mergesort\|Natural Mergesort]] \|\| <math>\Theta (n \log(\operatorname{Runs}(X))) </math><ref name=Flensburg>{{Internetquelle\|url=~~http~~://www.~~iti~~.fh-flensburg.de/lang/algorithmen/sortieren/merge/natmerge.htm\|werk=FH Flensburg\|~~titel~~=~~Natural~~ ~~Mergesort~~\|zugriff=2019-07-20}}</ref>		\| [[Mergesort#Natural Mergesort\|Natural Mergesort]] \|\| <math>\Theta (n \log(\operatorname{Runs}(X))) </math><ref name="Flensburg">{{Internetquelle \|autor=Hans Werner Lang \|url=https://www.inf.hs-flensburg.de/lang/algorithmen/sortieren/merge/natmerge.htm \|titel=Natural Mergesort \|werk=[[Hochschule Flensburg (Fachhochschule)\|Hochschule Flensburg]] \|datum=2001 \|zugriff=2019-07-20}}</ref>
	\|-		\|-
	\|Patience Sorting \|\| Best-Case: <math>O(n)</math>, bei sortierter Eingabe. Average-Case <math>O(n \log n)</math><ref name=Patience>{{Internetquelle\|url=https://www.microsoft.com/en-us/research/publication/patience-is-a-virtue-revisiting-merge-and-sort-on-modern-processors/?from=http%3A%2F%2Fresearch.microsoft.com%2Fpubs%2F209622%2Fpatsort-sigmod14.pdf\|titel=Patience is a Virtue: Revisiting Merge and ~~Sorton~~ Modern Processors\|zugriff=2019-07-30}}</ref>		\|Patience Sorting \|\| Best-Case: <math>O(n)</math>, bei sortierter Eingabe. Average-Case <math>O(n \log n)</math><ref name="Patience">{{Internetquelle \|autor=Badrish Chandramouli, Jonathan Goldstein \|url=https://www.microsoft.com/en-us/research/publication/patience-is-a-virtue-revisiting-merge-and-sort-on-modern-processors/?from=http%3A%2F%2Fresearch.microsoft.com%2Fpubs%2F209622%2Fpatsort-sigmod14.pdf \|titel=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors \|datum=2014 \|sprache=en \|zugriff=2019-07-30}}</ref>
	\|-		\|-
	\| Randomisierter [[Quicksort]] \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref>G. Brodal, R. Fagerberg and G. Moruz. ''On the adaptiveness of quicksort.'', 2005, S. 3. </ref>		\| Randomisierter [[Quicksort]] \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref>G. Brodal, R. Fagerberg and G. Moruz. ''On the adaptiveness of quicksort.'', 2005, S. 3. </ref>

Balticbuchonia: /* Einzelnachweise */ doppeltes Wort

2022-08-27T12:17:19Z

Einzelnachweise: doppeltes Wort

← Nächstältere Version		Version vom 27. August 2022, 14:17 Uhr
Zeile 186:		Zeile 186:
	</syntaxhighlight>		</syntaxhighlight>

	Abschließende Experimente zeigen, dass AdaSort zuverlässig den schnellsten Algorithmus auswählt, und im Durchschnitt nur wenige Mikrosekunden langsamer ist als der jeweils schnellste Sortieralgorithmus. Diese Experimente waren allerdings an die Entscheidungsgrenzen für ''n'' im Algorithmus, also <math> n \in \{50, 100, 1000, 10000, 100000, 500000, 1000000\} </math> angepasst, und auf Eingaben fast ohne Ordnung mit <math> \operatorname{RUNS}(X) \approx 0{,}8</math> eingeschränkt. Da das Machine-Learning-Verfahren ebenfalls nur für diese ''n'' Entscheidungsgrenzen gelernt hat, ist damit ~~ist~~ nicht klar, wie gut AdaSort im Vergleich zu anderen Algorithmen für beispielsweise <math>n = 357211, \text{RUNS} = 0{,}001</math> ist, also <math>\approx 357</math> Runs mit durchschnittlicher Länge von <math>\approx 1000</math>. Es ist zu vermuten, dass für allgemeine <math>n</math> und größere Ordnung in den Eingaben andere Entscheidungsgrenzen für andere Algorithmen gefunden werden können, mit denen AdaSort in diesen Fällen auch eine bessere durchschnittliche Laufzeit erzielt.		Abschließende Experimente zeigen, dass AdaSort zuverlässig den schnellsten Algorithmus auswählt, und im Durchschnitt nur wenige Mikrosekunden langsamer ist als der jeweils schnellste Sortieralgorithmus. Diese Experimente waren allerdings an die Entscheidungsgrenzen für ''n'' im Algorithmus, also <math> n \in \{50, 100, 1000, 10000, 100000, 500000, 1000000\} </math> angepasst, und auf Eingaben fast ohne Ordnung mit <math> \operatorname{RUNS}(X) \approx 0{,}8</math> eingeschränkt. Da das Machine-Learning-Verfahren ebenfalls nur für diese ''n'' Entscheidungsgrenzen gelernt hat, ist damit nicht klar, wie gut AdaSort im Vergleich zu anderen Algorithmen für beispielsweise <math>n = 357211, \text{RUNS} = 0{,}001</math> ist, also <math>\approx 357</math> Runs mit durchschnittlicher Länge von <math>\approx 1000</math>. Es ist zu vermuten, dass für allgemeine <math>n</math> und größere Ordnung in den Eingaben andere Entscheidungsgrenzen für andere Algorithmen gefunden werden können, mit denen AdaSort in diesen Fällen auch eine bessere durchschnittliche Laufzeit erzielt.

	== Einzelnachweise ==		== Einzelnachweise ==

Boehm: typog

2022-08-04T06:47:42Z

typog

Wikinger08: QS erledigt

2021-01-21T15:07:09Z

QS erledigt

← Nächstältere Version		Version vom 21. Januar 2021, 17:07 Uhr
Zeile 1:		Zeile 1:
	{{QS-Antrag\|1. Dezember 2020\|2=2019 hier abgekippt und seitdem verwaist. Falls korrekt und enz. relevant: Von wo aus dem ANR sollte das verlinkt werden? --[[Benutzer:Jbergner\|Jbergner]] ([[Benutzer Diskussion:Jbergner\|Diskussion]]) 12:10, 1. Dez. 2020 (CET)}}
	'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.		'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.

Wikinger08: Wikinger08 verschob die Seite Adaptives Sortieren nach Adaptiver Sortieralgorithmus: Lemmakorrektur

2021-01-21T15:04:32Z

Wikinger08 verschob die Seite Adaptives Sortieren nach Adaptiver Sortieralgorithmus: Lemmakorrektur

← Nächstältere Version	Version vom 21. Januar 2021, 17:04 Uhr
(kein Unterschied)

Wikinger08: Komma

2021-01-21T14:59:31Z

Komma

← Nächstältere Version		Version vom 21. Januar 2021, 16:59 Uhr
Zeile 2:		Zeile 2:
	'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.		'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.

	Da es in der Praxis oft vorkommt, dass Eingaben bereits beinahe sortiert sind, ist man an Algorithmen interessiert, die in diesen Fällen besonders schnell arbeiten. Das Ziel dabei ist es die [[Sortierverfahren#Beweis der unteren Schranke für vergleichsbasiertes Sortieren\|untere Schranke]] <math>O(n \log n)</math> für den [[Average Case]] bei vergleichsbasierten Sortieralgorithmen zu unterbieten.		Da es in der Praxis oft vorkommt, dass Eingaben bereits beinahe sortiert sind, ist man an Algorithmen interessiert, die in diesen Fällen besonders schnell arbeiten. Das Ziel dabei ist es, die [[Sortierverfahren#Beweis der unteren Schranke für vergleichsbasiertes Sortieren\|untere Schranke]] <math>O(n \log n)</math> für den [[Average Case]] bei vergleichsbasierten Sortieralgorithmen zu unterbieten.

	Bei der Laufzeitanalyse der adaptiven Verfahren wird neben der Eingabegröße auch ein Maß für die bereits vorhandene Ordnung in der Eingabe einbezogen – im Gegensatz zu [[Sortierverfahren#Vergleichsbasiertes Sortieren\|klassischen vergleichsbasierten Sortierverfahren]], bei denen nur zwischen [[Best Case]], Average Case und [[Worst Case]] unterschieden wird, das Verhalten der Algorithmen zwischen diesen Fällen aber nicht weiter untersucht wird.		Bei der Laufzeitanalyse der adaptiven Verfahren wird neben der Eingabegröße auch ein Maß für die bereits vorhandene Ordnung in der Eingabe einbezogen – im Gegensatz zu [[Sortierverfahren#Vergleichsbasiertes Sortieren\|klassischen vergleichsbasierten Sortierverfahren]], bei denen nur zwischen [[Best Case]], Average Case und [[Worst Case]] unterschieden wird, das Verhalten der Algorithmen zwischen diesen Fällen aber nicht weiter untersucht wird.

Warburg1866: links

2020-12-02T07:12:41Z

links

← Nächstältere Version		Version vom 2. Dezember 2020, 09:12 Uhr
Zeile 2:		Zeile 2:
	'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.		'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.

	Da es in der Praxis oft vorkommt, dass Eingaben bereits beinahe sortiert sind, ist man an Algorithmen interessiert, die in diesen Fällen besonders schnell arbeiten. Das Ziel dabei ist es die [[Sortierverfahren#Beweis der unteren Schranke für vergleichsbasiertes Sortieren\|untere Schranke]] <math>O(n \log n)</math> für den Average-Case bei vergleichsbasierten Sortieralgorithmen zu unterbieten.		Da es in der Praxis oft vorkommt, dass Eingaben bereits beinahe sortiert sind, ist man an Algorithmen interessiert, die in diesen Fällen besonders schnell arbeiten. Das Ziel dabei ist es die [[Sortierverfahren#Beweis der unteren Schranke für vergleichsbasiertes Sortieren\|untere Schranke]] <math>O(n \log n)</math> für den [[Average Case]] bei vergleichsbasierten Sortieralgorithmen zu unterbieten.

	Bei der Laufzeitanalyse der adaptiven Verfahren wird neben der Eingabegröße auch ein Maß für die bereits vorhandene Ordnung in der Eingabe einbezogen – im Gegensatz zu [[Sortierverfahren#Vergleichsbasiertes Sortieren\|klassischen vergleichsbasierten Sortierverfahren]], bei denen nur zwischen Best-Case, Average-Case und Worst-Case unterschieden wird, das Verhalten der Algorithmen zwischen diesen Fällen aber nicht weiter untersucht wird.		Bei der Laufzeitanalyse der adaptiven Verfahren wird neben der Eingabegröße auch ein Maß für die bereits vorhandene Ordnung in der Eingabe einbezogen – im Gegensatz zu [[Sortierverfahren#Vergleichsbasiertes Sortieren\|klassischen vergleichsbasierten Sortierverfahren]], bei denen nur zwischen [[Best Case]], Average Case und [[Worst Case]] unterschieden wird, das Verhalten der Algorithmen zwischen diesen Fällen aber nicht weiter untersucht wird.

	== Maße der Ordnung ==		== Maße der Ordnung ==

Jbergner: /* Einleitung */ QS+

2020-12-01T11:10:34Z

Einleitung: QS+

← Nächstältere Version		Version vom 1. Dezember 2020, 13:10 Uhr
Zeile 1:		Zeile 1:
			{{QS-Antrag\|1. Dezember 2020\|2=2019 hier abgekippt und seitdem verwaist. Falls korrekt und enz. relevant: Von wo aus dem ANR sollte das verlinkt werden? --[[Benutzer:Jbergner\|Jbergner]] ([[Benutzer Diskussion:Jbergner\|Diskussion]]) 12:10, 1. Dez. 2020 (CET)}}
	'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.		'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.

CaroFraTyskland: Rechtschreibfehler

2019-08-07T12:11:31Z

Rechtschreibfehler

← Nächstältere Version		Version vom 7. August 2019, 14:11 Uhr
Zeile 6:		Zeile 6:

	== Maße der Ordnung ==		== Maße der Ordnung ==
	Damit die bereits vorhandene Ordnung in der Eingabe in die Analyse des ~~Agorithmus~~ einfließen kann, muss diese Ordnung gemessen werden. Dafür haben sich mehrere verschiedene Maße etabliert.		Damit die bereits vorhandene Ordnung in der Eingabe in die Analyse des Algorithmus einfließen kann, muss diese Ordnung gemessen werden. Dafür haben sich mehrere verschiedene Maße etabliert.

	Ein häufig verwendetes Maß<ref name = "Petersson155">O. Petersson, A. Moffat: ''A framework for adaptive sorting.'' 1992, S. 155+156.</ref> ist die Anzahl der [[Fehlstand\|Fehlstände]], also die Anzahl der Paare in falscher Ordnung, in der Eingabe <math> X = (x_1, ..., x_n) </math>:		Ein häufig verwendetes Maß<ref name = "Petersson155">O. Petersson, A. Moffat: ''A framework for adaptive sorting.'' 1992, S. 155+156.</ref> ist die Anzahl der [[Fehlstand\|Fehlstände]], also die Anzahl der Paare in falscher Ordnung, in der Eingabe <math> X = (x_1, ..., x_n) </math>:
Zeile 82:		Zeile 82:
	=== Patience Sorting ===		=== Patience Sorting ===
	Patience Sorting<ref name=Patience/> verläuft in zwei Phasen. In der ersten Phase werden ''Runs'' (siehe oben) erzeugt: jedes Element wird entweder dem Ende eines bereits angelegten Runs angefügt, oder, falls es keinen Run gibt, bei dem das möglich ist, bildet einen neuen Run.		Patience Sorting<ref name=Patience/> verläuft in zwei Phasen. In der ersten Phase werden ''Runs'' (siehe oben) erzeugt: jedes Element wird entweder dem Ende eines bereits angelegten Runs angefügt, oder, falls es keinen Run gibt, bei dem das möglich ist, bildet einen neuen Run.
	In der zweiten Phase wird ein [[Merge-Algorithmen#k-Wege-Mischen\|k-Wege-Mischen]] auf die Runs angewendet, um eine sortierte Folge zu ~~erhaten~~.		In der zweiten Phase wird ein [[Merge-Algorithmen#k-Wege-Mischen\|k-Wege-Mischen]] auf die Runs angewendet, um eine sortierte Folge zu erhalten.

	'''Beispiel:'''		'''Beispiel:'''

Aka: Leerzeichen vor Zahl eingefügt, Halbgeviertstrich, Links normiert, Kleinkram

2019-08-06T18:26:25Z

Leerzeichen vor Zahl eingefügt, Halbgeviertstrich, Links normiert, Kleinkram

← Nächstältere Version		Version vom 21. Januar 2021, 16:59 Uhr
Zeile 2:		Zeile 2:
	'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.		'''Adaptive Sortieralgorithmen''' sind [[Sortierverfahren\|Sortieralgorithmen]], deren [[Kontrollfluss]] von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.

	Da es in der Praxis oft vorkommt, dass Eingaben bereits beinahe sortiert sind, ist man an Algorithmen interessiert, die in diesen Fällen besonders schnell arbeiten. Das Ziel dabei ist es die [[Sortierverfahren#Beweis der unteren Schranke für vergleichsbasiertes Sortieren\|untere Schranke]] <math>O(n \log n)</math> für den [[Average Case]] bei vergleichsbasierten Sortieralgorithmen zu unterbieten.		Da es in der Praxis oft vorkommt, dass Eingaben bereits beinahe sortiert sind, ist man an Algorithmen interessiert, die in diesen Fällen besonders schnell arbeiten. Das Ziel dabei ist es, die [[Sortierverfahren#Beweis der unteren Schranke für vergleichsbasiertes Sortieren\|untere Schranke]] <math>O(n \log n)</math> für den [[Average Case]] bei vergleichsbasierten Sortieralgorithmen zu unterbieten.

	Bei der Laufzeitanalyse der adaptiven Verfahren wird neben der Eingabegröße auch ein Maß für die bereits vorhandene Ordnung in der Eingabe einbezogen – im Gegensatz zu [[Sortierverfahren#Vergleichsbasiertes Sortieren\|klassischen vergleichsbasierten Sortierverfahren]], bei denen nur zwischen [[Best Case]], Average Case und [[Worst Case]] unterschieden wird, das Verhalten der Algorithmen zwischen diesen Fällen aber nicht weiter untersucht wird.		Bei der Laufzeitanalyse der adaptiven Verfahren wird neben der Eingabegröße auch ein Maß für die bereits vorhandene Ordnung in der Eingabe einbezogen – im Gegensatz zu [[Sortierverfahren#Vergleichsbasiertes Sortieren\|klassischen vergleichsbasierten Sortierverfahren]], bei denen nur zwischen [[Best Case]], Average Case und [[Worst Case]] unterschieden wird, das Verhalten der Algorithmen zwischen diesen Fällen aber nicht weiter untersucht wird.

← Nächstältere Version		Version vom 4. August 2022, 08:47 Uhr
Zeile 8:		Zeile 8:
	Damit die bereits vorhandene Ordnung in der Eingabe in die Analyse des Algorithmus einfließen kann, muss diese Ordnung gemessen werden. Dafür haben sich mehrere verschiedene Maße etabliert.		Damit die bereits vorhandene Ordnung in der Eingabe in die Analyse des Algorithmus einfließen kann, muss diese Ordnung gemessen werden. Dafür haben sich mehrere verschiedene Maße etabliert.

	Ein häufig verwendetes Maß<ref name = "Petersson155">O. Petersson, A. Moffat: ''A framework for adaptive sorting.'' 1992, S. 155+156.</ref> ist die Anzahl der [[Fehlstand\|Fehlstände]], also die Anzahl der Paare in falscher Ordnung, in der Eingabe <math> X = (x_1, ~~...~~, x_n) </math>:		Ein häufig verwendetes Maß<ref name = "Petersson155">O. Petersson, A. Moffat: ''A framework for adaptive sorting.'' 1992, S. 155+156.</ref> ist die Anzahl der [[Fehlstand\|Fehlstände]], also die Anzahl der Paare in falscher Ordnung, in der Eingabe <math> X = (x_1, \dots, x_n) </math>:

	:<math>\operatorname{Inv}(X) = \| \left\{ (i,j) \mid 1 \leq i < j \leq n ~\text{und}~ x_i > x_j \right\} \| </math>.		:<math>\operatorname{Inv}(X) = \| \left\{ (i,j) \mid 1 \leq i < j \leq n ~\text{und}~ x_i > x_j \right\} \| </math>.

	Weitere oft genutzte Maße<ref name ="Petersson155"/> sind:		Weitere oft genutzte Maße<ref name ="Petersson155"/> sind:
	* die Anzahl von Serien aufeinanderfolgender, ansteigender Elemente, sogenannter ~~"runs"~~:		* die Anzahl von Serien aufeinanderfolgender, ansteigender Elemente, sogenannter „runs“:
	:<math> \operatorname{Runs}(X) = \|\{\, i\, \mid 1 \leq i < n ~\text{und}~ x_i > x_(i+1) \}\| + 1 </math>		:<math> \operatorname{Runs}(X) = \|\{\, i\, \mid 1 \leq i < n ~\text{und}~ x_i > x_(i+1) \}\| + 1 </math>
	* die Anzahl von Elementen, die mindestens entfernt werden müssen, um eine sortierte Folge zu erhalten:		* die Anzahl von Elementen, die mindestens entfernt werden müssen, um eine sortierte Folge zu erhalten:
	:<math> \operatorname{Rem}(X) = n - \max\{\, k\, \mid X ~\text{hat eine sortierte Teilfolge der Länge}~ k \} </math>		:<math> \operatorname{Rem}(X) = n - \max\{\, k\, \mid X ~\text{hat eine sortierte Teilfolge der Länge}~ k \} </math>
	* die minimale Anzahl von Vertauschungen je zweier Elemente, um die Eingabe zu sortieren: <math> \operatorname{Exc}(X) </math>		* die minimale Anzahl von Vertauschungen je zweier Elemente, um die Eingabe zu sortieren: <math> \operatorname{Exc}(X) </math>

Zeile 44:		Zeile 44:
	! Sortierverfahren \|\| Laufzeit		! Sortierverfahren \|\| Laufzeit
	\|-		\|-
	\| A-Sort<ref>K. Mehlhorn: ''Sorting Presorted Files.'' 1978, S. 11.</ref> \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> (optimal)<ref name = "Peterson165"/><ref>G. Stolting, Chapman & Hall/CRC Computer and Information Science Series.''Handbook of Data Structures and Applications'', 2005, S. 11–8. </ref>		\| A-Sort<ref>K. Mehlhorn: ''Sorting Presorted Files.'' 1978, S. 11.</ref> \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> (optimal)<ref name = "Peterson165"/><ref>G. Stolting, Chapman & Hall/CRC Computer and Information Science Series.''Handbook of Data Structures and Applications'', 2005, S. 11–8. </ref>
	\|-		\|-
	\| Adaptive Heap Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> <ref name =ConstantFactor>S. Edelkamp, A. Elmasry, J. Katajainen.''Two Constant-Factor-Optimal Realizations of Adaptive Heapsort'', 2011, S. 3. </ref>		\| Adaptive Heap Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> <ref name =ConstantFactor>S. Edelkamp, A. Elmasry, J. Katajainen.''Two Constant-Factor-Optimal Realizations of Adaptive Heapsort'', 2011, S. 3. </ref>
	\|-		\|-
	\| [[AVL-Baum\|AVL]] Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref name=AVL>A. Elmasry. ''Adaptive sorting with AVL trees.'', 2004, S. 309. </ref>		\| [[AVL-Baum\|AVL]] Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref name=AVL>A. Elmasry. ''Adaptive sorting with AVL trees.'', 2004, S. 309. </ref>
	\|-		\|-
	\| [[Mergesort#Natural Mergesort\|Natural Mergesort]] \|\| <math>\Theta (n \log(\operatorname{Runs}(X))) </math><ref name=Flensburg>{{Internetquelle\|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/natmerge.htm\|werk=FH Flensburg\|titel=Natural Mergesort\|zugriff=2019-07-20}}</ref>		\| [[Mergesort#Natural Mergesort\|Natural Mergesort]] \|\| <math>\Theta (n \log(\operatorname{Runs}(X))) </math><ref name=Flensburg>{{Internetquelle\|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/natmerge.htm\|werk=FH Flensburg\|titel=Natural Mergesort\|zugriff=2019-07-20}}</ref>
Zeile 54:		Zeile 54:
	\|Patience Sorting \|\| Best-Case: <math>O(n)</math>, bei sortierter Eingabe. Average-Case <math>O(n \log n)</math><ref name=Patience>{{Internetquelle\|url=https://www.microsoft.com/en-us/research/publication/patience-is-a-virtue-revisiting-merge-and-sort-on-modern-processors/?from=http%3A%2F%2Fresearch.microsoft.com%2Fpubs%2F209622%2Fpatsort-sigmod14.pdf\|titel=Patience is a Virtue: Revisiting Merge and Sorton Modern Processors\|zugriff=2019-07-30}}</ref>		\|Patience Sorting \|\| Best-Case: <math>O(n)</math>, bei sortierter Eingabe. Average-Case <math>O(n \log n)</math><ref name=Patience>{{Internetquelle\|url=https://www.microsoft.com/en-us/research/publication/patience-is-a-virtue-revisiting-merge-and-sort-on-modern-processors/?from=http%3A%2F%2Fresearch.microsoft.com%2Fpubs%2F209622%2Fpatsort-sigmod14.pdf\|titel=Patience is a Virtue: Revisiting Merge and Sorton Modern Processors\|zugriff=2019-07-30}}</ref>
	\|-		\|-
	\| Randomisierter [[Quicksort]] \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref>G. Brodal, R. Fagerberg and G. Moruz. ''On the adaptiveness of quicksort.'', 2005, S. 3. </ref>		\| Randomisierter [[Quicksort]] \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref>G. Brodal, R. Fagerberg and G. Moruz. ''On the adaptiveness of quicksort.'', 2005, S. 3. </ref>
	\|-		\|-
	\|[[Shellsort]] \|\| Best-Case: <math>O(n \log n)</math>, bei sortierter Eingabe. Average-Case nicht in <math>O(n \log n)</math>.<ref name = shellsort>C. Plaxton, B. Poonen, T. Suel, ''Improved Lower Bounds for Shellsort.'' 1992, S. 9.</ref>		\|[[Shellsort]] \|\| Best-Case: <math>O(n \log n)</math>, bei sortierter Eingabe. Average-Case nicht in <math>O(n \log n)</math>.<ref name = shellsort>C. Plaxton, B. Poonen, T. Suel, ''Improved Lower Bounds for Shellsort.'' 1992, S. 9.</ref>
Zeile 186:		Zeile 186:
	</syntaxhighlight>		</syntaxhighlight>

	Abschließende Experimente zeigen, dass AdaSort zuverlässig den schnellsten Algorithmus auswählt, und im Durchschnitt nur wenige Mikrosekunden langsamer ist als der jeweils schnellste Sortieralgorithmus. Diese Experimente waren allerdings an die Entscheidungsgrenzen für ''n'' im Algorithmus, also <math> n \in \{50, 100, 1000, 10000, 100000, 500000, 1000000\} </math> angepasst, und auf Eingaben fast ohne Ordnung mit <math> \operatorname{RUNS}(X) \approx 0.8</math> eingeschränkt. Da das Machine-Learning-Verfahren ebenfalls nur für diese ''n'' Entscheidungsgrenzen gelernt hat, ist damit ist nicht klar, wie gut AdaSort im Vergleich zu anderen Algorithmen für beispielsweise <math>n = 357211, RUNS = 0.001</math> ist, also <math>\approx 357</math> Runs mit durchschnittlicher Länge von <math>\approx 1000</math>. Es ist zu vermuten, dass für allgemeine <math>n</math> und größere Ordnung in den Eingaben andere Entscheidungsgrenzen für andere Algorithmen gefunden werden können, mit denen AdaSort in diesen Fällen auch eine bessere durchschnittliche Laufzeit erzielt.		Abschließende Experimente zeigen, dass AdaSort zuverlässig den schnellsten Algorithmus auswählt, und im Durchschnitt nur wenige Mikrosekunden langsamer ist als der jeweils schnellste Sortieralgorithmus. Diese Experimente waren allerdings an die Entscheidungsgrenzen für ''n'' im Algorithmus, also <math> n \in \{50, 100, 1000, 10000, 100000, 500000, 1000000\} </math> angepasst, und auf Eingaben fast ohne Ordnung mit <math> \operatorname{RUNS}(X) \approx 0{,}8</math> eingeschränkt. Da das Machine-Learning-Verfahren ebenfalls nur für diese ''n'' Entscheidungsgrenzen gelernt hat, ist damit ist nicht klar, wie gut AdaSort im Vergleich zu anderen Algorithmen für beispielsweise <math>n = 357211, \text{RUNS} = 0{,}001</math> ist, also <math>\approx 357</math> Runs mit durchschnittlicher Länge von <math>\approx 1000</math>. Es ist zu vermuten, dass für allgemeine <math>n</math> und größere Ordnung in den Eingaben andere Entscheidungsgrenzen für andere Algorithmen gefunden werden können, mit denen AdaSort in diesen Fällen auch eine bessere durchschnittliche Laufzeit erzielt.

	== Einzelnachweise ==		== Einzelnachweise ==

← Nächstältere Version		Version vom 6. August 2019, 20:26 Uhr
Zeile 3:		Zeile 3:
	Da es in der Praxis oft vorkommt, dass Eingaben bereits beinahe sortiert sind, ist man an Algorithmen interessiert, die in diesen Fällen besonders schnell arbeiten. Das Ziel dabei ist es die [[Sortierverfahren#Beweis der unteren Schranke für vergleichsbasiertes Sortieren\|untere Schranke]] <math>O(n \log n)</math> für den Average-Case bei vergleichsbasierten Sortieralgorithmen zu unterbieten.		Da es in der Praxis oft vorkommt, dass Eingaben bereits beinahe sortiert sind, ist man an Algorithmen interessiert, die in diesen Fällen besonders schnell arbeiten. Das Ziel dabei ist es die [[Sortierverfahren#Beweis der unteren Schranke für vergleichsbasiertes Sortieren\|untere Schranke]] <math>O(n \log n)</math> für den Average-Case bei vergleichsbasierten Sortieralgorithmen zu unterbieten.

	Bei der Laufzeitanalyse der adaptiven Verfahren wird neben der Eingabegröße auch ein Maß für die bereits vorhandene Ordnung in der Eingabe einbezogen - im Gegensatz zu [[Sortierverfahren#~~Vergleichsbasiertes_Sortieren~~\|klassischen vergleichsbasierten Sortierverfahren]], bei denen nur zwischen Best-Case, Average-Case und Worst-Case unterschieden wird, das Verhalten der Algorithmen zwischen diesen Fällen aber nicht weiter untersucht wird.		Bei der Laufzeitanalyse der adaptiven Verfahren wird neben der Eingabegröße auch ein Maß für die bereits vorhandene Ordnung in der Eingabe einbezogen – im Gegensatz zu [[Sortierverfahren#Vergleichsbasiertes Sortieren\|klassischen vergleichsbasierten Sortierverfahren]], bei denen nur zwischen Best-Case, Average-Case und Worst-Case unterschieden wird, das Verhalten der Algorithmen zwischen diesen Fällen aber nicht weiter untersucht wird.

	== Maße der Ordnung ==		== Maße der Ordnung ==
Zeile 44:		Zeile 44:
	! Sortierverfahren \|\| Laufzeit		! Sortierverfahren \|\| Laufzeit
	\|-		\|-
	\| A-Sort<ref>K. Mehlhorn: ''Sorting Presorted Files.'' 1978, S. 11.</ref> \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> (optimal)<ref name = "Peterson165"/><ref>G. Stolting, Chapman & Hall/CRC Computer and Information Science Series.''Handbook of Data Structures and Applications'', 2005, S.~~11-8~~. </ref>		\| A-Sort<ref>K. Mehlhorn: ''Sorting Presorted Files.'' 1978, S. 11.</ref> \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> (optimal)<ref name = "Peterson165"/><ref>G. Stolting, Chapman & Hall/CRC Computer and Information Science Series.''Handbook of Data Structures and Applications'', 2005, S. 11–8. </ref>
	\|-		\|-
	\| Adaptive Heap Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> <ref name =ConstantFactor>S. Edelkamp, A. Elmasry, J. Katajainen.''Two Constant-Factor-Optimal Realizations of Adaptive Heapsort'', 2011, S.3. </ref>		\| Adaptive Heap Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> <ref name =ConstantFactor>S. Edelkamp, A. Elmasry, J. Katajainen.''Two Constant-Factor-Optimal Realizations of Adaptive Heapsort'', 2011, S. 3. </ref>
	\|-		\|-
	\| [[AVL-Baum\|AVL]] Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref name=AVL>A. Elmasry. ''Adaptive sorting with AVL trees.'', 2004, S.309. </ref>		\| [[AVL-Baum\|AVL]] Sort \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref name=AVL>A. Elmasry. ''Adaptive sorting with AVL trees.'', 2004, S. 309. </ref>
	\|-		\|-
	\| [[Mergesort#Natural Mergesort\|Natural Mergesort]] \|\| <math>\Theta (n \log(\operatorname{Runs}(X))) </math><ref name=Flensburg>{{Internetquelle\|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/natmerge.htm\|werk=FH Flensburg\|titel=Natural Mergesort\|zugriff=2019-07-20}}</ref>		\| [[Mergesort#Natural Mergesort\|Natural Mergesort]] \|\| <math>\Theta (n \log(\operatorname{Runs}(X))) </math><ref name=Flensburg>{{Internetquelle\|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/natmerge.htm\|werk=FH Flensburg\|titel=Natural Mergesort\|zugriff=2019-07-20}}</ref>
Zeile 54:		Zeile 54:
	\|Patience Sorting \|\| Best-Case: <math>O(n)</math>, bei sortierter Eingabe. Average-Case <math>O(n \log n)</math><ref name=Patience>{{Internetquelle\|url=https://www.microsoft.com/en-us/research/publication/patience-is-a-virtue-revisiting-merge-and-sort-on-modern-processors/?from=http%3A%2F%2Fresearch.microsoft.com%2Fpubs%2F209622%2Fpatsort-sigmod14.pdf\|titel=Patience is a Virtue: Revisiting Merge and Sorton Modern Processors\|zugriff=2019-07-30}}</ref>		\|Patience Sorting \|\| Best-Case: <math>O(n)</math>, bei sortierter Eingabe. Average-Case <math>O(n \log n)</math><ref name=Patience>{{Internetquelle\|url=https://www.microsoft.com/en-us/research/publication/patience-is-a-virtue-revisiting-merge-and-sort-on-modern-processors/?from=http%3A%2F%2Fresearch.microsoft.com%2Fpubs%2F209622%2Fpatsort-sigmod14.pdf\|titel=Patience is a Virtue: Revisiting Merge and Sorton Modern Processors\|zugriff=2019-07-30}}</ref>
	\|-		\|-
	\| Randomisierter [[Quicksort]] \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref>G. Brodal, R. Fagerberg and G. Moruz. ''On the adaptiveness of quicksort.'', 2005, S.3. </ref>		\| Randomisierter [[Quicksort]] \|\| <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math><ref>G. Brodal, R. Fagerberg and G. Moruz. ''On the adaptiveness of quicksort.'', 2005, S. 3. </ref>
	\|-		\|-
	\|[[Shellsort]] \|\| Best-Case: <math>O(n \log n)</math>, bei sortierter Eingabe. Average-Case nicht in <math>O(n \log n)</math>.<ref name = shellsort>C. Plaxton, B. Poonen, T. Suel, ''Improved Lower Bounds for Shellsort.'' 1992, S. 9.</ref>		\|[[Shellsort]] \|\| Best-Case: <math>O(n \log n)</math>, bei sortierter Eingabe. Average-Case nicht in <math>O(n \log n)</math>.<ref name = shellsort>C. Plaxton, B. Poonen, T. Suel, ''Improved Lower Bounds for Shellsort.'' 1992, S. 9.</ref>
Zeile 60:		Zeile 60:
	\|[[Smoothsort]] \|\| <math>O(n)</math> für sortierte Eingaben. Erreicht <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> nicht.<ref name = "hertel">{{Internetquelle\|url=http://scidok.sulb.uni-saarland.de/volltexte/2011/4062/pdf/fb14_1982_11.pdf\|titel=Smoothsort's behavior on presorted sequences\|zugriff=2019-07-30}}</ref> Worst-Case: <math>O(n \log n)</math>		\|[[Smoothsort]] \|\| <math>O(n)</math> für sortierte Eingaben. Erreicht <math>O \left(n \log \left(\frac{\operatorname{Inv}(X)}{n}\right) + n \right)</math> nicht.<ref name = "hertel">{{Internetquelle\|url=http://scidok.sulb.uni-saarland.de/volltexte/2011/4062/pdf/fb14_1982_11.pdf\|titel=Smoothsort's behavior on presorted sequences\|zugriff=2019-07-30}}</ref> Worst-Case: <math>O(n \log n)</math>
	\|-		\|-
	\| [[Splay-Baum\|Splay]]sort \|\| In Experimenten ab einer bestimmten Ordnung in der Eingabe schneller als Randomisierter Quicksort und AVL Sort.<ref name=inversionsensitive>A. Elmasry, A. Hammad. ''An Empirical Study for Inversions-Sensitive Sorting Algorithms.'', 2005, S.597. </ref>		\| [[Splay-Baum\|Splay]]sort \|\| In Experimenten ab einer bestimmten Ordnung in der Eingabe schneller als Randomisierter Quicksort und AVL Sort.<ref name=inversionsensitive>A. Elmasry, A. Hammad. ''An Empirical Study for Inversions-Sensitive Sorting Algorithms.'', 2005, S. 597. </ref>
	\|-		\|-
	\| Straight [[Insertionsort]] \|\| <math>\Theta (n + \operatorname{Inv}(X)) </math><ref name = "Peterson165">O. Petersson, A. Moffat: ''A framework for adaptive sorting.'' 1992, S. 165.</ref>		\| Straight [[Insertionsort]] \|\| <math>\Theta (n + \operatorname{Inv}(X)) </math><ref name = "Peterson165">O. Petersson, A. Moffat: ''A framework for adaptive sorting.'' 1992, S. 165.</ref>
	\|-		\|-
	\| [[Timsort]] \|\| <math>O(n + n \log \operatorname{Runs}(X))</math>.<ref>N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. ''On the Worst-Case Complexity of TimSort.'', 2012, S.4:8. </ref> Worst-Case: <math>O(n \log n)</math> <ref name=Tim>N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. ''On the Worst-Case Complexity of TimSort.'', 2012, S.4:4. </ref>		\| [[Timsort]] \|\| <math>O(n + n \log \operatorname{Runs}(X))</math>.<ref>N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. ''On the Worst-Case Complexity of TimSort.'', 2012, S. 4:8. </ref> Worst-Case: <math>O(n \log n)</math> <ref name=Tim>N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. ''On the Worst-Case Complexity of TimSort.'', 2012, S. 4:4. </ref>
	\|-		\|-
	\|}		\|}
Zeile 78:		Zeile 78:

	=== Natural Mergesort ===		=== Natural Mergesort ===
	[[Mergesort#Natural Mergesort\|Natural Mergesort]]<ref name=Flensburg/> verwendet als Ausgangspunkt für die merge-Operationen nicht einelementige Teilfolgen, sondern die in der Eingabe bereits vorhandenen ''Runs'' (siehe oben). Falls das größte Element der einen Teilfolge kleiner ist als das kleinste der zweiten Teilfolge, so kann die merge-Operation durch eine entsprechende [[~~Formale_Sprache~~#Konkatenation\|Konkatenation]] der beiden Teilfolgen ersetzt werden.		[[Mergesort#Natural Mergesort\|Natural Mergesort]]<ref name=Flensburg/> verwendet als Ausgangspunkt für die merge-Operationen nicht einelementige Teilfolgen, sondern die in der Eingabe bereits vorhandenen ''Runs'' (siehe oben). Falls das größte Element der einen Teilfolge kleiner ist als das kleinste der zweiten Teilfolge, so kann die merge-Operation durch eine entsprechende [[Formale Sprache#Konkatenation\|Konkatenation]] der beiden Teilfolgen ersetzt werden.

	=== Patience Sorting ===		=== Patience Sorting ===
Zeile 155:		Zeile 155:
	Keiner der bekannten adaptiven Sortieralgorithmen ist in allen Fällen schneller als alle anderen. Die Laufzeit der Algorithmen hängt aufgrund ihrer Adaptivität stark von der Eingabe ab, und so ist in manchen Fällen der eine Algorithmus schneller, in anderen der andere. Welcher Algorithmus der schnellste für eine Eingabe ist, ist erst nach der Ausführung bekannt.		Keiner der bekannten adaptiven Sortieralgorithmen ist in allen Fällen schneller als alle anderen. Die Laufzeit der Algorithmen hängt aufgrund ihrer Adaptivität stark von der Eingabe ab, und so ist in manchen Fällen der eine Algorithmus schneller, in anderen der andere. Welcher Algorithmus der schnellste für eine Eingabe ist, ist erst nach der Ausführung bekannt.

	Es ist aber möglich die Laufzeiten vorab zu [[Schätzfunktion#Schätzfunktionen\|schätzen]], und den Algorithmus auszuwählen mit der geringsten geschätzten Laufzeit, in der Hoffnung, dass dieser auch der tatsächlich schnellste Algorithmus für die Eingabe ist. Auf diese Weise kann aus den bekannten Algorithmen ein Algorithmus konstruiert werden, der für alle Eingaben, die zu einer guten Schätzung der Laufzeiten führen, so schnell sortiert, wie der jeweils schnellste Algorithmus, allerdings mit dem Zusatzaufwand für die Laufzeitschätzungen. Diese Schätzung kann mit [[~~Maschinelles_Lernen~~\|Machine-Learning]]-Verfahren durchgeführt werden.		Es ist aber möglich die Laufzeiten vorab zu [[Schätzfunktion#Schätzfunktionen\|schätzen]], und den Algorithmus auszuwählen mit der geringsten geschätzten Laufzeit, in der Hoffnung, dass dieser auch der tatsächlich schnellste Algorithmus für die Eingabe ist. Auf diese Weise kann aus den bekannten Algorithmen ein Algorithmus konstruiert werden, der für alle Eingaben, die zu einer guten Schätzung der Laufzeiten führen, so schnell sortiert, wie der jeweils schnellste Algorithmus, allerdings mit dem Zusatzaufwand für die Laufzeitschätzungen. Diese Schätzung kann mit [[Maschinelles Lernen\|Machine-Learning]]-Verfahren durchgeführt werden.

	In <ref>S. Majumdar, I. Jain, K. Kukreja ''AdaSort: Adaptive Sorting using Machine Learning.'' 2016.</ref> wurde das Machine-Learning-Verfahren so trainiert, dass es in Abhängigkeit von zwei Parametern, ''RUNS'' und ''n'', einen Sortieralgorithmus auswählt. Dabei ist		In <ref>S. Majumdar, I. Jain, K. Kukreja ''AdaSort: Adaptive Sorting using Machine Learning.'' 2016.</ref> wurde das Machine-Learning-Verfahren so trainiert, dass es in Abhängigkeit von zwei Parametern, ''RUNS'' und ''n'', einen Sortieralgorithmus auswählt. Dabei ist