Worst-Case-Verhalten < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 03:21 So 22.01.2006 | | Autor: | Gerd52 |
Hallo Forumsfreunde,
ich habe wieder ein paar Fragen und es geht um Sortieralgorithmen.
Wenn ich ein ungeordnetes Array der Länge n habe und in diesem sollen nur die Schlüsselwerte 0 und 1 vorkommen, nach denen das Array aufsteigend sortiert werden soll.
Wie wirkt sich das auf das Worst Case Verhalten des"Sortieren durch Einfügen" aus und wie schaut das Eingabearray aus, das dem Wort Case entspricht bzw und wie groß sind die Anzahl der Rechenoperationen die ich dafür benötige?
Danke für eure Hilfe
Gerd
|
|
| |
|
Hallo Gerd,
> Wenn ich ein ungeordnetes Array der Länge n habe und in
> diesem sollen nur die Schlüsselwerte 0 und 1 vorkommen,
> nach denen das Array aufsteigend sortiert werden soll.
> Wie wirkt sich das auf das Worst Case Verhalten
> des"Sortieren durch Einfügen" aus und wie schaut das
> Eingabearray aus, das dem Wort Case entspricht bzw und wie
> groß sind die Anzahl der Rechenoperationen die ich dafür
> benötige?
Ich habe jetzt einige Zeit an dieser Aufgabe (auf einem Blatt Papier) rumprobiert und muß doch sagen, daß es gar nicht so einfach ist, sich eine passende Folge zu überlegen.
Dann legte ich das Blatt zur Seite und machte am Computer weiter. Ich dachte mir nämlich, daß man ja auch insertionSort an einigen Folgen ausführen, und dabei die Anzahl der Operationen, die es für die Folgen benötigt, aufzeichnen könnte.
Wie müßte man da nun vorgehen? Am Besten systematisch! 
Man kann ja genau [mm]2^n[/mm] Folgen der Länge [mm]n[/mm] konstruieren. Jede dieser Folgen sortiert man dann mit insort und schreibt sich dabei die Anzahl der Operationen auf, die insort für die Folge gebraucht hat. So ... nun nimmt man einfach die Folge, bei der insort die größte Anzahl an Operationen ausgeführt hat.
Nun wäre es natürlich müßig das alles per Hand zu machen, also lassen wir den Computer mal dran arbeiten. 
Hier ist das C++ - Programm, daß ich geschrieben habe:
| 1: |
| | 2: | #include <math.h>
| | 3: | #include <iostream>
| | 4: | using namespace std;
| | 5: |
| | 6: | int n;
| | 7: | int maxnumwhileops = 0;
| | 8: | int* maxarray;
| | 9: |
| | 10: | void insertionSort(int a[], int org_a[], int l, int r){
| | 11: | int numwhileops = 0;
| | 12: |
| | 13: | for(int i=l+1; i <= r; i++){
| | 14: | int x = a[i];
| | 15: | int j = i-1;
| | 16: | while(l<=j && x < a[j]){
| | 17: | a[j+1] = a[j];
| | 18: | j--;
| | 19: |
| | 20: | numwhileops++;
| | 21: | }
| | 22: | a[j+1] = x;
| | 23: | }
| | 24: |
| | 25: | if(numwhileops > maxnumwhileops)
| | 26: | {
| | 27: | maxnumwhileops = numwhileops;
| | 28: |
| | 29: | for(int k = 0; k <= n-1; k++)
| | 30: | maxarray[k] = org_a[k];
| | 31: | }
| | 32: | }
| | 33: |
| | 34: | int main(int argc, char* argv[])
| | 35: | {
| | 36: | n = atoi(argv[1]);
| | 37: | int grenze = pow(2, n) - 1;
| | 38: |
| | 39: | int* a = new int[n];
| | 40: | int* original_a = new int[n];
| | 41: | maxarray = new int[n];
| | 42: |
| | 43: | for(int i = 0; i <= grenze; i++)
| | 44: | {
| | 45: | int anfang = i;
| | 46: |
| | 47: | for(int k = 0; k <= n-1; k++)
| | 48: | {
| | 49: | int rest = anfang % 2;
| | 50: | anfang /= 2;
| | 51: |
| | 52: | a[k] = rest;
| | 53: | original_a[k] = rest;
| | 54: | }
| | 55: |
| | 56: | insertionSort(a, original_a, 0, n-1);
| | 57: | }
| | 58: |
| | 59: | cout << endl << "n = " << n << ":" << endl;
| | 60: |
| | 61: | cout << "Feld: ";
| | 62: | for(int k = 0; k <= n-1; k++)
| | 63: | cout << maxarray[k];
| | 64: | cout << endl;
| | 65: |
| | 66: | cout << "Anzahl der Zuweisungen in der WHILE-Schleife: " << maxnumwhileops << endl << endl;
| | 67: |
| | 68: | delete [] a;
| | 69: | delete [] original_a;
| | 70: | delete [] maxarray;
| | 71: | return 0;
| | 72: | }
|
Im Wesentlichen habe ich mir per Google eine Implementation von insort rausgesucht, und Diese dann "an ein Meßgerät angeschlossen".
In Zeile 36 nimmt das Programm die Länge des Feldes von der Eingabezeile entgegen. Danach wird 'grenze' auf [mm]2^n - 1[/mm] gesetzt, und es werden alle möglichen [mm]2^n[/mm] Folgen von 0 bis [mm]2^n - 1[/mm] "abgezählt" (das ist hier durchaus wörtlich zu verstehen!). Jede dieser Folgen wird in Zeile 56 sortiert, wobei die unsortierte Folge in '[mm]\texttt{original}[/mm]_[mm]\texttt{a}[/mm]' festgehalten wird.
Das "Abzählen" geschieht in den Zeilen 45 - 54. Hier wird nur die Umwandlung einer Zahl aus dem Dezimalsystem ins Binärsystem vollzogen. Die Reste der einzelnen Modulo-Operationen werden im Feld gespeichert. [Vom Standpunkt der Umwandlung wäre das hier fehlerhaft, da die Zahl in umgekehrter Ziffernfolge abgespeichert wird; in Zeile 52 müßte also a[n-1-k] stehen. Aber das ist hier nicht wichtig, weil wir hier lediglich alle möglichen Folgen aufzählen wollen. Da dieses Verfahren ab einem gewissen Zeitpunkt nur noch die Operation [mm]0 \mod 2 = 0[/mm] ausführt, wird das Feld auch wirklich mit allen Möglichkeiten belegt.]
In insertionSort zählen wir dann in 'numwhileops' die Anzahl der Zuweisungen in der WHILE-Schleife. In den Zeilen 25-31 prüfen wir dann, ob ein neues Maximum bezgl. den Zuweisungsanzahl erreicht wurde, und merken uns das ursprüngliche Feld, wenn dem so war.
Führt man das Programm mit verschiedenen Feldlängen aus, erhält man folgende Ausgaben:
| 1: |
| | 2: | n = 1:
| | 3: | Feld: 0
| | 4: | Anzahl der Zuweisungen in der WHILE-Schleife: 0
| | 5: |
| | 6: |
| | 7: | n = 2:
| | 8: | Feld: 10
| | 9: | Anzahl der Zuweisungen in der WHILE-Schleife: 1
| | 10: |
| | 11: |
| | 12: | n = 3:
| | 13: | Feld: 100
| | 14: | Anzahl der Zuweisungen in der WHILE-Schleife: 2
| | 15: |
| | 16: |
| | 17: | n = 4:
| | 18: | Feld: 1100
| | 19: | Anzahl der Zuweisungen in der WHILE-Schleife: 4
| | 20: |
| | 21: |
| | 22: | n = 5:
| | 23: | Feld: 11000
| | 24: | Anzahl der Zuweisungen in der WHILE-Schleife: 6
| | 25: |
| | 26: |
| | 27: | n = 6:
| | 28: | Feld: 111000
| | 29: | Anzahl der Zuweisungen in der WHILE-Schleife: 9
| | 30: |
| | 31: |
| | 32: | n = 7:
| | 33: | Feld: 1110000
| | 34: | Anzahl der Zuweisungen in der WHILE-Schleife: 12
| | 35: |
| | 36: |
| | 37: | n = 8:
| | 38: | Feld: 11110000
| | 39: | Anzahl der Zuweisungen in der WHILE-Schleife: 16
| | 40: |
| | 41: |
| | 42: | n = 9:
| | 43: | Feld: 111100000
| | 44: | Anzahl der Zuweisungen in der WHILE-Schleife: 20
| | 45: |
| | 46: |
| | 47: | n = 10:
| | 48: | Feld: 1111100000
| | 49: | Anzahl der Zuweisungen in der WHILE-Schleife: 25
| | 50: |
| | 51: |
| | 52: | n = 11:
| | 53: | Feld: 11111000000
| | 54: | Anzahl der Zuweisungen in der WHILE-Schleife: 30
| | 55: |
| | 56: |
| | 57: | n = 12:
| | 58: | Feld: 111111000000
| | 59: | Anzahl der Zuweisungen in der WHILE-Schleife: 36
| | 60: |
| | 61: |
| | 62: | n = 13:
| | 63: | Feld: 1111110000000
| | 64: | Anzahl der Zuweisungen in der WHILE-Schleife: 42
| | 65: |
| | 66: |
| | 67: | n = 14:
| | 68: | Feld: 11111110000000
| | 69: | Anzahl der Zuweisungen in der WHILE-Schleife: 49
| | 70: |
| | 71: |
| | 72: | n = 15:
| | 73: | Feld: 111111100000000
| | 74: | Anzahl der Zuweisungen in der WHILE-Schleife: 56
|
Aus diesen Ergebnissen ziehen wir jetzt zwei Vermutungen:
Behauptung 1.
Unter allen Wörtern aus [mm]\{0,1\}^n[/mm] benötigt insort für das Wort [mm]\omega := 1^{\lfloor n/2\rfloor}0^{n-\lfloor n/2\rfloor} \in \{0,1\}^n[/mm] die größte Anzahl an Operationen.
Wie sortiert insort eine solche Folge? Indem er die [mm]\left\lfloor\frac{n}{2}\right\rfloor + 1\texttt{--te}[/mm] 0 der Folge durch [mm]\left\lfloor\frac{n}{2}\right\rfloor[/mm] Vertauschungen nach links verschiebt (zumindest kann man das bei den obigen Beispielen beobachten). Und wie viele Male macht insort sowas? Offenbar genau so viele Male, wie es 0en im Wort gibt. Damit formulieren wir unsere zweite Behauptung:
Behauptung 2.
insort benötigt [mm]\left\lfloor\frac{n}{2}\right\rfloor\left(n-\left\lfloor\frac{n}{2}\right\rfloor\right) = \mathcal{O}(n^2)[/mm] Zuweisungsoperationen in seiner WHILE-Schleife um [mm]\omega[/mm] aufsteigend zu sortieren.
Tja ... soviel erstmal zu den Behauptungen. Nur der Beweis steht noch aus. ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]")
Liebe Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
[P.S. Der Beweis läuft vermutlich über Induktion(; eventuell mußt Du die zu beweisenden Aussagen dazu noch etwas "anpassen").]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:35 Mi 25.01.2006 | | Autor: | PStefan |
Hallo!
Leider konnte dir keiner, gänzlich deine Frage beantworten, sondern nur teilweise.
Vielleicht hast du nächstes Mal mehr Glück. ![[kleeblatt]](/images/smileys/kleeblatt.gif "[kleeblatt]")
Liebe Grüße
PStefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:02 Mi 25.01.2006 | | Autor: | mathiash |
Hallo zusammen !
Ich finde, Karl hat sehr wohl die Frage komplett beantwortet, der Beweis, der seiner Meinung nach noch ausstand, steht informell in seiner Antwort, und das reicht doch auch.
Hut ab !!!
Gruss,
Mathias
|
|
|
|
