Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Mergesort: Stabiler Algorithmus
Autor
Universität/Hochschule Mergesort: Stabiler Algorithmus
mathletic
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 11.11.2013
Mitteilungen: 1470
  Themenstart: 2015-03-10

Hallo, wie kann ich beweisen dass das Sortierverfahren Mergesort stabil ist und dass die Sortierverfahren Heapsort und Quicksort nicht stabil sind?


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2282
  Beitrag No.1, eingetragen 2015-03-10

Hallo, zum Nachweis der Instabilität brauchst du nur ein Beispiel, das die Instabilität zeigt. Kandidaten wären: man sortiere für ein passendes n [1,2,3...n] anhand des Algorithmus, wobei die Elemente aber nach dem Ordnungskriterium **alle als gleich** gelten. Wenn da nicht wieder [1,2,3...n] herauskommt, hat man ein Beispiel gefunden. Möglicherweise braucht man kompliziertere Kandidaten. Für den Nachweis der Stabilität von Mergesort kann man induktiv vorgehen. Man zeige, für beliebiges n: Unter der Hypothese, dass Mergesort alle Listen aller Längen kleiner n stabil sortiert, sortiert er auch alle Listen der Länge n stabil. Hierfür müssen die Aufteilung und das Merge zusammenpassen (es gibt ja ein paar Varianten...), und vielleicht verdient der Nachweis dessen ein eigenes kleines Lemma.


   Profil
Calculus
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 10.08.2012
Mitteilungen: 6086
  Beitrag No.2, eingetragen 2015-03-10

