Sortieren

[hos15]

Hallo Liebe Java-Freunde wie würdet ihr diese Aufgabe lösen ?

Aufgabe:
Wolfgang und Sabine sollen ein Feld mit 1000 Werten sortieren. Wolfgang verwendet
einfach einen Bubble-Sort. Sabine teilt das Feld in zwei Felder mit je
500 Werten. Dann lässt sie jedes der beiden Felder mit Bubble-Sort sortieren.
Anschlieÿend mischt sie die beiden sortierten Teilfelder zu einem groÿen Feld zusammen.
Dieses Zusammenmischen benötigt nochmal 500 Vergleiche. Wie viele
Vergleiche benötigen Wolfgang und Sabine jeweils?

 

[Dukel]

Ich würde das Bubble Sort implementieren und einen Counter einbauen, der die vergleiche zählt.

 

[hos15]

und wenn so eine frage in der Prüfung dran kommen würde ? was würdest du dann tun ?

 

[Meniskusschaden]

In der Prüfung würde ich bei der Angabe der 500 Vergleiche für das Mischen Verdacht schöpfen, denn das ist schon sehr spezifisch. Im schlimmsten Fall müssten es doch eigentlich 999 Vergleiche sein. Was für Rückschlüsse kann man daraus auf die Daten ziehen und was würde das für die Laufzeit von Bubblesort bedeuten? Ich vermute, dass dort die Lösung liegt.

 

[hos15]

Bubblesort ist in der Komplexitätsklasse O(n^2). Wolfang Sortiert das Feld mit Bubblesort also hat er im schlimmsten fall 999 vergleiche. Sabine teilt das feld in 2 mit je 500 werten und sortiert. Beide felder sind jeweils in 499 vergleichen Sortiert also wären das 998 Vergleiche. Warum Sabine anschließend nachdem sortieren das Feld wieder zusammenmischt verstehe ich nicht.

 

[Meniskusschaden]

Warum Sabine anschließend nachdem sortieren das Feld wieder zusammenmischt verstehe ich nicht.

Mischen ist hier nicht wie beim Spielkarten mischen im Sinne von "durcheinander bringen" gemeint, sondern als merge-Schritt des Mergesort-Sortierverfahrens. Sabine hat also zwei Felder mit jeweils 500 sortierten Elementen und fügt diese mittels merge-Schritt zu einem 1000 Elemente großen, sortierten Feld zusammen.

 

[Meniskusschaden]

Ich finde den Ansatz von @Dukel übrigens gar nicht so schlecht, würde das aber nur auf dem Papier mit einer kleinen Beispielmenge jeweils nach Wolfgangs und Sabines Verfahren machen. So bekommst du mit relativ wenig Aufwand einen Eindruck, was da abläuft.

 

[Dukel]

Vielleicht das ganze als einfaches beispiel:
3,7,8,4,10,2,5,1,6,9
Wolfgang sortiert und bekommt
1,2,3,4,5,6,7,8,9 bei max neun Vergleichen heraus

Sabine teilt nach
3,7,8,4,10 und 2,5,1,6,9
Sortiert beide nach
3,4,7,8,10 bei max vier Vergleichen und 1,2,5,6,9 bei max vier Vergleichen
Die muss beide sortierten Listen aber nochmal sortieren
3,4,7,8,10,1,2,5,6,9
Dies wird aber vermutlich min. nochmal neun Vergleiche benötigen.

 

[Meniskusschaden]

Vielleicht das ganze als einfaches beispiel:
3,7,8,4,10,2,5,1,6,9
Wolfgang sortiert und bekommt
1,2,3,4,5,6,7,8,9 bei max neun Vergleichen heraus

Das stimmt nicht ganz. Neun Vergleiche reichen nur für den ersten Durchlauf. Hier sind mal die ersten beiden Durchläufe:

3,7,8,4,10,2,5,1,6,9
3,7,4,8,2,5,1,6,9,10 (nach Durchlauf 1 mit 9 Vergleichen)
3,4,7,2,5,1,6,8,9,10 (nach Durchlauf 2 mit 8 Vergleichen)

Sabine teilt nach
3,7,8,4,10 und 2,5,1,6,9
Sortiert beide nach
3,4,7,8,10 bei max vier Vergleichen und 1,2,5,6,9 bei max vier Vergleichen

Hier reichen vier Vergleiche auch nur für den jeweils ersten Durchlauf.

Die muss beide sortierten Listen aber nochmal sortieren
3,4,7,8,10,1,2,5,6,9
Dies wird aber vermutlich min. nochmal neun Vergleiche benötigen.

Das passiert aber mittels Merge-Schritt, so dass nicht mindestens, sondern höchstens 9 Vergleiche erforderlich sind. Um analog zur Aufgabenstellung zu bleiben, müssen hier aber sogar fünf Vergleiche ausreichen. Das bedeutet, dass die Datenkonstellation anders gewesen sein muß, als in diesem Beispiel.

 

[hos15]

Ich glaube mal mit max neun vergleichen meinst du für jeden einzelnen durchgang. Da N=10 wird 9 durchgänge durchgeführt mit max neun vergleichen in jedem durchgang.( wie du schon sagtest).
Also Wolfgang: In 9 durchgängen mit jeweils max 9 vergleiche ist wolfgang fertig mit dem sortieren.

