ShellSort < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo Zusammen,
Ich habe hier ein Sortierproblem, welches auf dem ShellSort-Algorithmus basiert. Zunächst einmal der Algorithmus, auf dem die Aufgabe basiert:
$ \begin{gathered} {\text{ShellSort}}\left( {{\text{itemType}}\,a\left[ 1 \right], \ldots ,a\left[ N \right]} \right){\text{\{}\green{\text{ // }} }}\green{a{\text{[] zu sortierende Folge}}} \hfill \\ \quad {\text{int }}i,j,k,h; \hfill \\ \quad {\text{itemType }}v;\quad \quad \quad \quad \quad \quad \quad \quad \quad \green{\text{// Zwischenspeicher}} \hfill \\ \quad {\text{int }}h\left[ t \right], \ldots ,h\left[ 1 \right]\quad \quad \quad \quad \quad \quad \quad \,\,\green{\text{// absteigende Folge von t Inkrementen}} \hfill \\ \quad {\text{for }}k = t{\text{ downto }}1{\text{ \{ }}\quad \quad \quad \quad \quad \;\;\green{\text{// Durchlaufe Inkrementenfolge}} \hfill \\ \quad \quad h = h\left[ k \right];\quad \quad \quad \quad \quad \quad \quad \quad \;\;\,\green{{\text{// aktuelles Inkrement }}h} \hfill \\ \quad \quad {\text{for }}i = h + 1{\text{ to }}N{\text{ \{ }}\quad \quad \quad \quad \quad \green{{\text{// Betrachte nur Positionen }} > h} \hfill \\ \quad \quad \quad v = a\left[ i \right];\;j = i; \hfill \\ \quad \quad \quad {\text{while }}\left( {j > h} \right){\text{ and }}\left( {a\left[ {j - h} \right] > v} \right){\text{ \{ }\green{\text{// Sortiere aktuelles Element ein}}} \hfill \\ \quad \quad \quad \quad a\left[ j \right] = a\left[ {j - h} \right];\;j \mathrel{\mathord{-}\mathord{=}} h;\quad \quad \quad \;\;\green{{\text{// }} \ldots {\text{ in Schritten der Weite }}h} \hfill \\ \quad \quad \quad {\text{\} }} \hfill \\ \quad \quad \quad a\left[ j \right] = v; \hfill \\ \quad \quad {\text{\} }} \hfill \\ \quad {\text{\} }} \hfill \\ {\text{\} }} \hfill \\ \end{gathered} $
| Aufgabe | Für $h,n,r \in \IN$ seien zwei Zahlenfolgen $x := x_1,\ldots,x_{r+h}$ und $y := y_1,\ldots,y_{r+n}$ gegeben, so daß für $1 \le i \le r$ jeweils $y_i \le x_{i+h}$ gilt.
Zeige: Sind $x'_1,\ldots,x'_{r+h}$ und $y'_1,\ldots,y'_{r+n}$ sortierte Versionen von x und y, so gilt $\forall 1 \le i \le r: y'_i \le x'_{i+h}$. |
Dies ist die Musterlösung:
[m]\begin{gathered}
\bar x = x_1 , \ldots ,x_{r + h} \hfill \\
\bar y = y_1 , \ldots ,y_{r + h} \hfill \\
\end{gathered}[/m]
Es gelte: [m]y_i \le x_{i + h}[/m]
Z.Z.: Ist [mm] $\bar [/mm] y'$ sortierte Version von [mm] $\bar [/mm] y$ und [mm] $\bar [/mm] x'$ sortierte Version von [mm] $\bar [/mm] x [mm] \Rightarrow [/mm] y'_i [mm] \le [/mm] x'_{i+h} [mm] \forall [/mm] i [mm] \in \left[1:r\right]$
[/mm]
Beweis:
[mm] $y_1 \le x_{1+h} \ldots y_r \le x_{r+h}$. [/mm] Für jedes [mm] $x_{1+h},\ldots,x_{r+h}$ [/mm] gibt es ein [mm] $y\!$, [/mm] so daß [mm] $y_i \le x_{i+h}$. [/mm] Angenommen $y'_i > x'_{i+h} [mm] \ne x_{i+h} \ge [/mm] y$, dann gäbe es $y'_i [mm] \le x'_{i+h},\ldots,y'_{i-1} \le [/mm] x'_{i+h-1}, x'_{i+h} < y'_i$, dann gäbe es schon vorher ein [mm] $x_{i+h} [/mm] < [mm] y_i$. [/mm] Widerspruch. [mm] $\square$
[/mm]
Leider verstehe ich diesen Beweis nicht. Das, was in der Aufgabenstellung vorgegeben ist, kann man sich doch folgendermaßen bildhaft vorstellen:
Gegeben:
[Dateianhang nicht öffentlich]
Beispiel:
[Dateianhang nicht öffentlich]
Anhand dieser Graphiken habe ich jetzt versucht so zu folgern:
Angenommen nach der Sortierung gäbe es ein $y'_i$, so daß $y'_i > x'_{h+i}$. Dann muß wegen der Sortierung auch $x'_1 [mm] \le \ldots \le [/mm] x'_h [mm] \le \ldots \le [/mm] x'_{h+i} < y'_i [mm] \le \ldots \le [/mm] y'_r [mm] \le \ldots \le [/mm] y'_{r+n}$ gelten.
Das ist das Einzige, was mir bisher einleuchtet(, weil man das an dem Bild sieht). Aber wie folgert man jetzt weiter?
Vielen Dank!
Viele Grüße
Karl
P.S. Ich habe diese Frage auch ![[]](/images/popup.gif) im Usenet gestellt.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
Anhang Nr. 2 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:21 Mo 04.07.2005 | | Autor: | Aly |
Für $h,n,r [mm] \in \IN$ [/mm] seien zwei Zahlenfolgen $x := [mm] x_1,\ldots,x_{r+h}$ [/mm] und $y := [mm] y_1,\ldots,y_{r+n}$ [/mm] gegeben, so daß für $1 [mm] \le [/mm] i [mm] \le [/mm] r$ jeweils [mm] $y_i \le x_{i+h}$ [/mm] gilt.
Zeige: Sind [mm] $x'_1,\ldots,x'_{r+h}$ [/mm] und [mm] $y'_1,\ldots,y'_{r+n}$ [/mm] sortierte Versionen von x und y, so gilt [mm] $\forall [/mm] 1 [mm] \le [/mm] i [mm] \le [/mm] r: y'_i [mm] \le [/mm] x'_{i+h}$.
Es ist ganz einfach ... Es ist ein Abzählargument
Seien [mm] x^{'}_{i+h} [/mm] und [mm] y^{'}_{i} [/mm] beliebig mit [mm] 1\le [/mm] i [mm] \le [/mm] n.
[mm] x^{'}_{i+h} [/mm] spaltet die Folge [mm] x^{'} [/mm] in zwei Teile:
Elemente die grösser [mm] x^{'}_{i+h} [/mm] sind und Elemente die kleiner als diese sind.
Es gibt r-i Elemente [mm] \ge x^{'}_{i+h}
[/mm]
[mm] y^{'}_{i} [/mm] spaltet die Folge y' in zwei Teile:
Elemente die grösser gleich [mm] x^{'}_{i+h} [/mm] sind und Elemente die kleiner gleich als diese sind.
Es gibt i-1 Elemente [mm] \le y^{'}_{i}.
[/mm]
Nun die Beziehungen vor der Sortierung bleiben erhalten aber nur die Reihenfolge ändert sich.
Und unsere Frage ist, ob die Beziehungen ihre Form in der sortierten Folgen behalten oder nicht.
Die Antwort ist ein klares ja.
Warum?
Nun Wir wissen dass es r Elemente in [mm] x^{'} [/mm] gibt, die grösser als r Elemente in [mm] y^{'} [/mm] sind. Eine Annahme, die diese Tatsache widerspricht ist sicher falsch.
Wir zeigen nun, dass folgende Annahme diese Tatsache widerspricht und dass sie deswegen falsch ist.
Nun nehmen wir an
[mm] \exists 1\le [/mm] i [mm] \le [/mm] r mit [mm] x^{'}_{i+h} [/mm] < [mm] y^{'}_{i}
[/mm]
dann gibt es nicht mehr r Elemente in x' die grösser als r Elemente in y' sind und das aus folgendem Grund:
Es gibt n-r Elemente [mm] \ge x^{'}_{i+h} [/mm] diese können natürlich nur grösser als r-i Elemente aus y' sein. Nun wir müssen weitere i Elemente in x' finden die grösser als i Elemente in y' sind. Diese sind im zweiten Teil von x' zu suchen nämlich dem Teil, deren Elemente kleiner gleich [mm] x^{'}_{i+h} [/mm] sind aber diese Elemente sind, wegen der Sortierung der Folge und wegen [mm] x^{'}_{i+h} \le y^{'}_{i}, [/mm] alle kleiner [mm] y^{'}_{i}. [/mm] also wenn dann können sie nur grösser als die Elemente in y' die kleiner [mm] y^{'}_{i} [/mm] sind und diese sind nur i-1 Elemente.
d.h höchsten kann es r-i+i-1 = r-1 Elemente in x' geben die grösser als r-1 Elemente in y' sind. Aber wir wissen dass es r solcher Elemente gibt. Somit kann es kein i geben mit der betrachteten Eigenschaft und demzufolge ist die Beh. bewiesen
|
|
|
| |
|
Hallo Aly,
Zunächst vielen Dank für deine Antwort!
> Für [mm]h,n,r \in \IN[/mm] seien zwei Zahlenfolgen [mm]x := x_1,\ldots,x_{r+h}[/mm]
> und [mm]y := y_1,\ldots,y_{r+n}[/mm] gegeben, so daß für [mm]1 \le i \le r[/mm]
> jeweils [mm]y_i \le x_{i+h}[/mm] gilt.
> Zeige: Sind [mm]x'_1,\ldots,x'_{r+h}[/mm] und [mm]y'_1,\ldots,y'_{r+n}[/mm]
> sortierte Versionen von x und y, so gilt [mm]\forall 1 \le i \le r: y'_i \le x'_{i+h}[/mm].
>
> Es ist ganz einfach ... Es ist ein Abzählargument
> Seien [mm]x'_{i+h}[/mm] und [mm]y'_i[/mm] beliebig mit [mm]1\le i \le n[/mm].
Müßte hier nicht $1 [mm] \le [/mm] i [mm] \le \red{r}$ [/mm] stehen?
> [mm]x'_{i+h}[/mm] spaltet die Folge x' in zwei Teile:
> Elemente die grösser [mm]x'_{i+h}[/mm] sind und Elemente die
> kleiner als diese sind.
![[ok]](/images/smileys/ok.gif "[ok]")
> Es gibt r-i Elemente [mm]\ge x'_{i+h}[/mm]
Sind das nicht eher [mm] $r-i\operatorname{\textcolor{red}{+}}\textcolor{red}{1}$ [/mm] Elemente?
> [mm]y'_i[/mm] spaltet
> die Folge y' in zwei Teile:
> Elemente die grösser gleich [mm]x'_{i+h}[/mm] sind und Elemente
> die kleiner gleich als diese sind.
Hast Du hier wirklich [mm]x'_{i+h}[/mm] gemeint? Mir erscheint folgender Satz plausibler:
Elemente die [mm]\ge y'_i[/mm] sind und Elemente die [mm] $\le$ [/mm] als diese sind.
> Es gibt i-1 Elemente [mm]\le y'_{i}.[/mm]
Hier denke ich nun wieder, daß es [mm] $\textcolor{red}{i}$ [/mm] Elemente sind.
> Nun die Beziehungen vor der Sortierung bleiben erhalten,
> also nur die Reihenfolge ändert sich.
> Und unsere Frage ist, ob die Beziehungen ihre Form in der
> sortierten Folgen behalten oder nicht.
> Die Antwort ist ein klares ja.
>
> Warum?
>
> Nun Wir wissen dass es r Elemente in x' gibt, die
> grösser als r Elemente in y' sind. Eine Annahme, die
> diese Tatsache widerspricht ist sicher falsch.
> Wir zeigen nun, dass folgende Annahme diese Tatsache
> widerspricht und dass sie deswegen falsch ist.
>
> Nun nehmen wir an
>
> [mm]\exists 1 \le i \le r[/mm] mit [mm]x'_{i+h} < y'_i[/mm]
> dann gibt es nicht mehr r Elemente in x' die grösser als r
> Elemente in y' sind
Wir verneinen also die ursprüngliche Aussage.
> und das aus folgendem Grund:
>
> Es gibt n-r Elemente [mm]\ge x'_{i+h}[/mm]
Ich denke, hier stimmt die Anzahl der Elemente nicht. Hattest Du nicht auch hier [mm] $r-i+1\!$ [/mm] Elemente im Sinn, für die [mm]\ge x'_{i+h}[/mm] gilt?
> diese können natürlich nur grösser als r-i Elemente aus y' sein.
Ich würde auch hier von [mm] $r-i+1\!$ [/mm] Elementen sprechen. Wie begründest sich: "können nur größer sein"? Das müssen wir doch erst zeigen, oder?
> Nun wir müssen weitere i Elemente in x' finden die grösser als i Elemente in y' sind.
> Diese sind im zweiten Teil von x' zu suchen
> nämlich dem Teil, deren Elemente kleiner gleich
> [mm]x'_{i+h}[/mm] sind
Warum suchen wir dort überhaupt nach solchen [mm] $i\!$ [/mm] Elementen?
> aber diese Elemente sind, wegen der Sortierung der Folge und wegen [mm]x'_{i+h} \le y'_i[/mm], alle [mm]< y'_i[/mm].
> Also wenn dann können sie nur grösser als die Elemente in y' sein, die kleiner [mm]y'_i[/mm] sind, und diese sind nur i-1 (i?) Elemente.
> d.h höchsten kann es r-i+i-1 = r-1 Elemente in x' geben
> die grösser als r-1 Elemente in y' sind.
Statt [mm] $r-i+i-1\!$ [/mm] schreiben wir $r-i+1 + i = [mm] r+1\!$. [/mm] Aber ich denke, daß wir damit auch einen Widerspruch herbeigeführt haben. Schließlich wissen wir, daß es gerade [mm] $r\!$ [/mm] Elemente gibt, für die die obige Behauptung gilt, und jetzt haben wir noch ein Element "hinzugefügt".
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:09 Fr 15.07.2005 | | Autor: | Aly |
Hallo Karl,
Ich denke, ich habe einige Sachen ungenau formuliert.
Dass es (r-i) Elemente grösser gleich [mm] x^{'}_{i+h} [/mm] gibt, ist nur richtig wenn man [mm] x^{'}_{i+h} [/mm] von diesem Vergleich ausschliesst, also gemeint ist folgendes:
Es gibt (r-i) Elemente grösser gleich [mm] x^{'}_{i+h} [/mm] aber deren Index grösser i+h ist.
Nun wie leicht ist es den Beweis einzusehen, nachdem man man es verstanden/entdeckt hat!
Aber es ist sehr schwierig das, was man verstanden hat zu beschreiben oder besser gesagt anschaulich aufzuschreiben.
Ich denke es ist besser es so zu formulieren
Es gibt 7 Brüder und 10 Schwester, die nach Alter aufsteigend angeordnet sind.(d.h wenn ich sage: der erste Bruder, dann heißt das der jüngste Bruder usw.)
Gegeben sei folgendes:
Die ersten 4 Brüder sind kleiner (der Grösser nach) als die letzten vier Schwester
(Ein Analogon für:
Für [mm]h,n,r \in \IN[/mm] seien zwei Zahlenfolgen [mm]x := x_1,\ldots,x_{r+h}[/mm]
und [mm]y := y_1,\ldots,y_{r+n}[/mm] gegeben, so daß für [mm]1 \le i \le r[/mm]
jeweils [mm]y_i \le x_{i+h}[/mm] gilt.)
d.h. 1 Bruder < 7 Schwester, 2 Bruder < 8 Schwester usw... nun ordnen wir die Brüder der Größe nach aufsteigend und die Schwester der Grösse nach aufsteigend.(D.h wenn ich im Folgenden der/die i-te Bruder/Schwester aufschreibe, dann heißt das: der/die i-te kleinste Bruder/Schwester )
Dann ist der 1 Bruder < 7 Schwester, 2 Bruder<8 Schwester, usw
Wieso? Nehmen wir an das gilt nicht ... dann ist einer der Brüder grösser als die entsprechende Schwester, sagen wir mal der zweite grösser als die 8te Schwester (der grösse nach)
Tatsache:
Wir wissen aus obigen Betrachtungen dass 4 Schwester sind grösser als 4 Brüder,
Die grösseren Schwester:
Nun es gibt nur zwei Schwester grösser als die achte. Diese können nur zwei der vier zu erfüllenden Beziehungen erfüllen. D.h wenn diese Schwester mit 2 Brüder in Vergleich stehen, können sie mit anderen nicht mehr verglichen werden, weil ja 4 Schwester gefunden werden müssen, die grösser als mindestens 4 Brüder sind. Also können höchstens mit "zwei Beziehungen" zur Erfüllung der obigen Tatsache beitragen.
Gesucht also noch zwei weiteren Beziehungen.
Die kleineren Schwester:
Die anderen Schwester, die kleiner als die 8te sind, können nicht grösser als die Brüder sein, die grösser oder gleich groß wie der 2te Bruder sind, noch können sie gleich groß wie der zweite Bruder sein, weil er ja grösser als die 8te Schwester ist, wogegen die "kleineren" Schwester höchstens so gross wie die 8te sind. sie können also im besten Fall nur grösser als der 1ste Bruder sein. Also insgesamt sind alle Schwester grösser als höchstens drei Brüder...
Wir wissen aber das dies nicht stimmt aus obigen Überlegungen (es sind ja mindestens vier) also Widerspruch...
Die hier behandelten Zahlen spielen keine Rolle.
Man kann beliebige Zahlen einsetzen ohne die Beweisführung zu schaden. Also der Beweis ist universell genug um zu sagen, dass die Behauptung für eine beliebige Anzahl von Schwestern und Brüdern mit den genannten Vorrausetzungen gilt.
Womit die Behautung bewiesen ist.
Eine bessere Veranschaulichung fällt mir momentan nicht ein. Wenn du das nicht verstanden hast, sag mir Bescheid, vielleicht fällt mir bis dahin was besseres ein.
Grüsse
Aly
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:42 So 17.07.2005 | | Autor: | Karl_Pech |
Hallo Aly!
An dieser Stelle nochmals vielen dank für deine Mühen!
Ich denke, ich habe jetzt begriffen, warum es funktioniert. Ich werde hier dann die Lösung aufschreiben, wenn ich wieder Zeit habe.
Viele Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:07 Mo 18.07.2005 | | Autor: | Aly |
Hallo Karl,
Gut, dass du meine Darstellung verstanden hast. Ich habe mir auch den Beweis noch mal ausgearbeitet, und bin zur folgenden formalen und klaren Darstellung gekommen:
Also nochmal die Aufgabestellung:
> Für [mm]h,n,r \in \IN[/mm] seien zwei Zahlenfolgen [mm]x := x_1,\ldots,x_{r+h}[/mm]
> und [mm]y := y_1,\ldots,y_{r+n}[/mm] gegeben, so daß für [mm]1 \le i \le r[/mm]
> jeweils [mm]y_i \le x_{i+h}[/mm] gilt.
> Zeige: Sind [mm]x'_1,\ldots,x'_{r+h}[/mm] und [mm]y'_1,\ldots,y'_{r+n}[/mm]
> sortierte Versionen von x und y, so gilt [mm]\forall 1 \le i \le r: y'_i \le x'_{i+h}[/mm].
Tatsache:
Wegen der Annahme wissen wir dass es in x',
eine Teilfolge [mm] \phi(x')= x^{'}_{i_{1}}, [/mm] ..., [mm] x^{'}_{i_{r}}
[/mm]
und
in y' ebenfalls
ein Teilfolge [mm] \Phi(y')= y^{'}_{j_{1}}, [/mm] ..., [mm] y^{'}_{j_{r}}, [/mm]
mit
1 [mm] \le [/mm] k [mm] \le [/mm] r: [mm] y'_{j_{k}} \le x'_{i_{k}} [/mm] gibt,
denn nach Sortierung ändern sich die Beziehungen nicht, höchstens die Reihenfolge des Auftretens der Elemente ändert sich.
Beweis durch Widerspruch:
Ist die Behauptung falsch, so gilt [mm]\exists 1 \le i \le r: y^{'}_i > x^{'}_{i+h}[/mm].
Nun wegen der Tatsache müssen r Elemente in x' vorhanden sein, die die Teilfolge [mm] \phi(x') [/mm] bilden und in y' müssen ebendfalls r Elemente vohanden sein, die die Teilfolge [mm] \Phi(y') [/mm] bilden, natürlich mit der in der Tatsache genannten Eigenschaft.
Unter Annhame dass die Behauptung falsch ist, und dass die obige Eigenschaft nicht gilt, fragen wir uns wo sind die Teilfolgen zu finden.
nun [mm] x^{'}_{i+h} [/mm] spaltet x' in zwei Teile:
[mm] T_{1}:= [/mm] Elemente die grösser gleich [mm] x^{'}_{i+h}, [/mm] deren Indizes grösser i+h sind.
und
[mm] T_{2}:= [/mm] Elemente die kleiner gleich [mm] x^{'}_{i+h} [/mm] , deren Indizes kleiner gleich i+h sind.
[mm] y^{'}_{i} [/mm] spaltet y' in zwei Teile:
[mm] T^{'}_{1}:= [/mm] Elemente die grösser gleich [mm] y^{'}_{i}, [/mm] deren Indizes grösser gleich i sind.
und
[mm] T^{'}_{2}:= [/mm] Elemente die kleiner gleich [mm] y^{'}_{i} [/mm] , deren Indizes kleiner i sind.
Betrachten wir nun [mm] T_{1}:
[/mm]
Die Kardinalität von [mm] T_{1} [/mm] ist r-i.
Nehmen wir an alle Elemente von [mm] T_{1} [/mm] zur Teilfolge [mm] \phi(x') [/mm] gehören, dann müssen noch i Elemente in x' vorhanden sein, die zu [mm] \phi(x') [/mm] gehören.
Betrachten wir nun [mm] T_{2}:
[/mm]
Die Kardinalität von [mm] T_{2} [/mm] ist i+h.
Nun die Elemente dieser Menge sind alle kleiner gleich [mm] x^{'}_{i+h} [/mm] (da x' ja sortiert ist)
das heisst sie sind, wegen [mm] y^{'}_i [/mm] > [mm] x^{'}_{i+h}, [/mm] auch alle kleiner als [mm] y^{'}_{i}.
[/mm]
Da y' auch sortiert ist können nur die Elemente von [mm] T^{'}_{2} [/mm] durch Verlgeich mit Elementen in
[mm] T_{2} [/mm] in [mm] \Phi(y') [/mm] sein. Weil wenn wir ein beliebiges Element [mm] y^{'}_{j} [/mm] aus [mm] T^{'}_{1} [/mm] nehmen und es mit einem beliebigen Element [mm] x^{'}_{i} [/mm] in [mm] T_{2} [/mm] vergleicht dann gilt [mm] x^{'}_{i}
Betrachten wir nun [mm] T^{'}_{2}:
[/mm]
Diese Menge enthält i-1 Elemente. Also es gibt in [mm] T_{2} [/mm] höchstens i-1 Elemente die in Beziehung mit diesen Elementen gebracht werden können ohne irgenwelches Element in [mm] T^{'}_{2} [/mm] zu wiederholen (Schubfachprinzip). Also es gibt in [mm] T_{2} [/mm] höchstens i-1 Elemente die zu [mm] \phi(x') [/mm] gehören.
Das heisst in [mm] T_{1} [/mm] und [mm] T_{2} [/mm] gibt es insgesamt nur r-i+i-1 = r-1 Elemente die zu [mm] \phi(x') [/mm] gehören
Aber wir wissen, dass in x' r Elemente gibt, die zu [mm] \phi(x') [/mm] gehören... Widerspruch.
Also es kann nicht sein dass [mm]\exists 1 \le i \le r: y^{'}_i > x^{'}_{i+h}[/mm].
Deswegen gilt [mm]\forall 1 \le i \le r: y^{'}_i \le x^{'}_{i+h}[/mm], womit die Behauptung bewiesen ist.
Ich hoffe das ist formal genug..
Gruß
Aly
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:22 Mo 25.07.2005 | | Autor: | Karl_Pech |
Hallo Aly,
Ich habe Dir noch versprochen, daß ich meine Idee zu dieser Aufgabe hier noch schreibe. Also, zu zeigen ist:
> Für [mm]h,n,r \in \IN[/mm] seien zwei Zahlenfolgen [mm]x := x_1,\ldots,x_{r+h}[/mm]
> und [mm]y := y_1,\ldots,y_{r+n}[/mm] gegeben, so daß für [mm]1 \le i \le r[/mm]
> jeweils [mm]y_i \le x_{i+h}[/mm] gilt.
> Zeige: Sind [mm]x'_1,\ldots,x'_{r+h}[/mm] und [mm]y'_1,\ldots,y'_{r+n}[/mm]
> sortierte Versionen von x und y, so gilt [mm]\forall 1 \le i \le r: y'_i \le x'_{i+h}[/mm].
Dazu sortieren wir zunächst alle [mm] $y_1,\ldots,y_{r+n}$ [/mm] in aufsteigender Reihenfolge, wobei wir die obigen Elemente der [mm] $x\texttt{-Folge} [/mm] "mitschleppen", wodurch oberhalb "leere Zwischenräume" zwischen einzelnen [mm] $x\texttt{-Zahlen}$ [/mm] entstehen. Allerdings wird die vorausgesetzte [mm] $\leqslant\!\texttt{-Beziehung}$ [/mm] durch das "Mitschleppen" nicht gestört. Es gilt jetzt also: [m]\forall h+1 \le j \le h+r \wedge \forall i_j \in \left\{h+1,\dotsc,h+r\right\}: y_j' \le x_{i_j}[/m].
Als Nächstes verschieben wir beginnend bei [mm] $x_{i_1}$ [/mm] alle [mm] $x_{i_j}$ [/mm] soweit wie möglich nach links und lassen die Zwischenräume auf diese Weise verschwinden. Die [mm] $\leqslant\!\texttt{-Beziehung}$ [/mm] wird auf diese Weise nicht gestört. Schließlich haben wir die [mm] $y\texttt{-Folge}$ [/mm] vorher aufsteigend sortiert. Ist also ein beliebiges [mm] $x_{i_k}$ [/mm] größer als das entsprechende [mm] $y_j'$, [/mm] so ist es erst recht größer als die vorherigen [mm] $y\texttt{'s}:\left(y_{j-1}', y_{j-2}'\texttt{ u.s.w.}\right)$. [/mm] Verschieben wir also alle [mm] $x_{i_j}$ [/mm] Elemente nacheinander nach links, so verstärken wir sogar eher die geforderte [mm] $\leqslant\!\texttt{-Beziehung}$ [/mm] anstatt sie abzuschwächen.
Im dritten Schritt sortieren wir die Folge [mm] $\left(x_i\right)_{i=1,\ldots,h+r}$ [/mm] aufsteigend, indem wir jeweils [mm] $x_{\max} [/mm] := [mm] \max \left\{ {x_1 , \dotsc, x_{h + r} } \right\}$ [/mm] bestimmen. Dieses [mm] $x_{\max}$ [/mm] setzen wir dann an die höchste Stelle und verringern unsere Folge um ein Element (nämlich das Höchste) und wiederholen das Ganze bis [mm] $x\!$ [/mm] sortiert ist (umgekehrtes selectionSort). Auch dabei wird die [mm] $\leqslant\!\texttt{-Beziehung}$ [/mm] nicht gestört, denn entweder war das rechteste [mm] $x\texttt{-Element}$ [/mm] der [mm] $x\texttt{-Folge}$, [/mm] welches wir vorher soweit wie möglich nach links verschoben haben, bereits das Maximum: Dann muß sowieso nichts getauscht werden und die [mm] $\leqslant\!\texttt{-Beziehung}$ [/mm] bleibt erhalten, oder aber wir haben dieses Element durch ein noch größeres ersetzt, wodurch die [mm] $\leqslant\!\texttt{-Beziehung}$ [/mm] erst Recht erhalten bleibt. Man könnte einwenden, daß die [mm] $\leqslant\!\texttt{-Beziehung}$ [/mm] durch den Tausch für das "hintere" linke Element verletzt worden ist, weil dort ein größeres Element (das Maximum) durch ein Kleineres ersetzt worden ist, aber auch das ist nicht der Fall, weil die [mm] $y\texttt{-Folge}$ [/mm] vorher sortiert war. Das Maximum, das dort vorher gestanden hat, war größer als ein [mm] $y\texttt{-Element}$, [/mm] das weiter links stand, als das rechteste [mm] $y\texttt{-Element}$. [/mm] Dadurch war aber das vorherige [mm] $x\texttt{-Element}$, [/mm] welches dem rechtesten [mm] $y\texttt{-Element}$ [/mm] entsprach, erst recht größer als das linkere [mm] $y\texttt{-Element}$ [/mm] (zu dem das Maximum vorher in Beziehung stand). Durch den Tausch ist die [mm] $\leqslant\!\texttt{-Beziehung}$ [/mm] also nicht verletzt worden. Damit haben wir die [mm] $x\texttt{-Folge}$ [/mm] und die [mm] $y\texttt{-Folge}$ [/mm] sortiert ohne die [mm] $\leqslant\!\texttt{-Beziehung}$ [/mm] verletzt zu haben, was zu beweisen war. [mm] $\square$
[/mm]
Beispiel:
[m]\begin{gathered}
\begin{array}{cccccccccccc}
{48} & {71} & {82} & 6 & {75} & {35} & {95} & 4 & {} & {} & {} & {} \\
{} & {} & {} & {} & {70} & {35} & {95} & 3 & {81} & {29} & {80} & {69} \\
\end{array} \hfill \\
\hfill \\
{\texttt{nach der Sortierung der }}y{\texttt{-Folge:}} \hfill \\
\hfill \\
\begin{array}{cccccccccccc}
{48} & {71} & {82} & 6 & 4 & {} & {35} & {} & {75} & {} & {} & {95} \\
{} & {} & {} & {} & 3 & {29} & {35} & {69} & {70} & {80} & {81} & {95} \\
\end{array} \hfill \\
\hfill \\
x{\texttt{-Elemente nach links verschieben:}} \hfill \\
\hfill \\
\begin{array}{cccccccccccc}
{48} & {71} & {82} & 6 & 4 & {35} & {75} & {95} & {} & {} & {} & {} \\
{} & {} & {} & {} & 3 & {29} & {35} & {69} & {70} & {80} & {81} & {95} \\
\end{array} \hfill \\
\hfill \\
\leqslant {\texttt{ nicht gestört}}{\texttt{, da z}}{\texttt{.B}}{\texttt{. wegen }}70 < 75{\texttt{ und }}35 < 69 < 70{\texttt{ erst}} \hfill \\
{\texttt{Recht }}35 < 75{\texttt{ gilt}}{\texttt{.}} \hfill \\
{\texttt{Jetzt sortieren wird oben durch umgekehrtes selectionSort:}} \hfill \\
\hfill \\
\begin{array}{cccccccccccc}
{48} & {71} & {75} & 6 & 4 & {35} & {82} & {95} & {} & {} & {} & {} \\
{} & {} & {} & {} & 3 & {29} & {35} & {69} & {70} & {80} & {81} & {95} \\
\end{array} \hfill \\
\vdots \hfill \\
\begin{array}{cccccccccccc}
4 & 6 & {35} & {48} & {71} & {75} & {82} & {95} & {} & {} & {} & {} \\
{} & {} & {} & {} & 3 & {29} & {35} & {69} & {70} & {80} & {81} & {95} \\
\end{array} \hfill \\
\end{gathered}[/m]
Das, was ich oben zu erklären versuchte, kann man sich z.B. an diesem Beispiel klarmachen:
[m]\begin{array}{cccc}
1 & 3 & 2 & {} \\
{} & 1 & 2 & 5 \\
\end{array}[/m]
Hier muß die 3 hinter die 2. Die 2 wandert also nach links. Da aber schon vorher $2 [mm] \le [/mm] 2$ galt und die [mm] $y\texttt{-Folge}$ [/mm] sortiert ist, gilt erst Recht $1 [mm] \le [/mm] 2$, wegen $1 < 2$.
Viele Grüße
Karl
|
|
|
|