Überlege dir, was Stabilität im Zusammenhang mit Sortieralgorithmen bedeutet. Die Stabilität von Mergesort kannst du induktiv beweisen. Mergesort ruft lediglich zwei mal mergesort mit einem kleineren Vektor an Elementen auf und merged die Ergebnisse. Im Wesentlichen musst du nur beweisen, dass durch das mergen die Stabilität nicht verloren geht [sofern man es geeignet implementiert]. Um zu zeigen dass ein Algorithmus nicht stabil ist musst du lediglich ein Gegenbeispiel angeben. [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
mathletic
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 11.11.2013
Mitteilungen: 1470
  Beitrag No.3, vom Themenstarter, eingetragen 2015-03-11

\quoteon(2015-03-10 20:07 - tactac in Beitrag No. 1) Hallo, zum Nachweis der Instabilität brauchst du nur ein Beispiel, das die Instabilität zeigt. Kandidaten wären: man sortiere für ein passendes n [1,2,3...n] anhand des Algorithmus, wobei die Elemente aber nach dem Ordnungskriterium **alle als gleich** gelten. Wenn da nicht wieder [1,2,3...n] herauskommt, hat man ein Beispiel gefunden. Möglicherweise braucht man kompliziertere Kandidaten. \quoteoff Kann man zum Beispiel folgende Elemente nehmen? $\langle 4, 9, 3, 4, 0, 1\rangle$


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2282
  Beitrag No.4, eingetragen 2015-03-11

\quoteon(2015-03-11 08:52 - mathletic in Beitrag No. 3) [...] Kann man zum Beispiel folgende Elemente nehmen? $\langle 4, 9, 3, 4, 0, 1\rangle$ \quoteoff Das kommt auf den Algorithmus (Quick oder Heap?) an und u.U. seine Formulierung im Detail. Außerdem würde ich nicht die nackten Zahlen dort nehmen, sondern zwecks besserer Verfolgung noch eine "Id" heranhängen, die beim Vergleichen jedoch ignoriert wird. Also bei deinem Beispiel etwa $\langle (4,1), (9,1), (3,1), (4,2), (0,1), (1,1)\rangle$ Mit einem stabilen Algorithmus muss sich $\langle (0,1), (1,1), (3,1), (4,1), (4,2),(9,1) \rangle$ ergeben. Ergibt sich das nicht, hast du ein Gegenbeispiel gefunden; ansonsten musst du ein anderes Beispiel probieren.


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
fysiker
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.01.2015
Mitteilungen: 23
  Beitrag No.5, eingetragen 2021-02-03

Hallo! Ich würde diesen älteren Beitrag gerne wieder aufleben lassen https://matheplanet.com/matheplanet/nuke/html/images/forum/subject/rotate.gif \quoteon(2015-03-10 20:07 - tactac in Beitrag No. 1) Für den Nachweis der Stabilität von Mergesort kann man induktiv vorgehen. Man zeige, für beliebiges n: Unter der Hypothese, dass Mergesort alle Listen aller Längen kleiner n stabil sortiert, sortiert er auch alle Listen der Länge n stabil. Hierfür müssen die Aufteilung und das Merge zusammenpassen (es gibt ja ein paar Varianten...), und vielleicht verdient der Nachweis dessen ein eigenes kleines Lemma. \quoteoff Wie sähe denn der Induktionsanfang des Induktionsbeweises für die Stabilität des Mergesort-Algorithmus aus? Viele Grüße fysiker


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.6, eingetragen 2021-02-03

Induktionsanfang ist klar. Die leere Liste und die Liste mit einem Element werden sicherlich stabil sortiert. Für alles weitere benötigt man Details des konkreten Algorithmus. Man muss wissen, wie gesplittet und gemerget wird. Wenn man bspw. in gerade und ungerade Indizes splittet (das wäre beim Sortieren einfach verketteter Listen die naive Implementierung), wird es zumindest schwierig, die Stabilität nach dem Mergen zu garantieren. Einfache Variante: Wähle einen Algorithmus, der garantiert, dass die Stabilitätsinvariante immer erhalten bleibt. 1. Beim Splitten bleibt die Stabilitätsinvariante erhalten. (splitte bspw. in eine linke und rechte "Hälfte") 2. Beim Mergen bleibt die Stabilitätsinvariante erhalten. (bei Gleichheit wähle immer das linke Element) Der Induktionsschritt bezüglich der Stabilität besteht jetzt einfach darin, die Gültigkeit der Invariante nach den zwei Operationen formal nachzuweisen.


   Profil
fysiker
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.01.2015
Mitteilungen: 23
  Beitrag No.7, eingetragen 2021-02-03

Hallo Einfaeltiger! Danke für deine Antwort! Ich wage einen Versuch. Das ganze ist mir noch sehr unverständlich, also steinigt mich bitte, falls es falsch sein sollte https://matheplanet.com/matheplanet/nuke/html/images/forum/subject/icon17.gif Dafür benutze ich die für mich bekannte Definitionen für Sortieralgorithmen und Stabilität dieser. Also: Sei M Menge mit Ordnungsrelation \leq\). Für ein Tupel ($x_1,...,x_N)\,\in\,M^N$ ist eine Abb. $\pi:{1,...,N}\rightarrow {1,...N}$ ein Sortieralgorithmus, falls $\pi$ bijektiv und $x_{\pi(1)}\leq x_{\pi(j)} (i\leq j)$ überführt. Sei $\pi$ der Mergesort-Algorithmus. $\pi$ heißt nun stabil, falls $x_i=x_j\; (iBeitrag No. 6) Induktionsanfang ist klar. Die leere Liste und die Liste mit einem Element werden sicherlich stabil sortiert. Für alles weitere benötigt man Details des konkreten Algorithmus. Man muss wissen, wie gesplittet und gemerget wird. Wenn man bspw. in gerade und ungerade Indizes splittet (das wäre beim Sortieren einfach verketteter Listen die naive Implementierung), wird es zumindest schwierig, die Stabilität nach dem Mergen zu garantieren. Einfache Variante: Wähle einen Algorithmus, der garantiert, dass die Stabilitätsinvariante immer erhalten bleibt. 1. Beim Splitten bleibt die Stabilitätsinvariante erhalten. (splitte bspw. in eine linke und rechte "Hälfte") 2. Beim Mergen bleibt die Stabilitätsinvariante erhalten. (bei Gleichheit wähle immer das linke Element) Der Induktionsschritt bezüglich der Stabilität besteht jetzt einfach darin, die Gültigkeit der Invariante nach den zwei Operationen formal nachzuweisen. \quoteoff Warum darf ich mir aussuchen, wie gesplittet und gemerget wird? Dann wäre das doch nur ein Beispiel für den Mergesort-Algorithmus??? Nun startet die Verwirrung! https://matheplanet.com/matheplanet/nuke/html/images/forum/subject/aaaicon5.gif


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]