Sabine:
Aufgeteilt in 2 teile und beide teile sortiert mit Bubblesort d.h In jeweils 4 durchgängen mit max 4 vergleiche in jedem durchlauf. Das wären insgesamt 8 durchgänge mit jeweils max 4 vergleiche.
Durch das mischen muss Sabine das Feld mit N=10 nochmal sortieren mit Bubblesort und das wären nochmal 9 durchgänge mit max 9 vergleiche jeweils. Also wären das insgesamt mehr durchgänge und mehr vergleiche bei Sabine.

 

[hos15]

also fazit:

Wolfgang braucht (10-1)*10/2 vergleiche also : 45

 

[hos15]

und sabine braucht einmal 2* ((5-1)*5/2)= 20 vergleiche und beim mischen
braucht sie nochmal 45 vergleiche. Also braucht sie insgesamt 65 vergleiche

Natürlich nur im schlimmstenfall

 

[hos15]

Übertragen auf unsere aufgabe wäre dies aber ganz einfach da wir nur noch die ergebnisse mal 100 nehmen müssen und unser Problem wäre dann N=1000. Also braucht Wolfgang

4500 Vergleiche und Sabine 6500 Wolfgang gewinnt. Was sagt ihr zu diesen überlegungen ?

 

[Meniskusschaden]

Wolfgang braucht (10-1)*10/2 vergleiche also : 45

Das wäre der worst case. Bei der aktuellen Aufgabenstellung wäre das Feld aber bereits nach vier Durchgängen sortiert. Wenn der Bubblesort so implementiert ist, dass das erkannt wird, benötigt Wolfgang also deutlich weniger Vergleiche.

und sabine braucht einmal 2* ((5-1)*5/2)= 20 vergleiche und beim mischen
braucht sie nochmal 45 vergleiche. Also braucht sie insgesamt 65 vergleiche

Wie bereits geschrieben, benötigt sie für das Mischen zweier sortierter Felder im Allgemeinen maximal neun Vergleiche, in diesem speziellen Fall genügen aber fünf Vergleiche.

Übertragen auf unsere aufgabe wäre dies aber ganz einfach da wir nur noch die ergebnisse mal 100 nehmen müssen und unser Problem wäre dann N=1000. Also braucht Wolfgang

4500 Vergleiche und Sabine 6500 Wolfgang gewinnt. Was sagt ihr zu diesen überlegungen ?

Wenn du deine Formel mal für n=10 und n=1000 ausrechnest, siehts du, dass das nicht stimmen kann.

 

[hos15]

Ja das stimmt das habe ich nicht beachtet als Mathestudent ist das echt blöd
Also Speziell in der Aufgabe würde es etwas schwer sein den besten fall zu berücksichtigen.
Daher würde ich bei dieser Aufgabe vom worst Case ausgehen.

Wolfgang würde dabei 499500 vergleiche brauchen
und Sabine 749000 vergleiche also deutlich mehr Aufwand als Wolfgang.

Wenn man Speziell das Beispiel von Dukel nehmen würden dann würde Wolfgang im worst case
45 vergleiche brauchen und Sabine 65.
Aber da wir in diesem fall den Best case mit berücksichtigen sollten würde es deutlich weniger durchgänge brauchen aber wie viele genau das weiß ich nicht wie ich das sehen soll :/ kannst du mir dazu ein tipp geben

 

[Meniskusschaden]

und sabine braucht einmal 2* ((5-1)*5/2)= 20 vergleiche und beim mischen
braucht sie nochmal 45 vergleiche. Also braucht sie insgesamt 65 vergleiche

Du gehst offenbar immer noch davon aus, dass das abschliessende Mischen bei Sabines Lösung durch Bubblesort-Sortierung gelöst wird. Wie soll das bei 2x500 Elementen denn mit 500 Vergleichen möglich sein, wenn es bei nur 10 Elementen bereits 45 Vergleiche erfordert? Die 500 Vergleiche würden doch nicht einmal für einen einzigen Bubblesort-Durchlauf ausreichen.

 

[hos15]

und das heißt ? verstehe ich leider nicht ganz :/

 

[Meniskusschaden]

Sabine hat unmittelbar vor dem Mischen zwei sortierte Felder mit jeweils 500 Elementen. Das Mischen läuft analog dem Merge-Schritt des Mergesort-Verfahrens so ab, dass für beide Felder je ein Zeiger auf das jeweils erste Element zeigt. Dann werden die beiden Elemente auf die die Zeiger zeigen verglichen. Das kleinere wird in das Ergebnisfeld überführt und sein Zeiger auf das nächste Element positioniert. Das wird so lange wiederholt, bis eines der Felder komplett abgearbeitet ist. Die verbliebenen Elemente des anderen Feldes werden dann einfach in das Ergebnisfeld überführt. Dafür benötigt man im schlimmsten Fall 999 Vergleiche (oder im Beispiel von @Dukel neun Vergleiche). Hier sind mal die ersten Schritte mit den sortierten Teilmengen des Beispiels von @Dukel. x und X repräsentieren die beiden Zeiger, wobei das kleinere x den kleineren Wert des aktuellen Vergleichs anzeigt:

X
3,4,7,8,10
1,2,5,6,9
x                       1<3 => 1

X
3,4,7,8,10
1,2,5,6,9
  x                     2<3 => 2

x                       3<5 => 3
3,4,7,8,10
1,2,5,6,9
    X

  x                     4<5 => 4
3,4,7,8,10
1,2,5,6,9
    X