| Chris |
Naiv Random Sort
Meine Frage:
Liebe Informatiker, ich bin zwar kein Informatiker, sondern Physiker, aber ich wäre euch sehr dankbar, wenn ihr mir auf die Sprünge helfen könntet.
Ein Algorithmus sortiert ein Array A der Länge n, indem er in jedem Iterationsschirtt zwei uniformverteilte Zufallszahlen i und j zwischen 1 und n generiert und dann die die Einträge i und j vertauscht, falls der "linke" Eintrag größer als der "rechte ist:
0 <= i,j <=n, tausche falls A(min(i;j)) > A(max(i;j))
Aufgabe:
1) A ist nicht sortiert. Zeige, dass die Wahscheinlichkeit für einen Swap im nächsten Iterationsschritt mindestens 1/(n,2) ist.
2) A ist nicht sortiert. Zeige, dass die erwartete Anzahl an Iterationen bis zum nächsten Swap (n,2) ist.
3)Zeige, dass der Algorithmus nach höchstens (n,2) swaps endet.
4) Wie groß ist die Ordnung der durchgeführten Iterationen des Algorithmus?
Meine Ideen:
Zur 1)
Wenn ich das Ergebnis ausschreibe, bekomme ich 1/(n,2) = 2/ n*(n-1) was im Laplace-W-Raum der W-Keit von zwei erwünschten Ereignissen bei insgesamt n*(n-1) Ereignisse entspricht.
Da in der Aufgabe nach der Mindestwahrscheinlichkeit gefragt ist, habe ich einen Fall angenommen, in dem die Wahrscheinlichkeit minimal ist für einen Swap, und zwar wenn das Array A fast sortiert ist mit nur zwei Einträgen, die geswappt werden können. z.B
2,5,3,4,6
Der Zufallszahlengenerator müsste als entweder (5,4) oder (4,5) ausgeben, damit ein swap stattfindet. Allerdings gibt es insgesamt n^2 mögliche Ereignisse (i,j), wenn i und j auch gleich sein können, was bei einem ZZG ja eigentlich der Fall sein sollte. Wenn ich mir das Ergebnis anschaue, sollten es aber n*(n-1) Ereignisse sein, was der Annahme entspricht, dass keine zwei gleichen Zahlen generiert werden können. Diese Annahme finde ich aber nicht sinnvoll! |
